Meta Popular Questions Flashcards
88 - Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n
Have 2 pointers at the end of arrays. Have 3rd pointer pointing at the writing position. break condition is the first part of the while loop
for write_index in range(n + m - 1, -1, -1):
if p2 < 0:
break
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[write_index] = nums1[p1]
p1 -= 1
else:
nums1[write_index] = nums2[p2]
p2 -= 1
680 - Valid Palindrome 2
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = “aba”
Output: true
Example 2:
Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.
Example 3:
Have an inner function that checks if palindrome is valid for indexes, I and j. Then use that to check if we remove a char from the left pointer or the right pointer.
Be careful to decrement the j pointer. Beware of copy/paste errors.
class Solution:
def validPalindrome(self, s: str) -> bool:
def check_palindrome(s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
i = 0
j = len(s) - 1
while i < j:
# Found a mismatched pair - try both deletions
if s[i] != s[j]:
return check_palindrome(s, i, j - 1) or check_palindrome(s, i + 1, j)
i += 1
j -= 1
return True
125 - Valid Palindrome 1
Given a string s, return true if it is a palindrome, or false otherwise.
A palindrome is valid if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
Remember to use isalnum( ) to check for alpha-numeric
~~~
class Solution:
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
# ignore chars like #$%&@-=|
while i < j and not s[i].isalnum():
i += 1
# ignore chars like #$%&@-=|
while i < j and not s[j].isalnum():
j -= 1
# compare the lowercase values
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
```
236 - Find Lowest Common Ancestor of 2 nodes in binary tree
See if 2 of 3 conditions are True
Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree.
Space Complexity: O(N). This is because the maximum amount of space utilized by the recursion stack would be N since the height of a skewed binary tree could be N.
class Solution:
def \_\_init\_\_(self):
# Variable to store LCA node.
self.ans = None
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
def recurse_tree(current_node: TreeNode) -> bool:
# If reached the end of a branch, return False.
if not current_node:
return False
# Left Recursion
left = recurse_tree(current_node.left)
# Right Recursion
right = recurse_tree(current_node.right)
# If the current node is one of p or q
mid = (current_node == p or current_node == q)
# If any two of the three flags left, right or mid become True.
if mid + left + right >= 2:
self.ans = current_node
# Return True if either of the three bool values is True.
return mid or left or right
# Traverse the tree
recurse_tree(root)
return self.ans
1249 - Remove min parens to make balanced parens
Have a Set for closing paren without opening parent,
and Stack for opening parent without closing paren. iterate through each char in string. merge stack and set . enumerate through string again, check if in newset, build char array. using ““.join
~~~
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
indexes_to_remove = set()
stack = []
for i, c in enumerate(s):
# ignore non-paren characters
if c not in “()”:
continue
# for open paren, add index to stack
if c == “(“:
stack.append(i)
elif not stack:
# we saw closing paren without seeing open paren,
# so we know that we should remove this index
indexes_to_remove.add(i)
else:
# saw closing paren, pop the open paren index from stack
stack.pop()
# make a new set that is union of removal indexes and leftover open parens
indexes_to_remove = indexes_to_remove.union(set(stack))
# string_builder will hold the characters we want to keep
string_builder = []
for i, c in enumerate(s):
if i not in indexes_to_remove:
string_builder.append(c)
return "".join(string_builder) ~~~
TwoSum (not sorted)
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Assume that each input would have exactly one solution, and you may not use the same element twice.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Use a hash to remember the index
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
h = {}
for i, n in enumerate(nums):
delta = target - n
if delta in h:
return [i, h[delta]]
h[n] = i
return []
Return the Kth largest element of an array
Call heapify on the array. Then call heappop( )
Remember to multiply by -1 and return (res * -1)
from heapq import heapify, heappop
class Solution:
def findKthLargest(self, nums, k) -> int:
nums = [-n for n in nums]
heapify(nums)
res = 0
for _ in range(k):
res = heappop(nums)
return -res
Three 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.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
You should probably provide this solution first, since it builds on TwoSum
# Time Complexity: O(n^2). TwoSumII is O(n), and we call it n times.
# Sorting the array takes O(nlogn), so overall complexity is O(nlogn+n^2).
# This is asymptotically equivalent to O(n^2).
Space Complexity: from O(logn) to O(n),
# depending on the implementation of the sorting algorithm.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0:
break
if i == 0 or nums[i - 1] != nums[i]:
self.twoSumII(nums, i, res)
return res
def twoSumII(self, nums: List[int], i: int, res: List[List[int]]):
lo, hi = i + 1, len(nums) - 1
while lo < hi:
sum = nums[i] + nums[lo] + nums[hi]
if sum < 0:
lo += 1
elif sum > 0:
hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
ThreeSum without sorting
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res, dups = set(), set()
seen = {}
for i, val1 in enumerate(nums):
if val1 not in dups:
dups.add(val1)
for j, val2 in enumerate(nums[i + 1 :]):
complement = -val1 - val2
if complement in seen and seen[complement] == i:
res.add(tuple(sorted((val1, val2, complement))))
seen[val2] = i
return res
Time Complexity: O(n^2). We have outer and inner loops, each going through n elements.
While the asymptotic complexity is the same, this algorithm is noticeably slower than the previous approach. Lookups in a hashset, though requiring a constant time, are expensive compared to the direct memory access.
Space Complexity: O(n) for the hashset/hashmap.
200 - Num 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.
Example 1:
Input: grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
Output: 1
Time complexity : O(M×N) where M is the number of rows and
N is the number of columns.
Space complexity : worst case O(M×N) in case that the grid map
is filled with lands where DFS goes by M×N deep.
class Solution:
def numIslands_2024_08_02(self, grid) -> int:
def adjacents(grid, row, col):
adjacents = []
last_row = len(grid) - 1
last_col = len(grid[0]) -1
coords = [[0,1], [0,-1], [1,0], [-1,0]]
for coord in coords:
new_row = row + coord[0]
new_col = col + coord[1]
if new_row >= 0 and new_row <= last_row and new_col >= 0 and new_col <= last_col:
adjacents.append([new_row, new_col])
return adjacents
def explore(grid, row, col):
# mark as visited
grid[row][col] = '2'
for pair in adjacents(grid, row, col):
r = pair[0]
c = pair[1]
# check if visited or ocean
if grid[r][c] != '1':
continue
explore(grid, r, c)
num_islands = 0
num_rows = len(grid)
num_cols = len(grid[0])
for i in range(num_rows):
for j in range(num_cols):
if grid[i][j] == '1':
explore(grid, i, j)
num_islands += 1
return num_islands
408 - Valid Word Abbreviation
Input: word = “internationalization”, abbr = “i12iz4n”
Output: true
Input: word = “apple”, abbr = “a2e”
Output: false
Two pointers,
if p2 is digit do some atoi logic and move the p2 pointer. final check that the two pointers = len of original stuff
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
p1 = p2 = 0
word_len = len(word)
abbr_len = len(abbr)
while p1 < word_len and p2 < abbr_len:
if abbr[p2].isdigit():
if abbr[p2] == '0': # leading zeros are invalid
return False
# atoi logic
shift = 0
while p2 < abbr_len and abbr[p2].isdigit():
shift = (shift*10)+int(abbr[p2])
p2 += 1
p1 += shift
else:
if word[p1] != abbr[p2]:
return False
p1 += 1
p2 += 1
return p1 == word_len and p2 == abbr_len
”””
525. Contiguous Array
Given a binary array nums, return the maximum length of a contiguous subarray
with an equal number of 0 and 1.
Example 1:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
“””
make use of a HashMap map to store the entries in the form of (index,count).
We make an entry for a count in the map whenever the count is encountered first, and later on use the corresponding index to find the length of the largest subarray with equal no. of zeros and ones when the same count is encountered again.
# Runtime: O(N)
# Space: O(N)
class Solution:
def findMaxLength(self, nums):
count_map = {0: -1}
maxlen = 0
count = 0
for i, num in enumerate(nums):
count += 1 if num == 1 else -1
if count in count_map:
maxlen = max(maxlen, i - count_map[count])
else:
count_map[count] = i
return maxlen
”””
Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.
“””
class Solution:
def treeToDoublyList(self, root: ‘Node’) -> ‘Node’:
def helper(node):
“””
Performs standard inorder traversal:
left -> node -> right
and links all nodes into DLL
“””
nonlocal last, first
if node:
# left
helper(node.left)
# node
if last:
# link the previous node (last)
# with the current one (node)
last.right = node
node.left = last
else:
# keep the smallest node
# to close DLL later on
first = node
last = node
# right
helper(node.right)
if not root:
return None
# the smallest (first) and the largest (last) nodes
first, last = None, None
helper(root)
# close DLL
last.right = first
first.left = last
return first
”””
71 - Given an absolute path for a Unix-style file system, which begins with a slash ‘/’, transform this path into its simplified canonical path.
In Unix-style file system context, a single period ‘.’ signifies the current directory, a double period “..” denotes moving up one directory level, and multiple slashes such as “//” are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like “…”) as valid names for files or directories.
The simplified canonical path should adhere to the following rules:
It must start with a single slash ‘/’.
Directories within the path should be separated by only one slash ‘/’.
It should not end with a slash ‘/’, unless it’s the root directory.
It should exclude any single or double periods used to denote current or parent directories.
Return the new path.
Example 1:
Input: path = “/home/”
Output: “/home”
Explanation:
The trailing slash should be removed.
Example 2:
Input: path = “/home//foo/”
Output: “/home/foo”
Explanation:
Multiple consecutive slashes are replaced by a single one.
Use a Stack. pop if see “..”, otherwise add to stack
class Solution:
def simplifyPath(self, path: str) -> str:
# Initialize a stack
stack = []
# Split the input string on "/" as the delimiter
# and process each portion one by one
for portion in path.split("/"):
# If the current component is a "..", then
# we pop an entry from the stack if it's non-empty
if portion == "..":
if stack:
stack.pop()
elif portion == "." or not portion:
# A no-op for a "." or an empty string
continue
else:
# Finally, a legitimate directory name, so we add it
# to our stack
stack.append(portion)
# Stich together all the directory names together
final_str = "/" + "/".join(stack)
return final_str
”””
76. 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.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
Example 2:
Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = “a”, t = “aa”
Output: “”
Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.
“””
Initialize a character array map of size 128 to store the frequency of characters in string t.
Initialize variables count, start, end, minLen, and startIndex.
Iterate through each character in string t and update the character frequency in the map.
Use two pointers (start and end) to slide the window and find the minimum window that contains all characters from string t.
Increment end and decrease the frequency in map for each character encountered until all characters from t are present in the window.
When all characters from t are present, update minLen and startIndex based on the current window size and starting index.
Increment start and increase the frequency in map until the window no longer contains all characters from t.
After the iteration, the minimum window is found, and the result is a substring of s starting from startIndex with length minLen.
Time complexity: O(n), where n is the length of string s.
# Space complexity: O(1), as the map array has a constant size (128).
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t or len(s) < len(t):
return “”
map = [0] * 128
count = len(t)
start = 0
end = 0
min_len = float('inf')
start_index = 0
# UPVOTE !
for char in t:
map[ord(char)] += 1
while end < len(s):
if map[ord(s[end])] > 0:
count -= 1
map[ord(s[end])] -= 1
end += 1
while count == 0:
if end - start < min_len:
start_index = start
min_len = end - start
if map[ord(s[start])] == 0:
count += 1
map[ord(s[start])] += 1
start += 1
return "" if min_len == float('inf') else s[start_index:start_index + min_len]
146 - LRU Cache
get( ) and put( ) functions both running in O(1) time.
”””
Get the current node at the end of the linked list. This is the “real” tail: tail.prev. Let’s call it previousEnd.
node is being inserted after previousEnd. Therefore, set previousEnd.next = node.
Now, we set the pointers of node. First, node.prev = previousEnd.
Next, because the “real” tail is before tail, we set node.next = tail.
Finally, we update tail.prev = node.
“””
class ListNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dic = {}
# Two sentinel values
self.head = ListNode(-1, -1)
self.tail = ListNode(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.dic:
return -1
node = self.dic[key]
# move the end of the list
self.remove(node)
self.add(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.dic:
old_node = self.dic[key]
self.remove(old_node)
node = ListNode(key, value)
self.dic[key] = node
self.add(node)
if len(self.dic) > self.capacity:
node_to_delete = self.head.next
self.remove(node_to_delete)
del self.dic[node_to_delete.key]
def add(self, node):
previous_end = self.tail.prev
previous_end.next = node
node.prev = previous_end
node.next = self.tail
self.tail.prev = node
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
314 - Binary Tree Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Output:
[[9],[3,15],[20],[7]]
BFS, save vertical level as state,
keep a hash table of the vertical levels. keep inserting
maintain the min and max level amounts.
finally iterate from min to max vertical level and access the hash
class Solution:
def verticalOrder(self, root):
if not root:
return []
vertTable = defaultdict(list)
queue = deque()
min_column = 0
max_column = 0
queue.append([root, 0])
while queue:
node, column = queue.popleft()
vertTable[column].append(node.val)
min_column = min(column, min_column)
max_column = max(column, max_column)
if node.left:
queue.append([node.left, column - 1])
if node.right:
queue.append([node.right, column + 1])
res = []
for i in range(min_column, max_column + 1):
res.append(vertTable[i])
return res
