lc Flashcards
121: Max profix in an array
Input: prices = [7,1,5,3,6,4]
Output: 5
think of 2 ways
SOLUTION 1:
left and right pointers
if A[i] > A[j]:
i = j, j += 1
else:
record max
j += 1
SOLUTION 2:
if num < min: reset min and max
if num > max: update max, record res
- Contains Duplicate
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
set,
sort
- Product of Array Except Self
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
count the 0’s
multiply everything
if zeros_count >= 2: return all 0’s
if no zeros:
if 1 zero at index i:
res = product
else:
res[i] = product / nums[i]
- Maximum Subarray
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Key Idea:
ensure that the running sum is (+)
Solution: write this without i and k
for i in nums length:
if nums[k..i] < 0:
res = max nums[k..i], res
k = i // running_sum starts at k
else:
running_sum = nums[k..i] // running_sum += nums[i]
res = max(running_sum, res)
CODE:
running_sum = 0
res = nums[0]
for num in nums:
running_sum += num
if running_sum < 0:
res = max(res, running_sum)
running_sum = 0
else:
res = max(res, running_sum)
return res
- Find Minimum in Rotated Sorted Array
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Note:
if nums[l] >= nums[r], we have to check for condition nums[mid] > nums[r]
MIN = nums[0]
while l <= r:
mid = (l + r) // 2
if nums[l] >= nums[r]:
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid - 1
else:
r = mid
MIN = min(MIN, nums[mid])
- Search in Rotated Sorted Array
Note:
if we use while l <=r, we must update l and r points as += 1, -= 1 respectively,
we can also return mid from this
while l <= r:
if nums[mid] == target: return mid
# do normal binary search if Nl < Nr
if nums[l] < nums[r]:
if nums[mid] < target: l = mid + 1
else: r = mid - 1
# at this point, nums[mid] could be either >= nums[l]
# or < nums[l]
# for each case, check which side target should be in
else:
if nums[mid] >= nums[l]:
if target >= nums[l] and target <= nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if target >= nums[mid] and target <= nums[r]:
l = mid + 1
else:
r = mid - 1
if nums[mid] == target: return mid
return -1
- 3Sum
sort nums
for i in nums length:
if nums[i] == previous number: continue
use left and right pointer method and to find pairs that equal to current number.
while l < r:
sum = nums[i] + nums[l] + nums[r]
if sum < 0:
l += 1
elif sum > 0:
r -= 1
else:
we've found a target, however, we want to move left and right pointers inward to avoid duplicates
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l - 1]: l += 1
while l < r and nums[r] == nums[r + 1]: r -= 1
return res
- Container With Most Water
UNDESTAND why it works:
while l < r:
res = max(res, area(height,l,r))
if height[l] > height[r]:
r -= 1
else:
l += 1
return res
- Climbing Stairs
”””
dp[i] = dp[i-1] + dp[i-2]
“””
if n <= 3:
return n
one, two = 1, 2
three = 3
for i in range(3,n+1):
tmp = one + two # three
one = two
two = tmp
three = tmp
return three
- Coin Change.
review: bottom up and top down approach (skipped top down approach)
BOTTOM
for i in range(amount + 1):
for coin in coins:
if i- coin == 0:
dp[i] = 1
elif i - coin > 0:
dp[i] = min(dp[i-coin] + 1, dp[i])
can be simplified to:
for i in range(amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i-coin] + 1, dp[i])
- Longest Increasing Subsequence
REVIEW:
dp[i] = max(dp[i],1 + dp[k]) if nums[i] > nums[k]
dp[i] = 1 if nums[i] <= nums[k]
where:
k = is the range form 0..i-1
for i in range(len(nums)):
max_i = 0
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], 1 + dp[j])
- Longest Common Subsequence
TOP DOWN:
try t1[0] and t2[0]
if match:
res += 1
advance
else try:
t1[0] and t2[1] +
t1[1] and t2[0]
base case:
if indices are out of range
then add cache to it
BOTTOM UP:
dp = initialize 2d array of size (M+1)*(N+1)
iterate from bottom right to top left
if characters match:
dp[i][j] = 1 + dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j] , dp[i][j+1])
return dp[0][0]
CODE:
for i in range(len(s1)-1, -1,-1):
for j in range(len(s2)-1, -1, -1):
if s1[i] == s2[j]:
dp[i][j] = 1+ dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j] , dp[i][j+1])
- Word Break
REVIEW neetcode solution
TOP DOWN RECURSIVE:
add memoization to the following code:
def bfs(cur_s):
if cur_s in wordDict: return True
if cur_s in seen: seen[cur_s]
for i in range(len(cur_s),-1,-1):
if cur_s[i:] in wordDict:
if bfs(cur_s[:i]):
return True
return False
BOTTOM UP:
- j represents the end of the prefix of the string.
- dp[i] represents whether the substring up to index s[0..i-1]
- if dp[j] is true, and dp[j..i-1] is also true, then the entire substring dp[i] is True
- since j represents every possible prefix, the prefix of “” must also exists, thus we set dp[0] to True,
wordSet = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1,len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[-1]
- Combination Sum IV
answer at i = sum of (
if rem == 0, then theres only 1 way = 1
if rem != 0, then the number of count is dp[rem]
)
BOTTOM UP APPROACH:
dp = [0] * (target+1)
dp[0] = 1
for i in range(target+1):
for num in nums:
if num > i: break
dp[i] += dp[i-num]
return dp[target]
- House Robber
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
- House Robber II
return max(
nums[0],
house_robber1(nums[1:]),
house_robber1(nums[:-1])
)
- Decode Ways
Conceptualize, Know how to write in bottom up way
TOP DOWN:
def dfs(cur_nums):
if str(cur_nums) in dp: return dp[str(cur_nums)]
if not cur_nums: return 1
if cur_nums[0] == ‘0’: return 0
res = dfs(cur_nums[1:])
if len(cur_nums) >= 2 and int(cur_nums[:2]) <= 26:
res += dfs(cur_nums[2:])
dp[str(cur_nums)] = res
return res
BOTTOM UP:
if s[0] == “0”:
return 0
two_back = 1
one_back = 1
for i in range(1, len(s)):
current = 0
if s[i] != “0”:
current = one_back
two_digit = int(s[i - 1: i + 1])
if two_digit >= 10 and two_digit <= 26:
current += two_back
two_back = one_back
one_back = current
- Unique Paths
dp[i][j] = dp[i+1][j] + dp[i][j+1]
STRINGS:
- Jump Game
iterate backwards
if cur_jump + cur_index >= last_successful_index
then last_successful_index = current_index
True if last_successful_index == 0
- Longest Substring Without Repeating Characters
- use a set and add/remove from left and right pointers
- before loop starts, make sure that set is unique by updating left pointer
- Longest Repeating Character Replacement
- length - highest unique char <= # of allowed replacements
- at every iteration, compare the highest with the count of the current character in the substring
- update l while it is not valid
- record result
- Minimum Window Substring
review optimal
BRUTE FORCE:
create a dictionary of both s1 and s2
iterate s1:
while map1 satisfies map2:
record min res
remove char at indexL from map
increment indexL
- Valid Anagram
solution 1:
- compare sorted values
solution 2:
- create a map from the first string
- iterate the second string and decrement the map
- return length of map == 0
- Group Anagrams
Idea:
group the words by their sorted order
implementation
create a dictionary
for every word:
sort it
use the sorted version as the key
append the current word to the dictionary using the sorted key
- Valid Parentheses
if matches open breaces, append
if closed braces, compare
if stack empty early, return False
return arry has 0 length
- Valid Palindrome
two pointer
- Longest Palindromic Substring
expand from middle in two ways:
- single piont
- double point
- Encode and Decode Strings
make sure that the prefix tells you about the words afterwards
encoding:
res + length(string) + “#” + string
decoding:
find the # position
turn values up to # into an integer
append to list
- Maximum Depth of Binary Tree
level order traversal
- Same Tree
level order traversal
- Invert Binary Tree
if not node, return node
invert left
invert right
switch l and right pointers
return root
- Binary Tree Maximum Path Sum
joined val
joined_val = node.val + l + r
split_val = max(node.val, node.val + l, node.val + r)
self.res = max(self.res, split_val, joined_val)
# ret value
return split_val
- Serialize and Deserialize Binary Tree
understand tree properties for:
dfs, bfs, inorder, level order
with respect to stacks
Serialize:
call in order on it
Deserialize:
call in order while popping the very first node
LEVEL ORDER:
Serialize: Level Order Traversal => ‘‘.join(array)
Desearialize:
if string is ‘’: return None
root is the first val
add to queue
we want to go through all the nodes by doing..
while queue exist:
get node from queue
update left node child if not none
update arr index
get node from queue update right node child if not none update arr index
return root
while queue:
node = queue.popleft()
if nodes[index] != “None”:
node.left = TreeNode(int(nodes[index]))
queue.append(node.left)
index += 1
if nodes[index] != "None":
node.right = TreeNode(int(nodes[index]))
queue.append(node.right)
index += 1
- Construct Binary Tree from Preorder and Inorder Traversal
note: the index of the root node in inorder array also represents the number of
nodes that the left subtree has
root = preorder[0]
Left:
preorder[1: inorder.indexOf(root) + 1]
inorder[0: inorder.indexOf(root)]
Right:
preorder[inorder.indexOf(root) + 1: ]
inorder[inorder.indexOf(root) + 1: ]
OPTIMIZE:
- use a hashmap
- convert to: def helper(pre_left, pre_right, in_left, in_right):
- Subtree of Another Tree
compare the two tress in a in pre order format
- Kth Smallest Element in a BST
redo
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
- Validate Binary Search Tree
stack = []
node = root
prev = -float(‘inf’)
while stack or node:
while node:
stack.append(node)
node = node.left
# current node node = stack.pop() if node.val <= prev: return False prev = node.val # right node node = node.right
if node and node.val <= prev: return False
return True
- Lowest Common Ancestor of a Binary Search Tree
Recursive Logic:
- if one is greater and one is smaller than current node, return current node
- if current node is p or q, return current node
- if both nodes are greater than current node, return searched right node
- if both nodes are smaller than current node, return searched left node
Iterative Logic:
same thing as above but use an infinite loop and update root node
- Implement Trie (Prefix Tree)
should learn how to write it iteratively
Recursive:
def insert(self, word: str) -> None:
def dfs(node, word):
if not word:
node['stop'] = True
return
# add current character to current node
if word[0] not in node:
node[word[0]] = {}
dfs(node[word[0]], word[1:])
dfs(self.root, word)
- Design Add and Search Words Data Structure
should learn how to write it iteratively
Solution idea:
search all possible children keys when wild card is reached
def helper(root, word):
# base case
if not word:
return True if root.stop else False
# search all possible values when wild card is reached
elif word[0] == '.':
for v in root.chars.values():
if helper(v, word[1:]):
return True
return False
# dfs
elif word[0] not in root.chars:
return False
else:
return helper(root.chars[word[0]], word[1:])
- Word Search II
sometimes we can generate/memoize from the target instead of the given data.
Technique:
leaving crumbs method + building Trie from target instead of data.
ALGORITHM:
Note:
- path is used for keeping track of the words that we want to add to result
- visited prevents us from visiting the same cell again
build a trie from the words
use the trie to run dfs on the matrix for every cell
if trie.node.end_of_word == True, add to result
add visted cordinates to trie
add current char to path
call dfs
remove visited cordinates from trie
remove current char from path
REMINDER:
path must be added THEN poped after dfs’ing
must not forget __init__ when build classes
Code:
def dfs(i,j, node, visited, path):
if (i,j) in visited: return
if i >= ROW or i < 0 or j >= COL or j < 0: return
char = board[i][j]
# Here you have to pass the child node to DFS rather than the current node
if char not in node.children: return
visited.add((i,j))
path.append(char)
# Here you should check if we reached the end of a word in the trie. This should be done with node.children[char].stop, not node.stop
if node.children[char].stop:
res.add(''.join(path))
cords = [(1,0),(-1,0), (0,1), (0,-1)]
for cord in cords:
x, y = cord
dfs(i+x,j+y, node.children[char], visited, path) # here you are now passing the child node, not the current node
visited.remove((i,j))
path.pop()
- Balanced Binary Tree
dfs then check:
if abs(left - right) > 1: return -1
return max(left, right) + 1
- Implement Queue using Stacks
move to the other queue in the same order
- Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
use counter to keep track
in the end, the number with a positive counter is the result
- Add Binary
Review
summ = ca + cb + carry
cur_bit = summ % 2 # Current bit is the remainder when dividing by 2
carry = summ // 2 # Carry is the quotient when dividing by 2
res = str(cur_bit) + res
- Diameter of Binary Tree
instead of considering where null node yields -1 diameter, have it yield 0 and not update the root diameter with an extra value.
we basically want to calculate the height of the node
def dfs(node):
if not node: return 0
left_length = dfs(node.left)
right_length = dfs(node.right)
Update the diameter at every node
self.res = max(self.res, left_length + right_length)
Return the length of the longest path which passes through this node
return max(left_length, right_length) + 1
- Insert Interval
review Logn solution
add intervals to the result list based on the following conditions:
- if current_interval.end < newInterval.start: add current_interval
- if current_interval.start > newInterval.end: add newInterval, then join the rest
- else: this this means that there must be overlap. So we update new interval = newInterval.start = min(newInterval.start, cInterval.start), newInterval.end = min(newInterval.end, cInterval.end)
res.append(newInterval)
return res
- 01 Matrix
graph
redo on your own
BFS Solution:
Create a copy of mat, we’ll call it matrix.
Use a data structure seen to mark nodes we have already visited and a queue for the BFS.
Put all nodes with 0 into the queue. We will also track the level/number of steps with each queue entry. Mark these nodes in seen as well.
Perform the BFS:
- While queue is not empty, get the current row, col, steps from the queue.
- Iterate over the 4 directions. For each nextRow, nextCol, check if it is in bounds and not already visited in seen.
- If so, set matrix[nextRow][nextCol] = steps + 1 and push nextRow, nextCol, steps + 1 - onto the queue. Also mark nextRow, nextCol in seen.
Dynamic Programming:
Create a copy of mat, we’ll call it dp.
- Iterate row by row, column by column. At each row, col:
- Initialize minNeighbor to a large value. This represents the minimum value of dp from the cells we could have arrived from.
- Making sure to stay in bounds, check the two cells we could have arrived from: row - 1, col and row, col - 1.
- Update minNeighbor with their dp values.
- Set dp[row][col] = minNeighbor + 1.
Iterate over dp again but in reverse order. At each row, col:
- Initialize minNeighbor to a large value.
- Making sure to stay in bounds, check the two cells we could have arrived from: row + 1, col and row, col + 1.
- Update minNeighbor with their dp values.
- If minNeighbor + 1 is less than dp[row][col] (the minimum distance if we only considered down-right paths), then update it.
- K Closest Points to Origin
review quickpartition
- Evaluate Reverse Polish Notation
Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
use stack
- Min Stack
stack with tuples (x,y)
- x: actual value
- y: min value at current level
optimize by using 2 stacks:
- stack: holds original stack values
- min_stack (x,y)[]:
- x is the value, y is the count
- keepds track of the min value at the current level. If newly added value is the same as top of min_stack, increment the y count
- same for popping
- Combination Sum
redo
- For each target value t from 1 to target, iterate through each number num in candidates. If num is greater than t, skip to the next iteration.
- For each combination prev_comb that sums up to t - num, append a new combination consisting of prev_comb followed by num to dp[t], ensuring that this doesn’t result in a permutation.
need to initialize 0 because if t-num == 0, we want to add [] + [num] to dp[t]
dp = {0: [[]]}
for t in range(1, target + 1):
for num in candidates:
if num > t: break
if t - num not in dp:
continue
iterate combinations for t - num
for prev_comb in dp.get(t - num):
# ensure unique permutation
if prev_comb and prev_comb[-1] > num:
continue
# if t doesn't already exist, create it
if t not in dp:
dp[t] = []
# add prev_combination with current number to dp[t]
new_combination = prev_comb + [num]
dp[t].append(new_combination)
- Permutations
DFS:
iterate and make copies
- Lowest Common Ancestor of Binary Tree
sub optimal:
1. if find target.left == True and find target.right == True
return root
- if only (either left or right) is true,
return self.lowestCommonAncestor(left or right), depending on which side is true
Optimal:
dfs on left and right first
if both true, return root
if root == p or q, return root
if dfs from left is not None: return dfs from left
if dfs from right is not None: return dfs from right
981 time-based-key-value-store
Find the position using bisect_right
a map, that points to a Node.
This node contains an array of timestamps and a dictionary.
set:
append timestamp to array
update dictionary
get:
index of dictionary =
binary search for timestamp in array
helpful - learn bisect:
pos = bisect.bisect_right(timestamps, timestamp)
If the exact timestamp is not present, adjust the position
if pos > 0:
return sub_maps[timestamps[pos - 1]]
else:
return “”
l, r = 0, len(timestamps)-1
- Accounts Merge
review and redo
redo when reviewing graphs:
brute:
build a mapping between {name => [emails]}
while building, find union between account sets by:
while i < len(dic[name]):
if emails & dic[name][i]: # Intersection of two sets
emails |= dic[name][i] # Union of two sets
dic[name].pop(i) # Remove the merged set of emails
else:
i += 1
dic[name].append(emails)
** DFS:**
** union Find:**
- Sort Colors
you failed. redo
Dutch National Flag problem
- Initialize three pointers: l at the start, i at the start, and r at the end of the array.
- If nums[i] is 0, swap nums[i] with nums[l], then increment both l and i.
- If nums[i] is 1, just move to the next element by incrementing i.
- If nums[i] is 2, swap nums[i] with nums[r] and then decrement r, but don’t
- Partition Equal Subset Sum
- Idea *
- it is a include exclude problem to build subarrays
** todo **
- convert top bottom to bottom up
- link this problem with the maximum substirng. the one that builds the tree by deciding to inlcude or exclude
- lots of problems. review notion
** Top Down **
- think of subtraction
code:
@lru_cache(maxsize=None)
def dfs(nums: Tuple[int], n: int, subset_sum: int) -> bool:
# Base cases
if subset_sum == 0:
return True
if n == 0 or subset_sum < 0:
return False
# binary decision. to keep or not to keep
result = (
dfs(nums, n - 1, subset_sum - nums[n - 1]) or # take
dfs(nums, n - 1, subset_sum)) # not take
return result
** mistake 1: checks for array **
only, not subsets
for i in range(len(nums)):
for j in range(0, i):
print(sum(nums[j:i]))
** mistake 2: **
brute force will be 2^n
- String to Integer (atoi)
Key Points:
-
res = res * 10 + int(s[i])times 10 then add integer -
2**31-1or-2**31-1
- Spiral Matrix
Key Points:
- use borders
- include the ending borders when traversing
- make sure that the second time the iterate the row or column, they are itterating on a different row or colum. can check this by applying
if topborder < botborderorif leftborder < rightborder
- subsets
- review binary solution
binary
backtrack
cascading
- Letter Combinations of a Phone Number
dfs
level order traversal
- Minimum Window Substring
have and needs
expand and contract
use table and counter
