leetcode_new Flashcards
(90 cards)
1
Q
2 sum: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
A
2 sum — want to add 2 number and see if they’re in target. One way to sort it and use 2 pointers but this is 2 sum II is the input is sorted. If its not sorted you basically need to go through each element in the list and see if the element you need to sum it to target is present in the array, search of the array is achieved by pushing every element you visit into a dictionary or set and making checking if the element you need is already there. Push into set only after you visit each element not before. If target is 6 and first element is 3 you don’t want to push 3 into dictionary first and then look in dictionary to find it and say you’ve got a match.
2
Q
2 sum II: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Input Array Is Sorted
A
2 sum II — since input is sorted 2 pointers make the most sense here. Start from the 2 ends of the array and compare the sum with target. If the sum is larger then reduce the high pointer and if the target is larger then increase the left low
pointer.
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = len(numbers)-1
while l numbers[l]:
l += 1
elif target - numbers[l] < numbers [r]:
r -= 1
3
Q
3 sum: 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!!!!
A
3 sum — pretty much an extension to 2 sum. I don’t like neetcode’s solution. What I did instead of iterate through the loop and each time look at the rest of the array as a 2 sum problem with target being negative of the hook element you’re iterating throughh.
But the efficient solution is to sort the array and then iterate through the loop to get a pivot element and then do 2 sum II on the elements in the array after pivot element and figure out which 2 elements add to sum. move pointer based on if sum is greater than or less than target which is negative of pivot element. To get unique elements skip over repeat elements.
Basically breaks the problem into a 2 sum with different target. add to set() to make sure no duplicates.
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = set()
visited = set()
for i in range(len(nums)):
if nums[i] in visited:
continue
visited.add(nums[i])
two_sum = set()
for j in range(i+1, len(nums)):
if -nums[i] - nums[j] in two_sum:
srtd_set = sorted([nums[i],nums[j],-nums[i]-nums[j]])
result.add(tuple(srtd_set))
two_sum.add(nums[j])
return [[i,j,k] for (i,j,k) in result]
Two Pointers
(3 / 5)
Prerequisites
Two Pointers
Advanced Algorithms
Status
Star
Problem
Difficulty
Video Solution
Code
Valid Palindrome
Two Sum II Input Array Is Sorted
3Sum
Container With Most Water
Trapping Rain Water
View on Github
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
# Skip positive integers
if a > 0:
break
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res Select Roadmap
(30 / 150)
4
Q
Valid anagram: Given two strings s and t, return true if t is an anagram of s, and false otherwise. Can’t use sorting.
A
Valid anagram - Want to check if 2 strings have all the same alphabets and the same counts basically so you create a dictionary and add elements based on one string and subtract based on another, if not equal then its not an anagram.
5
Q
Contains Duplicate: 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.
A
Contains Duplicate - check for duplicate in a list. Another simple Hashmap implementation will do.
6
Q
Group Anagrams: Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
A
Group Anagrams - good rule of thumb for any grouping or similarity question is to try and hash it I think. Anyways for this one sorting each string in a new array and then hashing them with the index gives you location of similar string in the original array. After that all you need to do is create the answer. Can hash without sorting to avoid nlogn complexity if needed. See code below:
class Solution:
def hashify(self, string):
hash_list = [0]*26
for char in string:
hash_list[ord(char)-ord(‘a’)] += 1
hash_str = “”
for ele in hash_list:
hash_str+= str(ele) + ‘#’
return hash_str
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result_map = {}
for string in strs:
str_sorted = self.hashify(string)
if str_sorted in result_map:
result_map[str_sorted]+= [string]
else:
result_map[str_sorted] = [string]
return [result_map[key] for key in result_map]
7
Q
Top K freq elements: Given an integer array nums and an integer k, return the k most frequent elements. Do it in O(n) time.
A
You gotta do it in O(n). first solution that come to mind is prolly to put elements with count into dictionary and then sort dict.items() according to count and print top k elements. but the sorting is O(nlogn). Instead to do it in O(n) you take the dictionary with count and create a count array of size len(input_array)+1 and then at each index element put a list of numbers that have count as many as index. which means if there are 3 1’s and 3 2’s in your input then at index 3 in count array you’ll have [1,2].
8
Q
Product of Array Except Self
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]. You must write an algorithm that runs in O(n) time and without using the division operation.
A
You need to create 2 array by scanning through the input array twice. One is prefix with product of every element before itself at the corresponding index position and another array postfix where you scan through the array in reverse and have the product of every element after the index at corresponding index position. You can make it more efficient by directly creating answer arrat while calculating postfix.
9
Q
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
A
Put all elements in a set. iterate through the input array;
Good solution: you check if ele - 1 exists in the set if so you don’t start counting, this means that ele is part of a longer sequence which will get counted later. You start counting only if ele-1 is not in the set.
Not as good solution but still works: you find a possible start for every sequence by checking if the next number exists in the array for every element in the array (or more efficiently checking If num + max_count exists in the array) this tells us whether its worth it to check if all consecutive elements exist in the array. you check for how many consecutive elements exist for such a case and track that count and return max_count.
def longestConsecutive(self, nums: List[int]) -> int:
nums_set = set(nums)
result = 0
for num in nums_set:
seq_len = 1
if num+result in nums_set:
while num+1 in nums_set:
seq_len+=1
num+=1
result = max(result, seq_len)
return result
10
Q
Valid Palindrome: check if a string is valid palindrome. have to ignore all non-alphanumeric characters while checking. need to be case insensitive. (do you remember functions to convert string to lowercase and to check if string is alphanumeric)?
A
two pointers from both ends of the string and keep checking for similarity. str.lower() converts str to lowercase and returns it. str.isalnum() return true/false depending on if alphanumeric.
class Solution:
def isPalindrome(self, s: str) -> bool:
start = 0
end = len(s) - 1
while start < end:
while (not s[start].isalnum()) and start<end:
start+=1
while (not s[end].isalnum()) and start<end:
end-=1
if s[start].lower() != s[end].lower():
return False
start +=1
end -=1
return True
11
Q
Container With Most Water
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.
A
you start 2 pointers at 0 and len(heights) - 1 as this is what maximises width in height*width = area, then you want to reduce width only if that can increase height and possibly then increase area. So you find which of l and r pointers in minimum and move it. You keep doing this and then return max_area hence obtained.
start from both ends of the array with pointers and move the pointer with the lesser height while storing volume at each stage along the way as width * min(left_pointer_height, right_pointer_height). You’re moving the limiting factor value pointer
some intuition: You’re always moving the limiting factor, which is why even if there’s a much larger wall ahead of the maximum of the 2 container walls it doesn’t make sense to choose that because all you’ll be doing is reducing width without increasing height. for example if there is [5, 15, 2, 3, 4, 3] when you’re first at 5 and 3 it makes sense to move 3 and look for a higher wall, the fact that you have 15 in front of 5 doesn’t change the volume as it’ll be 3*width anyways even if the other wall is 5 or 15.
#start with two pointers at both ends of the array and move the one which is the limiting factor as there's no
#point in moving the one which isn't even to a possibly higher position.
12
Q
Best Time to Buy and Sell Stock
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.
A
you start with creating 2 pointers to note 2 values, one is min value in array and other is curr_price pointer. As you iterate through the loop if your curr_price is less than min_price then you update min_price to be there and keep calculating profit as curr_price - min_price. You return maximum when you’re done iterating through the loop. This makes sense as you basically want to buy lowest and sell highest after lowest. you keep updating lowest as you traverse the array and calculate profit at every price after that and return the maximum hence obtained.
best way to think about this is you want to find the minimum buying point and maximum selling point. If you have 2 pointers l and r, where r is your selling point for every r you want the minimum l before it. so start with l and r at 0 and 1 and then keep pushing r forward with l being the minimum before r which can be set by making l=r when nums[r] < nums[l]. This works as if we find a point less than min as we traverse an array we should have bought then as for a max price after it this makes sense. If the best min and max price were before this new min then that has already been recorded in max_price which we update for every new sliding window
def maxProfit(self, prices: List[int]) -> int:
min_price = 0
max_profit = 0
for i in range(1, len(prices)):
max_profit = max(max_profit, prices[i] - prices[min_price])
if prices[min_price] > prices[i]:
min_price = i
return max_profits
13
Q
Longest Substring Without Repeating Characters.
Given a string s, find the length of the longest substring without repeating characters.
A
sliding window with 2 pointers.
you want to start with 2 pointers that start at the beginning of the list and as you increment the right pointer see if the new element is there in your window (use a set for this) and if its there, pop your left pointer value from set and increment you left pointer until you can add right and still have all unique elements. this should give you max_len.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
unique_set = set()
start = 0
end = 0
max_len = 0
while end < len(s):
if s[end] not in unique_set:
unique_set.add(s[end])
end += 1
else:
unique_set.remove(s[start])
start += 1
max_len = max(max_len, len(unique_set))
return max_len
14
Q
Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
A
The main challenge here is that you not only need to use a sliding window (as you’re looking to analyse consecutive elements) to keep track of the substring but you also need to make sure that window is valid wrt the condition that if you replace k characters in the window it’ll have only 1 character.
main ideas:
1. keep track of window with dictionary and count variable for number of elements in it.
2. remember that the condition for validity is count - max(dict.values) <= k.
you push the element at hi into the window and check for validity. if valid you update max_window else you reduce window length
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
lo, hi = 0, 0
hmap = {}
# window = 1
max_window = 0
while hi < len(s):
hmap[s[hi]] = hmap.get(s[hi], 0) + 1
if hi-lo+1 - max(hmap.values()) <= k:
max_window = max(max_window, hi-lo+1)
else:
hmap[s[lo]] -= 1
lo += 1
hi += 1
return max_window
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
lo, hi = 0, 0
hmap = {}
max_window = 0
while hi < len(s):
hmap[s[hi]] = hmap.get(s[hi], 0) + 1
while hi-lo+1 - max(hmap.values()) > k:
hmap[s[lo]] -= 1
lo += 1
max_window = max(max_window, hi-lo+1)
hi += 1
return max_window
15
Q
Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
A
slide through the string with 2 pointers, keep checking for a valid window by putting elements into a dictionary and checking if the dictionary has required elements. if invalid: increase the right pointer to make the window bigger, if valid: increase the left pointer to decrease the window size as we want smallest array.
main ideas:
1. checking sliding window validity and increasing and decreasing size based on it so as to get smallest match. Here you have to be careful about while condition as you loop to find window. have a look at the solution while and if conditions below.
- neetcode video has a more optimum solution where when you check for validity only care about characters in target string and keep a global match count which you can look at and update to check for match instead of iterating through the keys in the dictionary every time .
class Solution:
def isSubset(self, s_map, t_map):
for key, value in t_map.items():
if key not in s_map or s_map[key] < value:
return False
return True
def minWindow(self, s: str, t: str) -> str:
if len(s)<len(t):
return ""
t_map = {}
for char in t:
t_map[char] = t_map.get(char, 0) + 1
l, r = 0, 0
mws = ""
s_map = {}
while l <= r:
if self.isSubset(s_map, t_map):
mws = s[l:r] if len(mws)==0 else mws
if len(mws) > r-l-1:
mws = s[l:r]
s_map[s[l]] -= 1
l+=1
else:
if r == len(s):
break
s_map[s[r]] = s_map.get(s[r], 0) + 1
r += 1
return mws
16
Q
Valid Parentheses
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.
A
Use a stack. Can use a dictionary to keep track of close to open relations.
push all opening braces into stack and when you get a closing brace the last element in stack should be the corresponding closing which you pop.
Code:
def isValid(self, s: str) -> bool:
stack = []
ele_map = {'{':'}', '[':']', '(':')'}
for ele in s:
if ele in ele_map:
stack.append(ele)
elif len(stack) and ele_map[stack[-1]] == ele : \\ here order of logical boolean evaluation matters!!
stack.pop()
else:
return False
return not len(stack)
17
Q
Find Minimum in Rotated Sorted Array
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.
A
if right half is sorted minimum won’t be there except maybe the first element
Simple condition which is to check if mid is less than hi if so right half is the sorted half. so move hi to mid as that could be the minimum. else left half is sorted lo = mid+1 as minimum can’t be the last element of sorted element
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)-1
while lo<hi:
mid = (lo+hi)//2
if nums[mid] < nums[hi]:
hi = mid #if left half is sorted lo = mid+1 as minimum can't be the last element on sorted first half
else: #nums[mid] > nums[lo]
lo = mid + 1
return nums[hi]
18
Q
Search in Rotated Sorted Array
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.
A
Finding pivot and then doing binary search is too complex.
Instead the thing to do is find in one loop:
there are 3 possible cases after comparing target with nums[mid]:
Case 1. If nums[mid] = target,
Case 2. If nums[mid] >= nums[left]. It implies that the left subarray nums[left ~ mid] is sorted. We can determine whether to proceed with this subarray by comparing target with the boundary elements:
If nums[left] <= target and target < nums[mid], it suggests that the sorted left half might include target while the other half does not contain target. Consequently, we focus on the left half for further steps.
Otherwise, the left half is guaranteed not to contain target, and we will move on to the right half.
Case 3. If nums[mid] < nums[left], it implies that the left subarray is rotated and the right subarray nums[mid ~ right] is sorted. Therefore, we can determine whether to proceed with the right subarray by comparing the target with its boundary elements:
If nums[mid] < target and target < nums[right], it implies that the sorted right half might contain target. As a result, we will move on with the right half.
Otherwise, the right half is guaranteed not to contain target, and we will move on to the left half.
this makes the solution a lot easier, go through the code
def search(self, nums: List[int], target: int) -> int:
#first find index of sorted portion with target in it
lo, hi = 0, len(nums) - 1
while lo<=hi:
mid = (lo+hi)//2
# print(lo, hi, mid)
if nums[mid] == target:
return mid
elif nums[mid] < nums[hi]:
if target > nums[mid] and target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
else:
if target < nums[mid] and target >= nums[lo]:
hi = mid - 1
else:
lo = mid + 1
return -1
19
Q
Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
A
take 2 variable and go through with a while loop and swap pointers around.
the recursive way to do it is a lil involved and non intuitive you have to one see that you have to send the end of the list in the return of the recursive call so it needs to travel back and as its being sent back you need to point node.next.next = node to reverse a link and then put node.next = None mostly to put first element in linked list to None when returning. There’s a video in the leetcode solution top comments thats very good. https://youtu.be/S92RuTtt9EE
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if (not head) or (not head.next):
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
20
Q
Merge Two Sorted linked Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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.
A
create a tail and dummy, dummy for result and tail to keep track of where you are in the combined list
decide which has the smaller start and calling that the start. then keep adding to it depending on who is smaller through a loop. append whatever is leftover and return.
look at code its non-trivial to code this up
def merge2(self, head1, head2):
tail = ListNode()
dummy = tail
while head1 and head2:
if head1.val<head2.val:
tail.next = head1
head1 = head1.next
else:
tail.next = head2
head2 = head2.next
tail = tail.next
tail.next = head2 if head2 else head1
return dummy.next
21
Q
Reorder List
You are given the head of a singly linked list. The list can be represented as follows:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
A
Though not necessary for a valid solution, it introduces the concept of a slow and fast pointer.
Easy: use a list to store elements and then just pointer manipulation. this is O(n) time and O(n) space.
O(1) space solution: this has 3 parts one is finding end and mid of the linkedlist using a fast and slow pointer. Second is reversing the second half of the linked list. Third is merging the 2 halves.
22
Q
Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
A
use concept of 2 pointers seperated by n nodes.
so you start with a dummy node and a left pointer pointing to it. then you send another right pointer ahead of dummy by n nodes. then you push out both pointers till right pointer reaches end of the linked list. At this point left pointer is pointing at node that needs to be modified to remove nth node from linked list. it’s important to think about dummy node as else you mess up edge cases.
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
l = dummy
r = head
for _ in range(n-1):
r = r.next
while r.next:
r = r.next
l = l.next
l.next = l.next.next
return dummy.next
23
Q
Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
A
simple solution is to use set but that’s o(n) space.
better to use floyd’s algorithm ie use fast and slow pointer and know that they will intersect in the loop. floyd’s algo is from the find the looping element question.
For this question all you need to do is start and slow and fast pointer if they meet there’s a loop if fast reaches a None there’s no loop.
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
24
Q
Merge k Sorted Lists
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.
A
intuitive solution of going double looping to go through every starting element of each of the lists to pick up the smallest and adding that to solution one by one works.
1. need to keep track of index to remove the right element.
2. need to handle some edge cases of empty lists in input.
But this is O(n*k) time, there’s a better O(nlogk) solution where the main idea is you merge in pairs of 2 cutting down the number of merges to logk time
Look at code its non trivial to code this up
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists: # Check if the list is empty or all elements are None
return None
while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
list1 = lists[i]
list2 = lists[i+1] if i+1 < len(lists) else None
mergedLists.append(self.merge2(list1, list2))
lists = mergedLists # Update lists to be the merged lists for the next iteration
return lists[0] # After merging, the final merged list is the first element
def merge2(self, head1, head2):
tail = ListNode()
dummy = tail
while head1 and head2:
if head1.val<head2.val:
tail.next = head1
head1 = head1.next
else:
tail.next = head2
head2 = head2.next
tail = tail.next
tail.next = head2 if head2 else head1
return dummy.next
25
Invert Binary Tree
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]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
simple recursive call will do use the same function as the solution definition. base case is if root is None
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.left = right
root.right = left
return root
iterative solution uses queue:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return root
Try iterative dfs
26
Maximum Depth of Binary Tree
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.
-----what is the data structure to do iterative BFS and iterative DFS? how do you do pop and push in each?
simple recursive solution.
base case is if root is None.
add one every recursive step. return max of recursive returns from left and right.
can be done with iterative DFS and iterative BFS using a deque data structure in python.
DFS = stack
BFS = queue
q= collections.deque()
q.append()
q.pop()
q.popleft()
#recursive
if root== None:
return 0
max_d = 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
return max_d
# # BFS:
# if not root: return 0
# q = deque()
# q.append(root)
# depth = 0
# while q:
# for i in range(len(q)):
# ele = q.popleft()
# if ele:
# q.append(ele.left)
# q.append(ele.right)
# depth += 1
# return depth-1
# # DFS
# if not root: return 0
# stack = [[root, 1]]
# maxd = 1
# while len(stack):
# node, depth = stack.pop()
# if node:
# stack.append([node.right, depth+1])
# stack.append([node.left, depth+1])
# maxd = max(maxd, depth)
# # return maxd-1
27
Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
recursive solution. keep checking if val is the same for both by iterating through the tree the same way
can also use stack here:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
#DFS
p_stack = [p]
q_stack = [q]
while p_stack and q_stack:
p_node = p_stack.pop()
q_node = q_stack.pop()
if p_node== None and q_node == None:
continue
elif p_node == None or q_node == None:
return False
elif p_node.val != q_node.val:
return False
p_stack.append(p_node.left)
p_stack.append(p_node.right)
q_stack.append(q_node.left)
q_stack.append(q_node.right)
return True
28
Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
iteratively go to every node in the tree and check if the tree with that node as root is the same as the subRoot tree.
checking if 2 trees are the same can also be done recursively.
```
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSame(root1, root2):
if root1 == None and root2 == None:
return True
elif root1 == None or root2 == None:
return False
if root1.val == root2.val:
return isSame(root1.left, root2.left) and isSame(root1.right, root2.right)
else:
return False
return isSame(root, subRoot)\
or (self.isSubtree(root.left, subRoot) if root.left else False) \
or (self.isSubtree(root.right, subRoot) if root.right else False)
```
29
Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left
subtree
of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
can be solved recursively by checking if tree from a given node is valid.
But main idea here is that we don't check from bottom to top we check from top to bottom by passing the min and max restrictions of that node which it inherits from its parents.
Right node will inherit parents max restriction and will have a min restriction parents value. Similarly left child will inherit the parents min restriction and will have a max restriction of parents value.
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValid(root, pmin, pmax):
if root == None:
return True
return root.val>pmin and root.val
30
Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
main idea is you gotta work from the bottom to the top of the tree. You return up both the max child height and diameter from every node.
the max child height is max of left and right child height plus 1 and diameter is max of right, left diameter and the right height plus left height.
31
Balanced Binary Tree
Given a binary tree, determine if it is
height-balanced
.
write a recursive function to which returns both the height from a node and whether the tree from that node is balanced.
the base case is height is 0 and true for balance validity.
the update rule is height is 1+ max of left and right height, its valid if both right and left are valid and height condition is met (difference is less than or equal to 1)
32
Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
tree = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
---- what data structure do you use and how?
you have to use a queue but since you want all elements in one level to be put in a list separately you have to use a for loop to pop all the elements in the queue at one time and then append all their children together for the next iteration and you wrap this for loop in a while loop which continues till queue is empty.
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
q = collections.deque()
if root:
q.append(root)
while q:
val = []
for i in range(len(q)):
node = q.popleft()
val.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(val)
return res
33
LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
# obj = LRUCache(capacity)
There is simpler code but using double linked list is best. Create a ListNode and in LRUCache class you need init, get, put, add add and remove
```
class ListNode:
def __init__(self, key= -10, val = -10, next1 = None, prev = None):
self.val = val
self.key = key
self.next = next1
self.prev = prev
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.knmap = {}
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.knmap:
self.remove(key)
self.add(key)
return self.knmap[key].val
else:
return -1
def put(self, key: int, value: int) -> None:
if key not in self.knmap.keys():
self.knmap[key] = ListNode(key, value)
else:
self.remove(key)
node = self.knmap[key]
node.val = value
self.add(key)
while len(self.knmap) > self.capacity:
del_key = self.tail.prev.key
self.remove(del_key)
del self.knmap[del_key]
def add(self, key):
node = self.knmap[key]
node.next = self.head.next
node.prev = self.head
node.next.prev = node
self.head.next = node
def remove(self, key):
node = self.knmap[key]
node.prev.next = node.next
node.next.prev = node.prev
Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
```
Your LRUCache object will be instantiated and called as such:
```
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
```
if you use a queue to keep track of gets and a dictionary to count the occurrence of key in queue and a dictionary to hold key value pairs then this is a lot simpler to implement than with doubly linked lists
class LRUCache:
def __init__(self, capacity: int):
self.cacheq = deque()
self.count_hash = {}
self.kv = {}
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.kv:
return -1
else:
self.put(key, self.kv[key])
return self.kv[key]
def put(self, key: int, value: int) -> None:
self.kv[key] = value
self.count_hash[key] = self.count_hash.get(key, 0) + 1
self.cacheq.appendleft(key)
while len(self.kv) > self.capacity:
key = self.cacheq.pop()
self.count_hash[key] -= 1
if self.count_hash[key] == 0:
del self.kv[key]
34
Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
----- make sure you have code in mind
This is basically making a list of the rightmost element at every level and returning it.
main challenge is how to do level order traversal or BFS. this is done using a queue and a for loop inside a while loop.
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
#do level order traversal and only append the last element
if not root:
return []
q = deque()
q.append(root)
sol = []
while q:
level = []
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level.append(node.val)
sol.append(level[-1])
return sol
35
Count Good Nodes in Binary Tree
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Need to do recursive calls and pass down the condition which is the max node seen up to this point on the way down the recursion. A lot like checking whether a BST is valid.
Add code!!
36
Lowest Common Ancestor of a Binary search tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
# class TreeNode:
bst is ordered which means everything on left of a node is always smaller and everything on right of a node is larger so you can leverage this to get an easy solution like below:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if (p.val < root.val) and (q.val < root.val):
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
37
Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
need to do dfs and return the kth element from top of stack since its a bst.
can be done iterative or recursively:
iterative:
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.right
recursive:
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# recursive dfs
self.k = k
self.result = None
self.dfs(root)
return self.result
def dfs(self, root):
if root.left and self.k>0:
self.dfs(root.left)
self.k-=1
if self.k == 0:
self.result = root.val
elif self.k<0:
return
if root.right and self.k>0:
self.dfs(root.right)
38
Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
classic dfs across grid problem. for loop through the node and when you get to an island if not visited already call dfs on it which will give you area of that island recursively. The recursive function checks for validity and makes sure the place we're at in grid is land and then adds up area and returns it.
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visit = set()
def dfs(r, c):
if (
r < 0
or r == ROWS
or c < 0
or c == COLS
or grid[r][c] == 0
or (r, c) in visit
):
return 0
visit.add((r, c))
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
area = 0
for r in range(ROWS):
for c in range(COLS):
area = max(area, dfs(r, c))
return area
--------------Another solution----------------------------------------------------------------
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
max_area = 0
visited = set()
directions = [(1,0), (0,1), (0,-1), (-1,0)]
nrows, ncols = len(grid), len(grid[0])
#iterative dfs
def dfs(row, col):
stack = [(row, col)]
area = 1
while stack:
r, c = stack.pop()
for dr, dc in directions:
r2, c2 = r+dr, c+dc
if r2>=0 and c2>=0 and r2=0 and c2>=0 and r2=0 and c1>=0 and r1
Complete code
39
Construct Binary Tree from Preorder and Inorder Traversal
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
preorder[0] has the first element and inorder tells you which elements are in which half. With this info you can recursively build the tree.
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
return root
40
Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
need to do iterate through every element in grid using a for loop and at every point where grid has a 1 you need to call a dfs/iterative bfs/iterative dfs to go mark as visited every piece of land around it as valid. So for this you need to maintain a hashset into which you add visited elements.
The number of times you get to uniquely do this is the count of islands.
def numIslands(self, grid: List[List[str]]) -> int:
nrows, ncols = len(grid), len(grid[0])
num_islands = 0
visited = set()
directions = [[1, 0], [0,1], [0,-1], [-1, 0]]
#recursive dfs
def dfs(row, col):
for dr, dc in directions:
r, c = row+dr, col+dc
if ((r, c) not in visited) and r=0 and c>=0:
visited.add((r, c))
if grid[r][c] == "1":
dfs(r, c)
#iterative dfs
def dfs_i(row, col):
stack = [(row, col)]
while stack:
r, c = stack.pop()
for dr, dc in directions:
r1, c1 = r+dr, c+dc
if r1>=0 and c1>=0 and r1=0 and c1>=0 and r1=0 and c1>=0 and r1
41
Clone Graph
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
You need to recursively create a copy of the entire graph but to avoid remaking node's you've already created you keep a dictionary oldToNew that has key as old Node and value as NewNode. if in your recursion an old node that is there in the dict needs to be created you simply use the one you already have.
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
self.d = {}
return self.cloneGraph_rec(node) if node else None
def cloneGraph_rec(self, node):
if node not in self.d:
new_node = Node(node.val)
self.d[node] = new_node
else:
new_node = self.d[node]
for neighbor in node.neighbors:
if neighbor not in new_node.neighbors:
if neighbor in self.d:
new_node.neighbors.append(self.d[neighbor])
else:
new_node.neighbors.append(self.cloneGraph_rec(neighbor))
return new_node
#neetcode solution
def cloneGraph(self, node: "Node") -> "Node":
oldToNew = {}
def dfs(node):
if node in oldToNew:
return oldToNew[node]
copy = Node(node.val)
oldToNew[node] = copy
for nei in node.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node) if node else None
#iterative solution
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node == None: return None
node_map = {}
new_n = Node(val = node.val, neighbors = None)
node_map[node] = new_n
stack = [node]
while stack:
n = stack.pop()
for neighbor in n.neighbors:
if neighbor not in node_map:
stack.append(neighbor)
new_nei = Node(val = neighbor.val, neighbors = None)
node_map[neighbor] = new_nei
node_map[n].neighbors.append(node_map[neighbor])
return node_map[node]
42
Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Trick here to realise that instead of thinking what cells can reach both the oceans you gotta think what cells can be reached by both the oceans.
Keep track of the cells that can be reached using sets and do the usual dfs funda here.
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prevHeight):
if (
(r, c) in visit
or r < 0
or c < 0
or r == ROWS
or c == COLS
or heights[r][c] < prevHeight
):
return
visit.add((r, c))
dfs(r + 1, c, visit, heights[r][c])
dfs(r - 1, c, visit, heights[r][c])
dfs(r, c + 1, visit, heights[r][c])
dfs(r, c - 1, visit, heights[r][c])
for c in range(COLS):
dfs(0, c, pac, heights[0][c])
dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
for r in range(ROWS):
dfs(r, 0, pac, heights[r][0])
dfs(r, COLS - 1, atl, heights[r][COLS - 1])
res = []
for r in range(ROWS):
for c in range(COLS):
if (r, c) in pac and (r, c) in atl:
res.append([r, c])
return res
43
Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
trick here is to figure out you need to do bfs from the rotten oranges to the fresh ones counting the number of levels it takes to turn all fresh to rotten. You need to run a initial double for loop to count the number of fresh and figure out where the rotten are from where you'll start bfs.
```
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
nrows, ncols = len(grid), len(grid[0])
rotten = deque()
nfresh = 0
for r in range(nrows):
for c in range(ncols):
if grid[r][c] == 2:
rotten.append((r,c))
elif grid[r][c] == 1:
nfresh += 1
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
minutes = 0
while rotten and nfresh:
minutes += 1
k = len(rotten)
for _ in range(k):
r1, c1 = rotten.pop()
for dr, dc in dirs:
r2, c2 = r1+dr, c1+dc
if r2>=0 and c2>=0 and r2
44
Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
can be solved with classic dp technique. base case is when you are at step == n, then you return 1. Which means if a series of choices bring you to step == n then that is a possible way.
if step>n then you return 0. if step is anything less you return dp(step+1) + dp(step+2)
45
Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
can be solved with classic dp technique. base case is when you are at step == n, then you return 1. Which means if a series of choices bring you to step == n then that is a possible way.
if step>n then you return 0. if step is anything less you return dp(step+1) + dp(step+2)
46
Min Cost Climbing Stairs
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
you can use classic dp techniques, since the goal is to minimise cost you return the cost of a step plus minimum of cost from taking the possible actions. base case is returning 0 when you end up on step n and returning inf when you overshoot which is an invalid state.
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
@lru_cache(None)
def dp(step):
if step == len(cost):
return 0
if step > len(cost):
return inf
return cost[step] + min(dp(step+1), dp(step+2))
return min(dp(0), dp(1))
47
House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
classic dp problem. What you gotta realise here is the robber at a state can rob a house and then rob the hour skipping one or skipping two. it skips one at least to avoid the cops and it skips 2 to be able to rob the house 2 over which might be a big hit.
your base case is zero if you reach house index n or greater and you start from house 0 or house 1. so you return max of these
```
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)<=2:
return max(nums)
@lru_cache(None)
def dp(i):
if i>=len(nums):
return 0
return max(nums[i]+dp(i+2), dp(i+1))
return dp(0)
```
48
House Robber II
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
```
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)<=2:
return max(nums)
@lru_cache(None)
def dp(i, nlen):
if i>=nlen:
return 0
return max(nums[i]+dp(i+2, nlen), dp(i+1, nlen))
return max(dp(1, len(nums)), dp(0, len(nums)-1))
```
49
Longest Palindromic Substring
Given a string s, return the longest
palindromic substring in s.
you iterate through the string and at each point envision the start of a palindrome of even and odd length. if even length then take 2 elements and see if you can expand outwards. if odd length take a middle element and see if you can expand outwards. Store the max length palindrome.
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
resLen = 0
for i in range(len(s)):
# odd length
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
if (r - l + 1) > resLen:
res = s[l : r + 1]
resLen = r - l + 1
l -= 1
r += 1
# even length
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if (r - l + 1) > resLen:
res = s[l : r + 1]
resLen = r - l + 1
l -= 1
r += 1
return res
50
Decode Ways
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
dp thinking; in a valid state you can have a 1 or a 2 followed by 0-6 in which case you can call dp on index +1 and index + 2. otherwise you only call on index+1. if you have a 0 at index then you return 0.
base case is when index is len(s) or greater in which case you return 1 since it's counting number of ways.
when you convert to iterative with 2 variables only make sure to set curr to 0 after every loop
```
class Solution:
def numDecodings(self, s: str) -> int:
@lru_cache(None)
def dp(i):
if i == len(s):
return 1
single = int(s[i])
double = int(s[i:i+2])
if single == 0:
return 0
result = 0
if single>0 and single<=9:
result += dp(i+1)
if double>9 and int(s[i:i+2])<=26:
result += dp(i+2)
return result
return dp(0)
```
```
class Solution:
def numDecodings(self, s: str) -> int:
dp = [0 for _ in range(len(s)+1)]
dp[len(s)] = 1
for i in reversed(range(len(s))):
single = int(s[i])
if single == 0:
dp[i] = 0
continue
result = 0
if single>0 and single<=9:
result += dp[i+1]
double = int(s[i:i+2])
if double>9 and double<=26:
result += dp[i+2]
dp[i] = result
return dp[0]
```
51
Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
classic dp problem where base case is that to get an amount of 0 you need 0 coins. and if amount is greater than 0 you iterate through all the coins and recursively call to see how many coins it would take to get to amount - coin_value.
A good trick to remember in the recursive is to set result to amount +1 this let's you avoid using float('inf').
when you write an iterative solution for this you go forward in the loop and not backward in the loop.
basic logic is that we need to go through all possibilities of taking any element from coins from amount at each stage of the tree. because of lru_cache this is possible. of all possible combinations you count the ones that give an amount of 0 eventually
recursive:
def coinChange(self, coins: List[int], amount: int) -> int:
@lru_cache(None)
def dp(am):
if am == 0:
return 0
result = amount + 1
for coin in coins:
if am - coin >=0:
result = min(result, 1 + dp(am-coin))
return result
return dp(amount) if dp(amount) < amount + 1 else -1
iterative:
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [inf]*(amount+1)
# @lru_cache(None)
# def dp(amount):
dp[0] = 0
for am in range(1, amount+1):
min_num_coins = inf
for coin in coins:
if am >= coin:
num_coins = 1 + dp[am-coin]
min_num_coins = min(min_num_coins, num_coins)
dp[am] = min_num_coins
return dp[amount] if dp[amount] != inf else -1
52
Maximum Product Subarray
Given an integer array nums, find a
subarray
that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
this is a dp approach. since the more elements you have the greater the product will be (all pos or even negative) you can dp with pointer to start of array then as you keep growing keep multiplying with elements and keeping track of the min and the max. the min and max could also be the element itself. then return the max you got of all the max's .
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = nums[0]
maxnum, minnum = nums[0], nums[0]
for num in nums[1:]:
tmp = max(maxnum * num, minnum * num, num)
minnum = min(maxnum * num, minnum * num, num)
maxnum = tmp
res = max(res, maxnum)
return res
53
Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
You should be able to do it one double loop by using modulo operator to reference sets in a 2D list.
The code is otherwise pretty simple traverse the 2D list and intelligently do column and row reading. and then box reading using modulo operator
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
box_sets = [[set() for _ in range(3)] for _ in range(3)]
for i in range(9):
row_set = set()
col_set = set()
for j in range(9):
row_ele = board[i][j]
col_ele = board[j][i]
box_ele = board[i][j]
if row_ele != ".":
row_ele = int(row_ele)
if 0
54
Random Pick with Weight
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
Example 1:
Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
You calculate cumulative weight and then you generate a random number between 0 and maximum of cumulative weights. Then you do binary search to find where the random generated number falls in the cum dist list and that's your answer
Be sure to notice how bisection or binary search is implemented try to remember that pattern
def __init__(self, w: List[int]):
self.cum_weights = [0 for _ in range(len(w))]
self.weights = w
for i in range(len(w)):
self.cum_weights[i] = self.cum_weights[i-1] + w[i]
def pickIndex(self) -> int:
pick = random.random() * self.cum_weights[-1]
l, r = 0, len(self.cum_weights)-1
while l < r:
mid = (l + r) // 2
if self.cum_weights[mid] == pick:
return mid
elif self.cum_weights[mid] < pick:
l = mid + 1
else:
r = mid
return l
55
Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Example 2:Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7
Need to create a stack out of the linked lists so that you can do addition from the back like addition in school.
How carry is calculated is a point of mistake sometimes
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
st1 = []
st2 = []
while l1 != None:
st1.append(l1.val)
l1 = l1.next
while l2 != None:
st2.append(l2.val)
l2 = l2.next
carry = 0
head = None
while st1 or st2 or carry:
dig1 = st1.pop() if st1 else 0
dig2 = st2.pop() if st2 else 0
head = ListNode((dig1+dig2+carry)%10, head)
carry = (dig1+dig2+carry)//10
return head
56
Evaluate Reverse Polish Notation
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.
Example 1:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Main thing to remember in this question is how to do division towards 0. a/b towards 0 = (a+(-a%b))//b if a*b<0 else a//b. You take away remainder from a to make it divisible by b and then divide if a or b are negative as division in python is to floor.
int(a/b) rounds to 0 :|
otherwise the code is a simple push into stack and when you hit operator pop last 2 elements and do operation:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for ele in tokens:
if ele == '+':
stack.append(int(stack.pop())+int(stack.pop()))
elif ele == '-':
stack.append(-int(stack.pop())+int(stack.pop()))
elif ele == '*':
stack.append(int(stack.pop())*int(stack.pop()))
elif ele == '/':
b = int(stack.pop())
a = int(stack.pop())
stack.append(a//b if a*b>0 else (a+(-a%b))//b)
else:
stack.append(ele)
return int(stack[0])
57
Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
Remember you can use a stack outside rec call save add to result.
Write a recursive function to which you pass number of open parenthesis and number of closed parenthesis. In the recursive function you can add closed and open parenthesis based on conditions of it being possible to add open parenthesis and if the number of closed parenthesis is fewer in stack than open parenthesis or the number of closed parenthesis we have to append is more than the open parenthesis (any configuration in which we put open parenthesis before corresponding close parenthesis is valid, so as long as you add closed parenthesis after open parenthesis your stack at end is valid).
Need to remember in this and many backtracking to pop after pushing and to maintain a stack
One thing to note here in how you write code is that if you define the function inside the other function you can low space complexity as you don't need to pass the variable along you can call it in the function as the variables will be in scope.
def generateParenthesis(self, n: int) -> List[str]:
result = []
stack = []
def recursive(num_open, num_close):
if num_open == 0 and num_close == 0:
return result.append("".join(stack))
if num_open > 0:
stack.append('(')
recursive(num_open-1, num_close)
stack.pop()
if num_close > num_open:
stack.append(')')
recursive(num_open, num_close-1)
stack.pop()
recursive(n, n)
return result
58
Subsets
Given an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.
Backtracking. at each level in the backtracking tree you choose whether to add an element or not add an element and in this way will end up with unique and required results at the leaves of the tree.
def subsets(self, nums: List[int]) -> List[List[int]]:
#backtracking with either add an element or don't add being branch decision at every level
res = []
subset = []
def dfs(i):
if i == len(nums):
res.append(subset.copy())
return
subset.append(nums[i])
dfs(i+1)
subset.pop()
dfs(i+1)
dfs(0)
return res
59
Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40
its backtracking with at every level you pick one element but since we can repeat elements instead of being able to pick one element from parent list you keep a pointer and you take a decision to either pick from elements after or from already picked element to element after.
at every node in decision tree you decide to either pick element at index i or not. if you pick element at index i on left side of tree you can again pick i or not pick i. On left side where you don't pick i you decide whether to pick i+1 or not pick i+1. This way left end leaf will be first element always picked and right end leaf will be no elements picked
This prob is good to redo
```
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
comb = []
def bt(i, tar):
if tar == 0:
result.append(comb[:])
return
if tar<0 or i>=len(candidates):
return
comb.append(candidates[i])
bt(i, tar-candidates[i])
comb.pop()
bt(i+1, tar)
return
bt(0, target)
return result
```
60
Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
The main insight here is that you know you have to go through all the elements in the array, like in recursive case is you permute a subarray and then append an element to the end. So you can pop from the front and append at the back and if you do this in a for loop you can go through the array and as you pop and append you're taking one element off permuting the rest and then appending it and getting total permutations in a recursive way
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
if len(nums) == 1:
return [nums[:]]
for _ in range(len(nums)):
n = nums.pop(0)
res += [[n] + ele for ele in self.permute(nums)]
nums.append(n)
return res
61
Subsets II
Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
This is like subsets 1 but with duplicates. If duplicates weren't present you would have a pointer at nums be argument to recursive function and then you would have 2 chioces of whether to include the element in subset or not include. Here since there are elements we sort the input array first and if we choose to not include an element we must also not include repetitions of the element. so in the case where we pop and call backtrack(i+1) we should do so after incrementing i to the last repetition of nums[i] basically increment i if nums[i] == nums[i+1] till this doesn't hold true.
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
unique = set()
nums.sort()
def dfs(i):
if i == len(nums):
res.append(subset[::])
return
subset.append(nums[i])
dfs(i+1)
subset.pop()
while i+1 < len(nums) and nums[i] == nums[i+1]: i+=1
dfs(i+1)
dfs(0)
return res
62
Surrounded Regions
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.
Example 2:
Input: board = [["X"]]
Output: [["X"]]
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.
In the problem hint its mentioned but also it should be clear that if you're connected to a O on the edge then you're ok, other all O's get replaced. So you traverse the edges of matrix and then do dfs at Os to find connected Os to save. rest get replaced with O
63
Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Constraints:
1 <= m, n <= 100
Simple 2 D dynamic programming. if a path reaches target return 1 and add all possibilities up.
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in reversed(range(m)):
for j in reversed(range(n)):
if i == m-1 and j == n-1:
dp[i][j] = 1
if i+1
64
Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.
its a dp problem where you start with 2 pointers at beginning of both strings and then if both characters are equal you increment and find MCS of new strings starting from there or you take max of MCS of strings incrementing both pointers one by one:
if text1[i] == text2[j]:
return 1+dp(i+1, j+1)
else:
return max(dp(i+1, j), dp(i, j+1))
can think of dp table formed here.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
@lru_cache(None)
def dp(i, j):
if i >= len(text1) or j >= len(text2):
return 0
if text1[i] == text2[j]:
return 1+dp(i+1, j+1)
else:
return max(dp(i+1, j), dp(i, j+1))
return dp(0,0)
65
Best Time to Buy and Sell Stock with Cooldown
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]
Output: 0
Constraints:
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
Dp problem which can be solved easily with memoization or with if we're at a state depending on whether we've bought or sold we can make decisions and work our way up the call stack
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@lru_cache(None)
def dp(i, bought, cooldown):
# reached end of list, sell if bought or do nothing
if i == len(prices) - 1:
return prices[-1] if bought else 0
#if already bought then can sell or can just wait
elif bought:
return max(prices[i]+dp(i+1, False, True), dp(i+1, True, False))
else:
# if not bought and in cooldown then wait for a round
if cooldown:
return dp(i+1, False, False)
# if not bought and not cooldown then can buy or just pass
return max(-prices[i]+dp(i+1, True, False), dp(i+1, False, False))
return dp(0, False, False)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# State: Buying or Selling?
# If Buy -> i + 1
# If Sell -> i + 2
dp = {} # key=(i, buying) val=max_profit
def dfs(i, buying):
if i >= len(prices):
return 0
if (i, buying) in dp:
return dp[(i, buying)]
cooldown = dfs(i + 1, buying)
if buying:
buy = dfs(i + 1, not buying) - prices[i]
dp[(i, buying)] = max(buy, cooldown)
else:
sell = dfs(i + 2, not buying) + prices[i]
dp[(i, buying)] = max(sell, cooldown)
return dp[(i, buying)]
return dfs(0, True)
66
Implement Trie (Prefix Tree)
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Constraints:
1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search, and startsWith.
you implement a trie by having a node which holds alphabets as children. you can have atmost 26 children. and each node also has a isEndOfWord boolean which denoted end of word if true.
class TrieNode:
def __init__(self, children = {}, isEndOfWord = False):
self.children = {}
self.isEndOfWord = False
class Trie:
def __init__(self):
self.parentNode = TrieNode()
def insert(self, word: str) -> None:
node = self.parentNode
for i in range(len(word)):
if word[i] not in node.children:
node.children[word[i]] = TrieNode()
node = node.children[word[i]]
if i == len(word) - 1:
node.isEndOfWord = True
def search(self, word: str) -> bool:
node = self.parentNode
for i in range(len(word)):
if word[i] in node.children:
node = node.children[word[i]]
if i == len(word) - 1 and node.isEndOfWord == True:
return True
else:
return False
return False
def startsWith(self, prefix: str) -> bool:
node = self.parentNode
for i in range(len(prefix)):
if prefix[i] in node.children:
node = node.children[prefix[i]]
else:
return False
return True
Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
67
Maximum Subarray
Given an integer array nums, find the
subarray
with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Main logic here is since you are finding a subarray, you traverse through the list but when you get to a new element it makes sense to keep the sum of numbers behind it only if it is greater than 0. Another way to think of this is you can take max(nums[r], nums[r]+running_sum).
The solution is super simple if you think in this manner.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_result = nums[0]
result = nums[0]
for r in range(1, len(nums)):
result = max(result+nums[r], nums[r])
max_result = max(result, max_result)
return max_result
68
Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board?
Solution called backtracking but basically the general graph approach works here. use that to see if pattern can be reached in a dfs manner. Main thing is to notice here that's different is that we need to remove from the visited set when we're leaving the dfs so that the character can be used in another traversal.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
nrows, ncols = len(board), len(board[0])
dirs = [(1, 0), (0, 1), (0, -1), (-1, 0)]
visited = set()
def dfs(r, c, word_ind):
visited.add((r, c))
if word_ind == len(word):
return True
found = False
for dr, dc in dirs:
row , col = r+dr, c+dc
if row>=0 and row= 0 and col < ncols and (row, col) not in visited and board[row][col] == word[word_ind]:
found = found or dfs(row, col, word_ind+1)
visited.remove((r, c))
return found
result = False
for i in range(nrows):
for j in range(ncols):
if board[i][j] == word[0]:
visited = set()
result = result or dfs(i, j, 1)
return result
69
Graph Valid Tree
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
Example 1:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Constraints:
1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no self-loops or repeated edges.
Main thing to note here is that a valid tree has n-1 number of edges if it has n nodes. This greatly helps in making the solution easy. this means you don't have to check for loops this condition does it for you. After this you just need to write a iterative dfs to check if every node is reachable from every node. To do this you enter the graph from one node and make sure you can reach every other node. It’s important to do this.
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1: return False
# Create an adjacency list.
adj_list = [[] for _ in range(n)]
for A, B in edges:
adj_list[A].append(B)
adj_list[B].append(A)
# We still need a seen set to prevent our code from infinite
# looping if there *is* cycles (and on the trivial cycles!)
seen = {0}
stack = [0]
while stack:
node = stack.pop()
for neighbour in adj_list[node]:
if neighbour in seen:
continue
seen.add(neighbour)
stack.append(neighbour)
return len(seen) == n
70
what are the python heap functions? what kind of heap is there in python?
what lib do you need to import? how do you pop from a heap? how do you push to heap?
import heapq
heapq is min heap by default.
heapq.heappop(array) -> pop element from min heap
heapq.heappush(array, element)
to implement max heap with heapq just take negative of all values
H = [1,2,3]
heapq.heapify(H)
71
How do you make binary search updates?
If isReachable(mid) returns true, then we know that the building at mid is reachable. We're no longer interested in any of the buildings before mid, as they can’t possibly be the final-reachable-building (as mid is further than them).
We don't know whether or not the building at mid + 1 is reachable, though, and nor should we check right now.
***** Remembering that lo and hi represent the boundaries of where the final-reachable-building could be, we should set lo = mid. This means that the building at mid is now the lowest building in the search range. ******
Which calculation for mid should we use?
On an odd-lengthed search space, identifying the midpoint is straightforward. On even-lengthed search spaces, though, we have two possible midpoints. The final step of the binary search algorithm design process is to decide whether it is the lower or higher midpoint that should be used.
Your decision should be based on how you are updating hi and lo (i.e., lo = mid and hi = mid - 1 for the algorithm we've designed here). Think about what happens once the search space is of length-two. You must ensure that the search space is guaranteed to be shrunk down to length-one, regardless of which condition is executed. If you take the lower middle, it will sometimes infinitely loop. And if you take the upper middle, it will be guaranteed to shrink the search space down to one.
So, it is the upper-middle that we want.
****The short rule to remember is: if you used hi = mid - 1, then use the higher midpoint. If you used lo = mid + 1, then use the lower midpoint.***** If you used both of these, then you can use either midpoint. If you didn’t use either (i.e., you have lo = mid and hi = mid), then, unfortunately, your code is buggy, and you won’t be able to guarantee convergence.
Whenever we want the upper middle, we use either mid = (lo + hi + 1) / 2 or mid = lo + (hi - lo + 1) / 2. These formulas ensure that on even-lengthed search spaces, the upper middle is chosen and on odd-lengthed search spaces, the actual middle is chosen.
72
Furthest Building You Can Reach
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building i to building i+1 (0-indexed),
If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
Constraints:
1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length
Main idea here is that you should use ladders for the largest climbs and bricks for the smallest one. How you can do this is to first use up all the ladders and keep the climbs you used them on in a min heap. Then once you run out of ladders if the next climb is more than the minimum in the min heap then pop from heap and push new climb and use bricks for this climb. Keep doing this until you run out of bricks.
class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
ladder_climbs = []
for i in range(len(heights)-1):
climb = heights[i+1] - heights[i]
if climb <= 0:
continue
else:
heapq.heappush(ladder_climbs, climb)
if len(ladder_climbs) > ladders:
bricks -= heapq.heappop(ladder_climbs)
if bricks < 0:
return i
return len(heights) - 1
73
Valid Word Square
Given an array of strings words, return true if it forms a valid word square.
A sequence of strings forms a valid word square if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).
Example 1:
Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.
Example 2:
Input: words = ["abcd","bnrt","crm","dt"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crm".
The 4th row and 4th column both read "dt".
Therefore, it is a valid word square.
Example 3:
Input: words = ["ball","area","read","lady"]
Output: false
Explanation:
The 3rd row reads "read" while the 3rd column reads "lead".
Therefore, it is NOT a valid word square.
Constraints:
1 <= words.length <= 500
1 <= words[i].length <= 500
words[i] consists of only lowercase English letters.
Tricky edge cases to the solution.
First thing to note is you double loop with i/row as len(words) and j /col as len(words[row])
Then when writing the conditions you have to make sure i/row doesn't violate the condition where it becomes col and j/col doesn't violate the condition where it becomes row.
class Solution:
def validWordSquare(self, words: List[str]) -> bool:
nrows, ncols = len(words), len(words[0])
for row in range(nrows):
for col in range(len(words[row])):
if col >= len(words) or row >= len(words[col]) or words[row][col] != words[col][row]:
return False
return True
74
Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1
Constraints:
1 <= intervals.length <= 104
0 <= starti < endi <= 106
There is a heap and normal way to do it.
you first sort the intervals array based on start time, then in the heap solution you start with first interval end time in heap and iterate through the rest of the sorted meeting intervals. The core logic is that if the start of the meeting is after end of first element in heap which is the minimum end of meeting times there you pop from heap and push current end time but if it isn't then you push end time to heap without popping. the number of elements remnaining in heap is the number of meeting rooms needed.
class Solution:
def minMeetingRooms(self, intervals):
intervals.sort(key=lambda x: x[0])
#heap elements are the meetings running in different rooms
heap = [intervals[0][1]]
for interval in intervals[1:]:
# If the room can be reused (meeting starts after the earliest ending meeting)
if interval[0] >= heap[0]:
heapq.heappop(heap) # Remove the earliest ending meeting
heapq.heappush(heap, interval[1]) # Add the current meeting end time
return len(heap)
75
Number of Connected Components in an Undirected
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Constraints:
1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
There are no repeated edges.
Create adj dictionary, iterate through nodes and do dfs. iterate through nodes as for node in range(n)
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
visited = set()
adj = {}
for edge in edges:
adj[edge[0]] = adj.get(edge[0], []) + [edge[1]]
adj[edge[1]] = adj.get(edge[1], []) + [edge[0]]
def dfs(node):
visited.add(node)
if node not in adj:
return
for n in adj[node]:
if n not in visited:
dfs(n)
res = 0
for node in range(n):
if node not in visited:
res += 1
dfs(node)
return res
76
Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don't need to modify intervals in-place. You can make a new array and return it.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105
you iterate through intervals in the list, if you fine an overlap you merge, this is one case and we can elaborate later here. if no overlap then if newInterval is less than interval we're iterating through then you add new interval and add rest of the intervals and then return. if newInterval if greater then you add the interval we're iterating through and go to next interval. if overlap then you merge the 2 interval and call than new interval and keep going. condition for overlap can be in the else, which makes sense as if you're not strictly less and not strictly more then there is overlap
class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [
min(newInterval[0], intervals[i][0]),
max(newInterval[1], intervals[i][1]),
]
res.append(newInterval)
return res
77
Course Schedule
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.
can do with dfs but should do with topological sort to know how to do topological sort.
Main idea in topological sort is that you first count indegree of all nodes, then you also build adjacency so that you know which nodes every node goes out to. You put nodes with indegree of 0 in a queue and then you pop from the queue and reduce indegree of all elements it connects to via info from the adj list. as you do this if a indegree is 0 you add that to queue. if as you pop you visit the same number of nodes as the num of courses you return true
Can also do with dfs, you create adj list and then you keep track of visited in a backtracking ish manner to find loops.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
indegree = {key:0 for key in range(numCourses)}
adj = {key:[] for key in range(numCourses)}
for a, b in prerequisites:
adj[b] += [a]
indegree[a] += 1
q = deque()
for node in indegree:
if indegree[node] == 0:
q.appendleft(node)
visited = 0
while q:
node = q.pop()
visited += 1
for n in adj[node]:
indegree[n] -= 1
if indegree[n] == 0:
q.appendleft(n)
return visited == numCourses
78
Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
dp solution with index in string as argument. when you call dp function you iterate through the words and see if you can match from index to index+len(word) if so then you call dp from new index.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@lru_cache(None)
def dp(i):
if i == len(s):
return True
contains = False
for word in wordDict:
if i+len(word)<=len(s) and s[i:i+len(word)] == word:
contains = contains or dp(i+len(word))
return contains
return dp(0)
79
Encode and Decode Strings
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function:
string encode(vector strs) {
// ... your code
return encoded_string;
}
Machine 2 (receiver) has the function:
vector decode(string s) {
//... your code
return strs;
}
So Machine 1 does:
string encoded_string = encode(strs);
and Machine 2 does:
vector strs2 = decode(encoded_string);
strs2 in Machine 2 should be the same as strs in Machine 1.
Implement the encode and decode methods.
You are not allowed to solve the problem using any serialize methods (such as eval).
Example 1:
Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]
Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2
Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);
Example 2:
Input: dummy_input = [""]
Output: [""]
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] contains any possible characters out of 256 valid ASCII characters.
encode as string_len+'#'+str and then decode
class Codec:
def encode(self, strs):
res = ""
for s in strs:
res += str(len(s)) + "#" + s
return res
def decode(self, s):
res = []
i = 0
while i < len(s):
j = i
while s[j] != '#':
j += 1
slen = int(s[i:j])
res.append(s[j+1:j+1+slen])
i = j+1+slen
return res
Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))
80
Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing
subsequence
.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
here you have to notice that longest subsequence can start from any index and from there you can jump to any index ahead with greater value. So looping becomes important. if you can notice this rest of the solution is simple dp implementation, need to keep base case of 1 and satrt max_len with 1
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
@lru_cache(maxsize=None)
def dp(i):
# Base case: The LIS ending at the first element is 1
if i == 0:
return 1
# Recursive case: Find the max LIS for all previous indices j where nums[j] < nums[i]
max_len = 1 # Length of LIS that includes just the nums[i]
for j in range(i):
if nums[j] < nums[i]:
max_len = max(max_len, dp(j) + 1)
return max_len
# Run the recursive function for all indices and return the maximum
return max(dp(i) for i in range(len(nums)))
81
Jump Game
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 105
The dp solution here makes more sense that you iterate from back of a list that keep tracks of whether you can jump to a spot. but the more optimal solution is noting that you don't really need to keep track of all the positions, you just need to keep track of the leftmost true and if it is within your jump range update is still possible
class Solution:
def canJump(self, nums: List[int]) -> bool:
can_reach = [False for _ in range(len(nums))]
can_reach[-1] = True
for i in reversed(range(len(nums)-1)):
for j in range(nums[i]+1):
can_reach[i] = can_reach[i] or can_reach[i+j]
if can_reach[i]: break
return can_reach[0]
class Solution:
def canJump(self, nums: List[int]) -> bool:
last_pos = len(nums) - 1
for i in reversed(range(len(nums)-1)):
if last_pos <= i + nums[i]:
last_pos = i
return last_pos == 0
82
Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
sort intervals list and then iterate through the list and merge
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x: x[0])
res = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i][0]> res[-1][1]:
res.append(intervals[i])
else:
res[-1] = [min(intervals[i][0], res[-1][0]), max(intervals[i][1], res[-1][1])]
return res
83
Non-overlapping Intervals
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
trick here is to notice that once you sort all start times you can start with prev pointing to 0 and iterate with i and compare the end times of prev and i. And you count overlaps. you almost simulate removal by picking how to update prev. if prev has a greater end time than i you change prev to i, this works as you know prev has a smaller start time and if it has a greater end time then removing it makes sense to remove aka not consider prev by updating prev to i and continuing
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key = lambda x: x[0])
prev = 0
ans = 0
for i in range(1, len(intervals)):
if intervals[prev][1] > intervals[i][0]:
ans += 1
if intervals[prev][1] > intervals[i][1]:
prev = i
else:
prev = i
return ans
84
Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
trick here is to know that 90 deg rotation is actually transpose followed by reflection.
be careful that you don't iterate to all elements when transposing you only have to go from 0 to row index for cols
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
nrows, ncols = len(matrix), len(matrix)
# transpose
for i in range(nrows):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
#reflection
for i in range(nrows):
for j in range(ncols//2):
matrix[i][j], matrix[i][ncols-1-j] = matrix[i][ncols-1-j], matrix[i][j]
85
Set Matrix Zeroes
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
iterate through matrix and put into q indices with 0.
then pop one by one and make all rows and cols 0 there
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
nrows, ncols = len(matrix), len(matrix[0])
q = deque()
for i in range(nrows):
for j in range(ncols):
if matrix[i][j] == 0:
q.appendleft((i,j))
while q:
row, col = q.pop()
for c in range(ncols):
matrix[row][c] = 0
for r in range(nrows):
matrix[r][col] = 0
86
Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
In this question the main idea is that you can reuse indices as you iterate through the matrix
things to remember are that you run a while loop till
len(res) < len(matrix) * len(matrix[0])
this makes keeping track of when to exit while loop easy. next every time you iterate through a row next row iteration will be 1 shorter and same for columns.
use 2 loops inside the while loop, one to go through a row and another to go through a column, keep the index at end of row iteration to use for column iteration and vice versa
```
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
r, c = len(matrix)-1, len(matrix[0])
dir = 1
res = []
i, j = 0, -1
while len(res) < len(matrix) * len(matrix[0]):
for _ in range(c):
j=j+dir
res.append(matrix[i][j])
c-=1
for _ in range(r):
i=i+dir
res.append(matrix[i][j])
r -= 1
dir *= -1
return res
```
87
Sequential Digits
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300
Output: [123,234]
Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
10 <= low <= high <= 10^9
create a string with conseq digits and move a sliding window along to pick from it
```
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
seq = "123456789"
res = []
for win in range(len(str(low)), len(str(high))+1):
lo, hi = 0, win
while hi<=len(seq):
num = int(seq[lo:hi])
if num >= low and num <= high:
res.append(num)
lo, hi = lo+1, hi+1
return res
```
88
Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
0 <= n <= 105
This question teaches 2 important concepts in bit manipulation questions. one is bit shifting and the other is zeroing out the least significant nonzero bit. x & (x-1) does this.
update rules can be:
`ans[num] = ans[num & (num - 1)] + 1`
or
`ans[num] = ans[num >> 1] + ans%2`
```
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0 for _ in range(n+1)]
for num in range(1, n+1):
ans[num] = ans[num & (num - 1)] + 1
return ans
```
89
Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
Many ways to do this question inclusing usig hashmap and using gauss' formula. But the main idea to learn from this solution is how under the XOR operation every number is its own inverse. ie 2^2 = 0 and 0^2 = 2
example :
Index 0 1 2 3
Value 0 1 3 4
missing
=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)
=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2
=0∧0∧0∧0∧2
=2
```
class Solution:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing
```
90
Bag of Tokens
You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.
Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):
Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.
Return the maximum possible score you can achieve after playing any number of tokens.
Example 1:
Input: tokens = [100], power = 50
Output: 0
Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).
Example 2:
Input: tokens = [200,100], power = 150
Output: 1
Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.
There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.
Example 3:
Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
The maximum score achievable is 2.
Constraints:
0 <= tokens.length <= 1000
0 <= tokens[i], power < 104
you might start thinking backtracking or dp but the main thing to note here is that you can sort the array and once you do that you know that to increase score you reduce from lo and if you want to increase score you can give a score away for the highest token available
```
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
tokens.sort()
lo, hi = 0, len(tokens)-1
max_score = 0
score = 0
while lo<=hi:
if tokens[lo] <= power:
power -= tokens[lo]
lo+=1
score += 1
max_score = max(max_score, score)
elif score > 0:
score -= 1
power += tokens[hi]
hi -= 1
else:
break
return max_score
```
-
Key Links
-
Subjects
-
Company
-
Find Us
-
