LeetCode Top150 Cheatsheet (to be continued)

English
29.0~37.3 min

Note: Only the optimal solu recorded, TC stands for time complexity, SC stands for space complexity.

Array / String

1. Merge Sorted Array
merge two non-decreasing ordered arrays in-place, ensuring the first array has enough space to store all elements.

Three pointers, fill the array backwards by comparing the tails of both arrays and placing the larger element into the next available end slot to avoid overwriting valid data, remember to deal with elements left in nums2, O(m + n) time complexity(TC), O(1) space complexity(SC).

code 
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Standard solution: Merge backwards using three pointers
        Time: O(m + n)
        Space: O(1)
        """
        # Three pointers:
        p1 = m - 1      # Points to last valid element in nums1
        p2 = n - 1      # Points to last element in nums2
        p = m + n - 1   # Points to position where we place next element
        
        # Merge from back to front
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1
        
        # If there are remaining elements in nums2, copy them
        # (No need to handle remaining nums1 elements, they're already in place)
        while p2 >= 0:
            nums1[p] = nums2[p2]
            p2 -= 1
            p -= 1

2. Remove Element
Remove all elements of val in nums in-place, return the left nums length

Overwrite the target value with the array's last element and decrement the tail pointer, keeping the current pointer stationary to validate the new value, O(n) TC, O(1) SC,

code 
class Solution2:
    def removeElement(self, nums: List[int], val: int) -> int:
        """
        Swap with end approach - Better when val occurrences are rare
        Time: O(n), Space: O(1)
        """
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            if nums[left] == val:
                # Swap with element from the end
                nums[left] = nums[right]
                right -= 1
                # Do not increment left yet, need to check swapped element
            else:
                left += 1
        
        return left

3. Remove Duplicates from Sorted Array
remove the duplicates in-place in non-descreasing integer array, keeping the relative order of the elements the same.

Iterate through the list and record the current number to the slow pointer only when it marks the end of a sequence of identical values.

code 
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        slow = 0
        for fast in range(0, len(nums)):
            if fast == len(nums) - 1 or nums[fast] != nums[fast+1]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

4. Remove Duplicates from Sorted Array II
remove the duplicates in-place in non-descreasing integer array such that each unique element appears at most twice, keeping the relative order of the elements the same.

Overwrite the slow pointer with the current element only if it differs from the element two positions back in the constructed valid sequence, effectively allowing at most two duplicates.

code 
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0

        for fast in range(0, len(nums)):
            if slow - 2 < 0 or nums[fast] != nums[slow - 2]:
                # checking past:
                nums[slow] = nums[fast]
                slow += 1
        
        return slow

5. Majority Element
Given an array nums of size n, return the majority element.(whose occurance more than [n/2], can assume always exists)

Boyer-Moore Voting, Maintain a candidate and a counter that increments for matches and decrements for mismatches, effectively canceling out distinct pairs until only the majority element remains, O(n) TC, O(1) SC

code 
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = nums[0]
        count = 1

        for num in nums[1:]:
            if candidate == num:
                count += 1
            elif count > 0:
                count -= 1
            else: 
                candidate = num
                count = 1

        return candidate

6. Rotate Array
Given an integer array nums, rotate the array to the right by k steps in-place, with O(1) SC.

Three-Reversal Algorithm: Reverse the entire array to move the tail segment to the front(AB -> B'A'), then reverse each segment individually to restore their internal element order(B'A' -> BA).

code 
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        n = len(nums)
        k %= n # avoid out of boundary error
        reverse(nums, 0, n - 1)
        reverse(nums, 0, k - 1)
        reverse(nums, k, n - 1)

7. Best time to buy and sell
given prices,choose a single day to buy and a different day in the future to sell, return maximum profit, or 0 if cannot achieve any profit.

Iterate through prices while dynamically tracking the lowest buying price seen so far and calculating the potential profit if sold today, keeping the maximum result.

code 
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            cur_profit = price - min_price
            max_profit = max(cur_profit, max_profit)

        return max_profit

7. Best time to buy and sell II
given prices, can buy and/or sell on each day, but can only hold at most one stock at any time, can sell and buy the stock mutiple times on the same day. return the maximum profit.

Greedy Approach: Iterate through the array, any time the price increases from one day to the next, add that profit to our total.

code 
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i-1]
            
        return profit

8. 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.

Greedy Approach: Iterate through the array to greedily update the furthest reachable index, ensuring the current position is within bounds until the target is reached.

code 
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # (exploiting the continuity) if I try to reach the farthest point each time, store it, so we can do early stop if we go too far (can we skip some step? no)
        target_index = len(nums) - 1
        if target_index == 0:
            return True

        furthest_index = 0
        for idx, num in enumerate(nums):
            if idx > furthest_index:
                return False
            furthest_index = max(furthest_index, idx + num)
            if furthest_index >= target_index:
                return True

9. Jump Game II
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 the minimum number of jumps to reach index n - 1, (you can always reach n - 1)

Implicit BFS: Iterate through the array to expand the current reach window, incrementing the jump count only when the boundary of the current level is reached to proceed to the next reachable range.

code 
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # (exploiting the continuity) if I try to reach the farthest point each time, store it, so we can do early stop if we go too far (can we skip some step? no)
        target_index = len(nums) - 1
        if target_index == 0:
            return True

        furthest_index = 0
        for idx, num in enumerate(nums):
            if idx > furthest_index:
                return False
            furthest_index = max(furthest_index, idx + num)
            if furthest_index >= target_index:
                return True

10. H-Index
Given an array citations for each paper, return h-index(the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.)

Counting sort, O(n) TC, We trade space for time by using a frequency array (buckets) to count citations capped at N, then iterate backwards to find the largest index i where the cumulative count of papers is at least i.

code 
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)

        bucket = [0] * (n + 1)

        for c in citations:
            bucket[min(c, n)] += 1
        
        count = 0
        for i in range(n, -1, -1):
            count += bucket[i]
            if count >= i:
                return i
        return 0

11. Insert Delete GetRandom O(1)
Implement the RandomizedSet class with insert, remove, and getRandom operations that all run in average O(1) time complexity.

Hash Map + Dynamic Array, O(1) average TC. We use a list to store elements for O(1) getRandom and a hash map to map values to indices for O(1) insert/remove. The key trick for remove is to swap the target element with the last element in the list, update the map, and then pop the last element, avoiding O(n) array shifting.

code 
import random

class RandomizedSet:

    def __init__(self):
        self.data = []
        self.indices = {}

    def insert(self, val: int) -> bool:
        if val in self.indices:
            return False
        
        self.indices[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.indices:
            return False
        
        # Swap the target element with the last element to delete in O(1)
        idx = self.indices[val]
        last_element = self.data[-1]
        
        self.data[idx] = last_element
        self.indices[last_element] = idx
        
        self.data.pop()
        del self.indices[val]

        return True

    def getRandom(self) -> int:
        return random.choice(self.data)

12. 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].

Prefix & Suffix Products, O(N) TC, O(1) Extra Space. We initialize the result array with 1s. We use a prefix variable to calculate the product of elements to the left during the forward pass, and a suffix variable to calculate the product of elements to the right during the backward pass, multiplying them into the result array.

code 
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n

        prefix_product = 1
        for i in range(n):
            res[i] *= prefix_product
            prefix_product *= nums[i]

        suffix_product = 1
        for i in range(n-1, -1, -1):
            res[i] *= suffix_product
            suffix_product *= nums[i]
        
        return res

13. Gas Station
Given arrays gas and cost, find the starting gas station index to travel around the circuit once. Return -1 if impossible.

Greedy, O(N) TC.
Key insight: If you start at A and run out of gas at B, you cannot start at any station between A and B (because they would run out even sooner without the accumulated gas from A).
Algorithm: If total_gas < total_cost, return -1 immediately. Iterate through stations maintaining current_tank. If current_tank < 0, the current path failed; reset start to i + 1 and current_tank to 0.

code 
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    # Global check: if total gas is not enough for total cost, impossible.
    if sum(gas) < sum(cost):
        return -1

    start_index = 0
    current_tank = 0

    for i in range(len(gas)):
        current_tank += gas[i] - cost[i]

        # If tank drops below 0, logic dictates no station from 
        # start_index to i can be the start. Jump to i + 1.
        if current_tank < 0:
            start_index = i + 1
            current_tank = 0

    return start_index

14. Candy
Distribute candies to n children such that every child gets \ge 1 candy, and children with higher ratings get more than their immediate neighbors. Minimize the total candies.

Greedy, Array, Two-Pass. O(N) TC.
Key insight: The "neighbors" constraint is bidirectional (left and right). We can decouple this into two unidirectional constraints:
1. Left Pass: Ensure child i has more than i-1 if ratings[i] > ratings[i-1].
2. Right Pass: Ensure child i has more than i+1 if ratings[i] > ratings[i+1].
Algorithm: The minimum candy for any child is the maximum of the requirements imposed by the Left Pass and the Right Pass. Candy[i] = \max(Left[i], Right[i]).

code (Standard vs. Space Optimized)

Version 1: Standard Approach (Two Arrays)

Easier to understand. We explicitly build L and R arrays and merge them.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        L = [1] * n
        R = [1] * n
        
        # 1. Left Pass: Compute constraints from the left neighbor
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                L[i] = L[i-1] + 1
        
        # 2. Right Pass: Compute constraints from the right neighbor
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                R[i] = R[i+1] + 1
                
        # 3. Merge: Take the max to satisfy both constraints
        total = 0
        for i in range(n):
            total += max(L[i], R[i])
            
        return total

Version 2: Space Optimized (One Array)

We reuse the candy array from the Left Pass. When doing the Right Pass, we update values in-place using max.

Crucial Logic: Why doesn't the Left Pass data pollute the Right Pass calculation?

  • We update candy[i-1] using candy[i] ONLY if ratings[i-1] > ratings[i].
  • If ratings[i-1] > ratings[i], it implies ratings[i] < ratings[i-1].
  • This means during the first pass (Left Pass), candy[i] did not accumulate a value from i-1. It was reset to (or stayed at) 1 (or its local minimum).
  • Therefore, candy[i] does not contain "Left Logic" noise when we need it for the "Right Logic" calculation.
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy = [1] * n

        # 1. Left Pass: Standard accumulation
        # candy[i] now represents "Left Slope Height"
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1] + 1
        
        # 2. Right Pass: In-place update
        # We process from right to left (n-1 -> 0)
        for i in range(n-1, 0, -1):
            if ratings[i-1] > ratings[i]:
                # LOGIC CHECK:
                # We need to ensure candy[i-1] is higher than candy[i].
                # candy[i] here is safe to use. Since ratings[i] < ratings[i-1], 
                # candy[i] did NOT gain value from candy[i-1] during the Left Pass.
                # We take max() to preserve the Left Pass result if it was already higher.
                candy[i-1] = max(candy[i-1], candy[i] + 1)
        
        return sum(candy)

proof: https://likegiver.com/blogs/leetcode-135-candy-proof-en

42. Trapping Rain Water

Compute how much water can be trapped between bars of an elevation map after raining.

Two Pointers, Array. O(N) TC, O(1) SC.
Key Insight (The "Shortest Wall" Principle):
Water level at any index i is determined by \min(\text{LeftMax}, \text{RightMax}) - \text{height}[i].

  • Standard DP: Stores all prefix/suffix maxes (O(N) Space).
  • Two Pointers (O(1) Space): We don't need the exact value of the taller wall. If left_max < right_max, we know the bottleneck for the left side is definitely left_max. The true right_max is guaranteed to be \ge the current right_max, so left_max remains the limiting factor.

Critical Logic Check:
Use if left_max < right_max to decide direction. We compare historical peaks, not current heights.

code

Optimal Approach: Compact Logic

This style merges the "update max" and "add water" steps.

  • If height[left] is a new peak, left_max updates to equal it, so left_max - height[left] adds 0.
  • If height[left] is a valley, left_max remains higher, so it adds positive water.
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0  # Safety check for empty input
        
        left, right = 0, len(height) - 1
        left_max = height[left]
        right_max = height[right]
        water = 0

        while left <= right:
            # DECISION: Which side is the bottleneck?
            if left_max < right_max:
                # 1. Update Left Max (If current is higher, water adds 0)
                left_max = max(left_max, height[left])
                # 2. Accumulate Water
                water += left_max - height[left]
                # 3. Move Pointer
                left += 1
            else:
                # Symmetric logic for the Right side
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1
        
        return water

Note: The condition left <= right ensures the last meeting point is processed (though it usually adds 0 water as it's the peak), making the logic foolproof without complex pointer math.

Reference:

  1. "Cracking the coding interview"
  2. Gemini 3 pro