Neetcode1H

Cheatsheet Content

1. Number of Submatrices That Sum to Target Notes: Uses 2D prefix sums and a hash map. Iterate through all possible pairs of columns $(c_1, c_2)$. For each pair, calculate row-wise sums for the submatrix formed by these columns. Apply the 1D subarray sum equals K logic using a hash map to count valid rows. Python Snippet: from collections import defaultdict def numSubmatrixSumTarget(matrix, target): rows, cols = len(matrix), len(matrix[0]) count = 0 for c1 in range(cols): row_sums = [0] * rows for c2 in range(c1, cols): for r in range(rows): row_sums[r] += matrix[r][c2] # Now, find subarrays in row_sums that sum to target prefix_sum_count = defaultdict(int) prefix_sum_count[0] = 1 current_sum = 0 for s in row_sums: current_sum += s count += prefix_sum_count[current_sum - target] prefix_sum_count[current_sum] += 1 return count 2. Naming a Company Notes: Group ideas by their first character. For each pair of initial characters $(c_1, c_2)$, count distinct suffixes. If two companies `A_suffix1` and `B_suffix2` can be swapped to `B_suffix1` and `A_suffix2`, they contribute to the count. The key insight is to count common suffixes between sets of words starting with different letters. Python Snippet: from collections import defaultdict def uniqueNames(ideas): initial_char_groups = defaultdict(set) for idea in ideas: initial_char_groups[idea[0]].add(idea[1:]) count = 0 chars = list(initial_char_groups.keys()) for i in range(len(chars)): for j in range(i + 1, len(chars)): char1 = chars[i] char2 = chars[j] set1 = initial_char_groups[char1] set2 = initial_char_groups[char2] # Count common suffixes common_suffixes = len(set1.intersection(set2)) # Number of unique suffixes in set1 not in set2 distinct_in_set1 = len(set1) - common_suffixes # Number of unique suffixes in set2 not in set1 distinct_in_set2 = len(set2) - common_suffixes # Each combination forms 2 valid pairs (swap suffixes) count += 2 * distinct_in_set1 * distinct_in_set2 return count 3. Text Justification Notes: Greedy approach: pack as many words as possible into each line. Calculate total length of words and available spaces. Distribute spaces evenly. Extra spaces are added one by one from left to right. Handle the last line separately: left-justified with single spaces between words, then padded with spaces at the end. Python Snippet: def fullJustify(words, maxWidth): result = [] n = len(words) i = 0 while i 4. Minimum Number of Operations to Make Array Continuous Notes: First, remove duplicates and sort the array to simplify the problem. A continuous array of length $N$ must contain elements in a range $[X, X+N-1]$. Iterate through each unique number as a potential starting point $X$ for the continuous array. For each $X$, determine how many elements in the sorted unique array fall within $[X, X+N-1]$. The number of elements *outside* this range (or missing from it) is the number of operations. Use a sliding window or two pointers on the sorted unique array for efficient counting. Python Snippet: def minOperations(nums): n = len(nums) unique_nums = sorted(list(set(nums))) min_ops = float('inf') right = 0 for left in range(len(unique_nums)): # Expand window until unique_nums[right] is outside the target range # Target range for length n starting at unique_nums[left] is [unique_nums[left], unique_nums[left] + n - 1] while right 5. Subarrays with K Different Integers Notes: This problem can be solved by reducing it to "number of subarrays with at most K distinct integers". The count of subarrays with *exactly* K distinct integers is: $ \text{count(at most K distinct)} - \text{count(at most K-1 distinct)} $ Function `atMostK(nums, k)` uses a sliding window and a frequency map. Expand the window from `right`, shrink from `left` if distinct count exceeds `k`. Python Snippet: from collections import defaultdict def subarraysWithKDistinct(nums, k): def atMostK(arr, K): count = 0 left = 0 freq_map = defaultdict(int) distinct_count = 0 for right in range(len(arr)): if freq_map[arr[right]] == 0: distinct_count += 1 freq_map[arr[right]] += 1 while distinct_count > K: freq_map[arr[left]] -= 1 if freq_map[arr[left]] == 0: distinct_count -= 1 left += 1 # All subarrays ending at 'right' and starting from 'left' are valid count += (right - left + 1) return count return atMostK(nums, k) - atMostK(nums, k - 1) 6. Number of Atoms Notes: Use a stack to handle parentheses and nested formulas. When encountering '(', push a new map onto the stack. When encountering ')', pop the top map, multiply its counts by the following number, and merge with the map below it. Parse element names (uppercase followed by lowercase letters) and their counts. Finally, sort elements alphabetically and format the output. Python Snippet: from collections import defaultdict def countOfAtoms(formula): n = len(formula) stack = [defaultdict(int)] i = 0 while i 1: result.append(str(final_map[atom])) return "".join(result) 7. Parsing A Boolean Expression Notes: Recursive approach or stack-based approach. For a recursive solution, define a helper function that takes a substring and returns its boolean value. Identify the operator `&`, `|`, `!`. Recursively evaluate the arguments within the parentheses. A stack can track current operations and their operands. When a ')' is encountered, pop elements until the corresponding '(' and apply the operator. Python Snippet (Stack-based): def parseBoolExpr(expression): stack = [] # Stores operators and boolean values for char in expression: if char == ')': # Pop elements until '(' operands = [] while stack[-1] != '(': operands.append(stack.pop()) stack.pop() # Pop '(' operator = stack.pop() # Pop operator if operator == '&': stack.append(all(operands)) elif operator == '|': stack.append(any(operands)) elif operator == '!': stack.append(not operands[0]) # '!' only has one operand elif char == ',': continue elif char == 't': stack.append(True) elif char == 'f': stack.append(False) else: # It's an operator '&', '|', '!' or '(' stack.append(char) return stack[0] 8. Shortest Subarray with Sum at Least K Notes: Use prefix sums to transform subarray sum problem into point difference problem. $P[j] - P[i] \ge K$. Maintain a monotonic deque of indices. The deque stores indices $j$ such that $P[j]$ is increasing. When $P[j] - P[\text{deque.front()}] \ge K$, we have a valid subarray. Update minimum length and pop from front. When $P[j] \le P[\text{deque.back()}]$, pop from back to maintain monotonicity (smaller prefix sums are better for future calculations if they are further left). Python Snippet: from collections import deque def shortestSubarray(nums, k): n = len(nums) prefix_sum = [0] * (n + 1) for i in range(n): prefix_sum[i+1] = prefix_sum[i] + nums[i] min_len = float('inf') # Deque stores indices `j` of prefix sums `P[j]` such that `P[j]` is increasing # This helps find `i` such that `P[j] - P[i] >= k` dq = deque() for j in range(n + 1): # Condition 1: P[j] - P[i] >= k # If P[j] - P[dq.front()] >= k, then current subarray [dq.front()+1 ... j] is valid # and we can pop dq.front() as it will not form a shorter subarray with any future `j'` while dq and prefix_sum[j] - prefix_sum[dq[0]] >= k: min_len = min(min_len, j - dq.popleft()) # Condition 2: Maintain monotonicity # If P[j] 9. Robot Collisions Notes: Sort robots by their positions to process collisions in order. Use a stack to manage robots moving right. When a robot moving left encounters a robot on the stack (moving right), a collision occurs. Handle collision logic: stronger robot survives (or both destroy each other if equal health). The surviving robot's health is reduced; if it's still moving right, push it back to the stack. If moving left, continue checking with stack. Python Snippet: def robotCollisions(positions, healths, directions): n = len(positions) robots = [] for i in range(n): robots.append((positions[i], healths[i], directions[i], i)) # (pos, health, dir, original_idx) robots.sort() # Sort by position stack = [] # Stores robots moving 'R' that might collide for pos, health, direction, original_idx in robots: if direction == 'R': stack.append((pos, health, direction, original_idx)) else: # direction == 'L' while stack and health > 0: prev_pos, prev_health, prev_direction, prev_original_idx = stack[-1] if prev_health == health: stack.pop() # Both destroyed health = 0 elif prev_health health stack[-1] = (prev_pos, prev_health - 1, prev_direction, prev_original_idx) # Left-moving robot destroyed health = 0 if health > 0: # If left-moving robot survived all collisions stack.append((pos, health, direction, original_idx)) # Collect remaining robots and sort by original index remaining_robots = [] for _, h, _, idx in stack: remaining_robots.append((idx, h)) remaining_robots.sort() return [h for idx, h in remaining_robots] 10. Kth Smallest Product of Two Sorted Arrays Notes: Binary search on the answer (the $k$-th smallest product). The range of possible products can be very wide (e.g., $-10^5 \times 10^5$ to $10^5 \times 10^5$). For a given `mid` value, count how many pairs $(num1, num2)$ have $num1 \times num2 \le \text{mid}$. The `count_less_than_or_equal(mid)` function needs to be efficient. Iterate through `nums1` and for each `n1`, use binary search on `nums2` to find valid `n2`s. Handle positive/negative `n1`s carefully as it flips the inequality. Python Snippet: import bisect def kthSmallestProduct(nums1, nums2, k): def count_le(val): count = 0 for n1 in nums1: if n1 == 0: if val >= 0: count += len(nums2) elif n1 > 0: # Find count of n2 such that n1 * n2 n2 n2 >= val / n1 (inequality flips) # This is len(nums2) - bisect_left(nums2, val / n1) count += len(nums2) - bisect.bisect_left(nums2, (val + n1 - 1) // n1) # ceiling div for negative return count # Determine search range for the answer # Max possible value: 10^5 * 10^5 = 10^10 # Min possible value: -10^5 * 10^5 = -10^10 low = -10**10 high = 10**10 ans = 0 while low = k: ans = mid_val high = mid_val - 1 else: low = mid_val + 1 return ans 11. Find K-th Smallest Pair Distance Notes: Similar to "Kth Smallest Product", this is binary search on the answer. The range of possible distances is $[0, \text{max(nums)} - \text{min(nums)}]$. For a given `mid` distance, count how many pairs $(num_i, num_j)$ have $|num_i - num_j| \le \text{mid}$. The `count_le(mid)` function needs `nums` to be sorted. Then, use a two-pointer approach (or binary search) to count pairs efficiently for each `nums[i]`. Python Snippet: import bisect def smallestDistancePair(nums, k): nums.sort() n = len(nums) def count_le(dist): count = 0 left = 0 for right in range(n): # For nums[right], find how many nums[left] satisfy nums[right] - nums[left] = nums[right] - dist while nums[right] - nums[left] > dist: left += 1 count += (right - left) # Number of valid pairs ending at right return count low = 0 # Min possible distance high = nums[-1] - nums[0] # Max possible distance ans = 0 while low = k: ans = mid_dist high = mid_dist - 1 else: low = mid_dist + 1 return ans 12. Split Array Largest Sum Notes: Another binary search on the answer. The range for the largest sum of a subarray is $[\text{max(nums)}, \text{sum(nums)}]$. For a given `mid` value (potential largest sum), check if the array can be split into `k` or fewer subarrays, where each subarray's sum is $\le \text{mid}$. The `check(max_sum)` function is greedy: try to fit as many numbers as possible into the current subarray without exceeding `max_sum`. Count the number of splits required. Python Snippet: def splitArray(nums, k): def check(max_subarray_sum): # Returns true if array can be split into at most k subarrays # where each subarray sum 13. LFU Cache Notes: Requires tracking both frequency and recency. Use a map `key_to_node` to store `key: node` where `node` contains `(key, value, frequency)`. Use another map `freq_to_dll` where `freq: DoublyLinkedList`. Each DLL stores nodes with that specific frequency, ordered by recency (LRU within a frequency level). Need to track `min_freq`. `get(key)`: update frequency, move node to next frequency's DLL. `put(key, value)`: If new key, add to `min_freq` DLL. If cache full, evict from `min_freq`'s DLL (LRU), then update `min_freq` if that DLL becomes empty. If existing key, update value, then act like `get`. Python Snippet: class Node: def __init__(self, key, val, freq): self.key = key self.val = val self.freq = freq self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = Node(0, 0, 0) # Dummy head self.tail = Node(0, 0, 0) # Dummy tail self.head.next = self.tail self.tail.prev = self.head self.size = 0 def add_node(self, node): # Add node right after head (most recent) node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node self.size += 1 def remove_node(self, node): node.prev.next = node.next node.next.prev = node.prev self.size -= 1 def pop_tail(self): # Remove and return LRU node (before tail) if self.size > 0: node = self.tail.prev self.remove_node(node) return node return None class LFUCache: def __init__(self, capacity: int): self.capacity = capacity self.size = 0 self.min_freq = 0 self.key_to_node = {} # key -> Node self.freq_to_dll = defaultdict(DoublyLinkedList) # freq -> DoublyLinkedList def _update_node(self, node): # Remove from current freq's DLL self.freq_to_dll[node.freq].remove_node(node) # If old min_freq's DLL becomes empty, increment min_freq if self.freq_to_dll[node.freq].size == 0 and self.min_freq == node.freq: self.min_freq += 1 # Increment frequency and add to new freq's DLL node.freq += 1 self.freq_to_dll[node.freq].add_node(node) def get(self, key: int) -> int: if key not in self.key_to_node: return -1 node = self.key_to_node[key] self._update_node(node) return node.val def put(self, key: int, value: int) -> None: if self.capacity == 0: return if key in self.key_to_node: node = self.key_to_node[key] node.val = value self._update_node(node) else: if self.size == self.capacity: # Evict LFU (and LRU within LFU) lfu_node = self.freq_to_dll[self.min_freq].pop_tail() if lfu_node: del self.key_to_node[lfu_node.key] self.size -= 1 # Add new node new_node = Node(key, value, 1) self.key_to_node[key] = new_node self.freq_to_dll[1].add_node(new_node) self.min_freq = 1 # New node always starts with freq 1 self.size += 1