LeetCode Problem Solutions Cheatsheet

Cheatsheet Content

1. Maximum Value of K Coins From Piles Problem Type: Dynamic Programming Notes: This problem can be solved using dynamic programming. The state $dp[i][k]$ represents the maximum value obtained from the first $i$ piles using exactly $k$ coins. For each pile, we can choose to take $0, 1, \dots, \min(k, \text{pile_size})$ coins. Key Idea: Iterate through piles and for each pile, iterate through possible coin counts taken from it, updating DP states. def maxValueOfCoins(piles, k): dp = [[0] * (k + 1) for _ in range(len(piles) + 1)] for i in range(1, len(piles) + 1): for j in range(k + 1): current_pile_sum = 0 # Option 1: Don't take any coins from current pile dp[i][j] = dp[i-1][j] # Option 2: Take x coins from current pile for x in range(min(j, len(piles[i-1]))): current_pile_sum += piles[i-1][x] dp[i][j] = max(dp[i][j], dp[i-1][j - (x + 1)] + current_pile_sum) return dp[len(piles)][k] 2. Regular Expression Matching Problem Type: Dynamic Programming, Recursion Notes: This is a classic DP problem. $dp[i][j]$ is `True` if $s[i:]$ matches $p[j:]$. Handle `.` (any character) and `*` (zero or more occurrences) carefully. Key Idea: Recursion with memoization or iterative DP. For `*`, consider two cases: match zero times or match one/more times. def isMatch(s, p): memo = {} def dp(i, j): if (i, j) in memo: return memo[(i, j)] if j == len(p): return i == len(s) first_match = (i 3. Apply Operations to Maximize Score Problem Type: Stack, Monotonic Stack, Prime Factorization, Segment Tree/Sparse Table (for range queries) Notes: The score of an array is based on prime factors. We need to find subarrays $[i, j]$ such that $nums[k]$ is the maximum for $i \le k \le j$. This screams Monotonic Stack for finding nearest greater/smaller elements. Key Idea: Use a monotonic stack to find the left and right boundaries for each element $nums[k]$ where it is the maximum. Then, for each such subarray, $nums[k]$ is the pivot. The problem involves a modulo arithmetic and potentially precomputing prime counts. # This problem is complex and requires precomputing prime counts # and using modular exponentiation. The monotonic stack part is key. # A simplified structure for finding boundaries: def prime_score(n): # Precompute prime counts for numbers up to max(nums) # This is a placeholder if n 1: count += 1 return count def maximumScore(nums, k): n = len(nums) mod = 10**9 + 7 # Precompute prime_score for all numbers in nums # Using Sieve of Eratosthenes to get prime factors for all numbers efficiently max_val = max(nums) spf = [0] * (max_val + 1) # smallest prime factor for i in range(2, max_val + 1): if spf[i] == 0: # i is prime for j in range(i, max_val + 1, i): if spf[j] == 0: spf[j] = i prime_scores = [0] * (max_val + 1) for i in range(2, max_val + 1): temp = i factors = set() while temp > 1: factors.add(spf[temp]) temp //= spf[temp] prime_scores[i] = len(factors) left = [-1] * n # index of nearest element to the left greater than or equal to nums[i] right = [n] * n # index of nearest element to the right greater than nums[i] stack = [] for i in range(n): while stack and nums[stack[-1]] 4. Minimum Number of Increments on Subarrays to Form a Target Array Problem Type: Greedy, Stack Notes: The key observation is that if we increment a subarray, we are essentially increasing all elements in that range. When we encounter a number larger than the previous one, we need to perform additional increments. Key Idea: The total number of increments is the sum of $(target[i] - target[i-1])$ for all $i$ where $target[i] > target[i-1]$. This is because to reach $target[i]$ from $target[i-1]$, we need at least $target[i] - target[i-1]$ additional increments that extend to $i$. def minNumberOperations(target): ans = target[0] for i in range(1, len(target)): if target[i] > target[i-1]: ans += (target[i] - target[i-1]) return ans 5. Find the Maximum Sum of Node Values Problem Type: Tree DP, Greedy Notes: This problem involves XOR operations on a tree. The key property of XOR is $a \oplus b \oplus b = a$. This means if we XOR a node's value with $k$, we must XOR another node's value with $k$ to maintain the total sum property (or effectively, we can pair up operations such that the rest of the tree is unaffected). Key Idea: Each edge operation involves two nodes. If we flip a node's value (XOR with $k$), we must flip an adjacent node's value. This suggests that we can always pair up flips. The total sum can be maximized by flipping any node if its value increases, as long as we can find a pair. Greedy Approach: Calculate the sum if all nodes are flipped to their maximum potential ($max(val, val \oplus k)$). Then, count how many nodes actually increase their value. If this count is even, we can achieve this maximum sum. If odd, we must sacrifice one flip. We sacrifice the one that causes the minimum loss. def maximumValueSum(nums, k, edges): total_sum = 0 count_increased = 0 min_loss = float('inf') # Minimum loss if we have to un-flip an odd number of nodes for num in nums: flipped_val = num ^ k if flipped_val > num: total_sum += flipped_val count_increased += 1 min_loss = min(min_loss, flipped_val - num) # Smallest gain else: total_sum += num min_loss = min(min_loss, num - flipped_val) # Smallest loss if we had to flip it if count_increased % 2 == 0: return total_sum else: # If count_increased is odd, we must make it even. # This means either un-flipping one node that was flipped (loss of flipped_val - num) # or flipping one node that was not flipped (loss of num - flipped_val) # In both cases, the net change is min_loss. return total_sum - min_loss 6. Maximum Score of a Good Subarray Problem Type: Two Pointers, Monotonic Stack Notes: A "good" subarray must contain index $k$. We want to maximize $min(nums[i \dots j]) \times (j - i + 1)$. Key Idea (Two Pointers): Start with the subarray $[k, k]$. Expand outwards using two pointers $i$ and $j$. At each step, expand the pointer that points to the larger value to maintain a larger minimum. def maximumScore(nums, k): n = len(nums) left, right = k, k min_val = nums[k] max_score = nums[k] while left > 0 or right 7. Minimum Number of K Consecutive Bit Flips Problem Type: Sliding Window, Difference Array Notes: We want to flip $k$ consecutive bits to turn all `0`s to `1`s. This is a classic "flip window" problem. Key Idea: Instead of actually flipping bits (which is $O(N \cdot K)$), use a "difference array" or a counter to track the effect of flips. When we flip a window, it affects bits from $i$ to $i+k-1$. We only need to know the state of `nums[i]` to decide if it needs a flip. def minKBitFlips(nums, k): n = len(nums) flips = 0 flip_effect_at_i = 0 # tracks the number of active flips affecting current position i is_flipped = [0] * n # is_flipped[i] = 1 if nums[i] was the start of a flip for i in range(n): # If a flip started at i-k needs to end, decrement flip_effect_at_i if i >= k: flip_effect_at_i -= is_flipped[i-k] # Determine the current effective state of nums[i] # (nums[i] + flip_effect_at_i) % 2 gives the actual bit value considering flips if (nums[i] + flip_effect_at_i) % 2 == 0: # If it's a 0, we need to flip if i + k > n: # Cannot flip k consecutive bits return -1 flips += 1 flip_effect_at_i += 1 is_flipped[i] = 1 # Mark that a flip started here return flips 8. Put Marbles in Bags Problem Type: Greedy, Sorting Notes: When we split $N$ marbles into $K$ bags, we make $K-1$ cuts. Each cut is between $weights[i]$ and $weights[i+1]$. The cost added by a cut at index $i$ is $weights[i] + weights[i+1]$. We want to maximize the difference between max and min scores. Key Idea: The sum of scores is $(weights[0] + weights[N-1]) + \sum_{j=1}^{K-1} (weights[cut_j] + weights[cut_j+1])$. The initial $weights[0] + weights[N-1]$ is fixed. We need to choose $K-1$ cut points to maximize the sum of $weights[i] + weights[i+1]$ for the max score, and minimize it for the min score. def putMarbles(weights, k): n = len(weights) if k == 1 or k == n: return 0 # No cuts needed, or all marbles are separate bags # The cost associated with each possible cut point i (between weights[i] and weights[i+1]) # is weights[i] + weights[i+1]. # We need to pick k-1 cut points. # Calculate all possible costs for making a cut cut_costs = [] for i in range(n - 1): cut_costs.append(weights[i] + weights[i+1]) # Sort these costs cut_costs.sort() # Ascending order # To maximize the score, pick the k-1 largest cut costs max_score_sum = sum(cut_costs[n - 2 - (k - 1) + 1 : n - 1]) # Sum of largest k-1 # To minimize the score, pick the k-1 smallest cut costs min_score_sum = sum(cut_costs[0 : k - 1]) # Sum of smallest k-1 return max_score_sum - min_score_sum 9. Data Stream as Disjoint Intervals Problem Type: Data Structures, Merging Intervals Notes: We need to efficiently add numbers and return a list of disjoint intervals. A `list` or `SortedList` of intervals can be used. Key Idea: When adding a new number, check if it merges with existing intervals. If `num` is $x$, it can merge with an interval $[a, b]$ if $x = a-1$ or $x = b+1$. After merging, we might need to merge the new interval with its neighbors if they now become contiguous. import bisect class SummaryRanges: def __init__(self): self.intervals = [] # List of [start, end] intervals def addNum(self, value: int) -> None: # Find insertion point # bisect_left finds insertion point for value in a sorted list # We need to find the interval that *contains* or *is next to* value # Custom binary search to find relevant intervals # Alternatively, maintain a sorted list of intervals and iterate/merge # A simpler approach: add the value as an interval [value, value] # Then merge with existing intervals. # This can be slow if many intervals and many adds. # Optimized approach: # 1. Find if `value` is already in an interval. If so, return. # 2. Find if `value` can merge with an existing interval. # 3. If `value` creates a new interval or merges/expands existing ones, update. # A common approach for this type of problem is to use a list of intervals # and binary search for the insertion point. # Then, iterate around that point to merge. # Let's use a simpler list-based approach for clarity, though it might be O(N) per addNum temp_intervals = [] merged = False for start, end in self.intervals: if value end + 1: # Current interval is completely before value temp_intervals.append([start, end]) else: # Value overlaps or is adjacent to current interval value = min(value, start) value = max(value, end) # Don't add to temp_intervals yet, wait for next interval to potentially merge if not merged: temp_intervals.append([value, value]) # Reconstruct intervals by merging adjacent ones after initial processing self.intervals = [] if not temp_intervals: return temp_intervals.sort() # Ensure sorted current_start, current_end = temp_intervals[0] for i in range(1, len(temp_intervals)): next_start, next_end = temp_intervals[i] if next_start list[list[int]]: return self.intervals # A more robust and efficient implementation would directly insert and merge # using bisect_left/bisect_right on the intervals list. # For example, find index `idx` where `intervals[idx][1] value + 1`. # Then check `intervals[idx][1] == value - 1` and `intervals[idx+1][0] == value + 1` for merging. 10. Meeting Rooms III Problem Type: Priority Queue, Simulation Notes: This problem requires managing meeting rooms and assigning meetings to the earliest available room. If multiple rooms are available at the same time, pick the one with the smallest index. Key Idea: Use two priority queues: one for available rooms (stores room indices) and one for occupied rooms (stores `(finish_time, room_index)`). Sort meetings by start time. import heapq def mostBooked(n, meetings): # Sort meetings by start time meetings.sort() # Priority queue for available rooms (stores room index) available_rooms = [i for i in range(n)] heapq.heapify(available_rooms) # Priority queue for occupied rooms (stores (end_time, room_index)) occupied_rooms = [] # (end_time, room_index) # Counter for how many times each room is used room_usage = [0] * n for start, end in meetings: # Free up rooms that have finished while occupied_rooms and occupied_rooms[0][0] max_usage: max_usage = room_usage[i] result_room = i return result_room 11. Integer to English Words Problem Type: String Manipulation, Recursion Notes: Convert an integer to its English word representation. Handle numbers up to $2^{31} - 1$. Key Idea: Break down the number into groups of three digits (thousands, millions, billions, etc.). Handle each three-digit group recursively. def numberToWords(num: int) -> str: if num == 0: return "Zero" less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"] tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"] thousands = ["", "Thousand", "Million", "Billion"] def helper(n): if n == 0: return "" elif n = 100 return less_than_20[n // 100] + " Hundred " + helper(n % 100) result = "" i = 0 while num > 0: if num % 1000 != 0: result = helper(num % 1000).strip() + " " + thousands[i] + " " + result num //= 1000 i += 1 return result.strip() 12. K-th Smallest in Lexicographical Order Problem Type: Trie-like Traversal, Digit DP Notes: Find the $k$-th smallest number in lexicographical order among integers from $1$ to $n$. Key Idea: Imagine a tree where children of `x` are `x0, x1, ..., x9`. We need to efficiently count how many numbers start with a given prefix. Then, navigate this conceptual tree. def findKthNumber(n: int, k: int) -> int: current = 1 # Start with the first number in lexicographical order k -= 1 # k becomes 0-indexed while k > 0: # Calculate how many numbers are in the subtree rooted at 'current' # and within the range [1, n] count = 0 next_prefix = current + 1 curr_prefix = current while curr_prefix = count: # The k-th number is not in this subtree, move to the next sibling current += 1 k -= count else: # The k-th number is in this subtree, move to the first child current *= 10 k -= 1 # Moved one step deeper (from parent to child) return current 13. Minimum One Bit Operations to Make Integers Zero Problem Type: Bit Manipulation, Recursion, Gray Code Notes: Convert any non-negative integer to $0$ using specific one-bit operations. This problem relates to Gray codes. Key Idea: The operations are: Change the rightmost bit. Change the $i$-th bit if the $(i-1)$-th bit is $1$ and all bits to its right (from $i-2$ to $0$) are $0$. This structure suggests a recursive pattern. To change $2^N$ to $0$, it takes $2^{N+1}-1$ operations. The general solution can be found by relating it to Gray codes or by observing the recursive structure of operations. # This problem has a known recursive solution based on bit patterns. # Let f(n) be the minimum operations to make n zero. # f(0) = 0 # f(1) = 1 (0 -> 1) # For n of the form 2^k: # f(2^k) = f(2^(k+1) - 1 - 2^k) + 1 + 2^k - 1 = 2^(k+1) - 1 # This is derived from the Gray code sequence. # A more direct recursive approach: # If n is 0, cost is 0. # Find the most significant bit (MSB) of n, say at position k (i.e., n has 2^k as MSB). # To turn n to 0: # 1. Turn n to 2^k. This involves making all bits below k to 0. Cost is f(n ^ 2^k). # 2. Turn 2^k to 0. Cost is f(2^k). # The total cost is f(n ^ 2^k) + f(2^k). # The operations are structured such that f(2^k) = 2^(k+1) - 1. # And f(n) = f(n ^ 2^k) + 2^k - 1 + 1 (the last op to change MSB) # This isn't quite right. The actual recurrence is based on Gray Code properties. # The most common solution leverages the observation that: # If n has MSB at position k, then # ops(n) = ops(n XOR 2^k) + 2^k (if n has MSB at k) # This formula is incorrect. # The correct formula is related to the number of operations to turn a number N into 0. # ops(N) = ops(N ^ (1 int: res = 0 # Iterate from MSB downwards while n > 0: # Find the highest set bit (MSB) k = n.bit_length() - 1 # Add 2^(k+1) - 1 operations. This is the cost to turn 2^k to 0. # This is based on Gray code properties: # to convert 2^k to 0, it takes 2^(k+1)-1 operations. # to convert any number N to 0: # 1. Flip MSB of N (k-th bit) to 0. This requires 2^k operations. # 2. Now we have a number N_prime (N without MSB). # We need to make N_prime to 0. # This is the standard solution for converting a number to its Gray code equivalent, # then converting Gray code to binary. res += (1 0 # 1 -> 1 # 10 -> 11 (1 op) # 11 -> 100 (2 ops) # 100 -> 111 (3 ops) # 101 -> 110 (4 ops) # 110 -> 101 (5 ops) # 111 -> 100 (6 ops) # The operations for 2^k are 2^(k+1)-1. # The recurrence is: f(n) = 2^(k+1) - 1 - f(n - 2^k) # This specific loop structure is another way to compute it: # res = 0 # for i in range(30, -1, -1): # Max 30 bits for 2^31 - 1 # if (n >> i) & 1: # If the i-th bit is set # res = (1 >= 1 # This is the standard way to calculate Gray code from binary # But it's not the solution to the problem. # The actual solution is a variant of the Gray code calculation: # Let's use the explicit recursive definition for clarity. # The problem asks for the number of operations to convert N to 0. # This is equivalent to `grayToBinary(N)` where `grayToBinary` is a function # that converts a Gray code to its binary representation. # No, it's not that either. # The problem is a direct mapping where `dp[i]` is the minimum ops for `i`. # dp[0] = 0 # dp[1] = 1 # dp[2] = 2 (10 -> 11 -> 01 -> 0) is wrong. # 000 -> 0 (0 op) # 001 -> 1 (1 op) # 010 -> 11 (1 op, op2 on bit 1) -> 10 (op1 on bit 0) -> 00 (op2 on bit 1 again based on 10) # 010: (010 -> 011 (op1) -> 001 (op2) -> 000 (op1)) = 3 ops # The actual sequence is: # 000 # 001 (1 op) # 011 (op2 on bit 1, because bit 0 was 1) (2 ops) # 010 (op1) (3 ops) # 110 (op2 on bit 2, because bit 1 was 1) (4 ops) # 111 (op1) (5 ops) # 101 (op2 on bit 1, because bit 0 was 1) (6 ops) # 100 (op1) (7 ops) # The cost to convert $2^k$ to $0$ is $2^{k+1}-1$. # The general recurrence is `f(n) = f(n ^ (1 11 -> 01 -> 00) # op(3) = 2 (11 -> 01 -> 00) # op(4) = 7 (100 -> 101 -> 111 -> 110 -> 010 -> 011 -> 001 -> 000) # The recurrence relation is: # If $n = 2^k$, then $f(n) = 2^{k+1} - 1$. # If $n = 2^k + x$ where $x