Leetcode BLIND-75 Flashcards
List of Popular Leetcode BLIND 75 Questions. NeetCode: https://neetcode.io/practice
217. Contains Duplicate ( Easy )
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct
Example 1:
Input: nums = [1,2,3,1] Output: true
- Convert given array into set ( it will remove duplicates)
- Again convert that set into array
set_nums = list(set(nums)) - if both original array and set array has same length means there were no duplicates present
- so return false` if len(nums) == len(set_nums): return False`
- else means they differ in length so there were duplicates present` return True`
242. Valid Anagram ( Easy )
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram" Output: true
Example 2:
Input: s = "rat", t = "car" Output: false
- Base Case:
if len(s) != len(t): return False - Create two Hashmaps
- Iterate and store char in string as key and count as value
- return True if both dict are same else false.
return countS == countT
Code
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t): return False
countS, countT = {}, {}
for i in range(len(s)):
countS[s[i]] = 1 + countS.get(s[i], 0)
countT[t[i]] = 1 + countT.get(t[i], 0)
return countS == countT
1. Two Sum ( Easy )
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Explanation: nums[0] + nums[1] == 9, we return [0, 1]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i in range(len(nums)):
if (target- nums[i]) in d: return [i, d[target-nums[i]]]
d[nums[i]] = i
49. Group Anagrams ( Medium )
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
- have a defaultdict of type list
` d = defaultdict(list)`
- iterate through array of strings and map tuple of sorted string as key with value as list of all the strings
for s in strs:
d[tuple(sorted(s))].append(s)
- lastly return all values in a string
` return d.values()`
Code
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
d[tuple(sorted(s))].append(s)
return d.values()
347. Top K Frequent Elements ( Medium)
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Code
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
freq = [[] for i in range(len(nums) + 1)]
for n in nums:
count[n] = 1 + count.get(n, 0)
for n, c in count.items():
freq[c].append(n)
res = []
for i in range(len(freq) - 1, 0, -1):
for n in freq[i]:
res.append(n)
if len(res) == k:
return res
# O(n)
238. Product of Array Except Self ( Medium)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4] Output: [24,12,8,6]
Code
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * (len(nums))
for i in range(1, len(nums)):
res[i] = res[i-1] * nums[i-1]
postfix = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res
125. Valid Palindrome ( Easy )
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama" Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Code
class Solution:
def isPalindrome(self, s: str) -> bool:
s = ''.join(c for c in s if c.isalnum()).lower()
return s == s[::-1]
Another Simple Example of Code
class Solution:
def isPalindrome(self, s: str) -> bool:
new_string = ''
for c in s:
if c.isalnum():
new_string += c
new_string = new_string.lower()
return new_string == new_string[::-1]
15. 3Sum (Medium)
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
- Sort the array
- Intialise res array to return later
- Iterate using enumerate function, as we will need number as well as index here
- If its not the first number and is equal to previous number then continue as its will give us the same/duplicate pairs again
if i > 0 and nums[i] == nums[i-1]: continue
- Rest of the problem is similar to Two Sum ll
- Initialise two pointers
l, r = i+1, len(nums)-1 - In the else part of code while
landrare not crossing each other and while number is equal to previous number, we will keep incresing the left pointer as we will keep getting the duplicates - Lastly we will return the
resarray
Code
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i, ele in enumerate(nums):
if i > 0 and nums[i] == nums[i-1]: continue
l, r = i+1, len(nums)-1
while l < r:
threesum = ele + nums[l] + nums[r]
if threesum > 0: r -= 1
elif threesum < 0: l += 1
else:
res.append([ele, nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]: l += 1
return res
11. Container With Most Water (Medium)
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1] Output: 1
- Two pointer method
- At each point,
curr_arerais min of height and distance betweenrandlcurrArea = min(height[l], height[r])*(r-l)maxArea = max(maxArea, currArea)
Code
class Solution:
def maxArea(self, height: List[int]) -> int:
maxArea = 0
l = 0
r = len(height)-1
while l <= r:
currArea = min(height[l], height[r])*(r-l)
maxArea = max(maxArea, currArea)
if height[l] < height[r]: l += 1
else: r -= 1
return maxArea
121. Best Time to Buy and Sell Stock (Easy)
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
cheap = prices[0]- max profit
maxPis0 - iterate, if curr
prices[i]is less than cheap thencheap = prices[i] - current profit
currPisprices[i] - cheapand -
maxPismax(maxP, currP) - lastly return max profit
maxP
Code
class Solution:
def maxProfit(self, prices: List[int]) -> int:
cheap = prices[0]
maxP = 0
for i in range(1, len(prices)):
if prices[i] < cheap:
cheap = prices[i]
currP = prices[i] - cheap
maxP = max(maxP, currP)
return maxP
20. Valid Parentheses (Easy)
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]" Output: false
- for every char in string if char is in
"([{"then will add to stack -
elifchar in string is")]}"and if stack’s last element is not"([{"resp or if stack is empty thenreturn Falseand pop the element from stack - lastly if stack is empty then
return Trueelsereturn False
Code
class Solution:
def isValid(self, s: str) -> bool:
st = []
for c in s:
if c in '([{':
st.append(c)
elif c is ')':
if (not st or st[-1] != '('): return False
st.pop()
elif c is']':
if (not st or st[-1] != '['): return False
st.pop()
elif c is'}':
if (not st or st[-1] != '{'): return False
st.pop()
if not st: return True
return False
153. Find Minimum in Rotated Sorted Array (Medium)
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
-
[4,5,6,7,0,1,2]if it was rotated 4 times. -
[0,1,2,4,5,6,7]if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2] Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
-
mid = l + (r-l) // 2( so that left + right doesn’t go above 32 bit Integer ) - Do Binary Search and return
nums[l]
Code
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums)-1
while l < r:
mid = l + (r-l) // 2
if nums[mid] < nums[r]: r = mid
else: l = mid+1
return nums[l]
33. Search in Rotated Sorted Array (Medium)
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
- Binary Search two pointers
landr - ` if nums[mid] == target: return mid `
- If
nums[mid]is greater than or equal tonums[l]then left part is sorted so now search in left part - If
targetis greater thannums[mid]or if less thannums[l]andnums[mid
then search in right part.l = mid+1 - In the else section right part is sorted
- If
targetis less thannums[mid]ortargetis greater thannums[mid]andtargetis gretaer thannums[r]then search in left part. i.er = mid-1 - Lastly return
-1as element is not found.
Code
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1
while l <= r:
m = (l+r) // 2
#middle element
if nums[m] == target: return m
#target found
elif nums[m] >= nums[l]:
#left part is sorted
if target > nums[m] or (target < nums[l] and target < nums[m]):
l = m+1
else: r = m-1
else:
#right part is sorted
if target < nums[m] or ( target > nums[m] and target > nums[r]):
r = m-1
else: l = m+1
return -1
206. Reverse Linked List ( Easy )
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Code
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
21. Merge Two Sorted Lists ( Easy )
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
- Create
curentanddummyNode asListNode(0) - while both
l1andl2is not empty, we will iterate andcurrent.nextwill be smaller value - Lastly to add reamining values from
list1andlist2we will do current.next = l1 or l2return dummy.next
Code
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
current = dummy = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
141. Linked List Cycle ( Easy)
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to.
Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Code
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return True
return False
23. Merge k Sorted Lists ( Hard )
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
- Base Case is that if len of
listsis0or1then we will returnNoneorlists[0]resp. mid = len(lists) // 2- We will Recursively call the given function on left and right part
- Then we will
returntheMergeTwoListsfunction on left and right part. - In the code below the return, we have defined
mergeTwoListswhich is excat code of Merge Two Linked Lists Problem
Code
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
#base case
if len(lists) == 0: return None
if len(lists) == 1: return lists[0]
mid = len(lists) // 2
left = self.mergeKLists(lists[:mid])
right = self.mergeKLists(lists[mid:])
#call defined function on left and right two merge them
return self.MergeTwoLists(left, right)
#define function to merge two linked lists into one
def MergeTwoLists(self, l1, l2):
new = curr = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return new.next
226. Invert Binary Tree ( Easy )
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3] Output: [2,3,1]
- Base Case: if
rootis empty orroot.leftandroot.rightis empty then we will return theroot. - We will assign
root.lefttoroot.rightand vice-versa - We will Recursively call the function on left and right subtree
- return the
root
Code
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root or (not root.left and not root.right): return root
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
104. Maximum Depth of Binary Tree ( Easy )
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
- ` if not root: return 0`
- 1 + max of Two Recursive Functions ( left and right )
Code
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
