Three Sum

Solution

Jump Game (Greedy Strategy)

• Optimal: $O(n)$ time, $O(1)$ space.

• The Logic: Use a single loop to track the max_reach index. As you walk through, update max_reach = max(max_reach, i + nums[i]).

• When to fail: If your current index i > max_reach, you've hit a dead end $\to$ return False.

• Greedy Paradigm: "Make the best local choice right now (extend reach as far as possible) and never look back."

Two Sum (Hash Map Strategy)

• Optimal: $O(n)$ time, $O(n)$ space.

• The Logic: Look backward instead of forward. Keep a dictionary of seen numbers (value -> index).

• The Math: For every number, calculate its complement = target - num. If the complement is in seen, you've found your pair! If not, store the current number and move on.

• Trade-off: You sacrifice a little memory ($O(n)$ space) to buy massive speed gains (dropping from $O(n^2)$ to $O(n)$).

3Sum (Sorting + Two Pointers)

• Optimal: $O(n^2)$ time, $O(1)$ auxiliary space.

• The Logic ("Lock and Slide"):

  1. Sort the array first (groups duplicates, enables logic-based pointer movement).

  2. Lock the first number a using an outer loop.

  3. Place two pointers at the ends of the remaining subarray: Left (l) and Right (r).

  4. Slide pointers inward: If the sum is too big, move r left (r -= 1). If the sum is too small, move l right (l += 1).

• Handling Duplicates:

  • Skip identical numbers for the locked index: if i > 0 and a == nums[i-1]: continue.

  • Skip identical numbers for the left pointer after finding a jackpot: while nums[l] == nums[l-1].

• Crucial Rule (Indices vs. Values): Triplets like [-1, -1, 2] are perfectly legal as long as the numbers come from different physical indices (i != j != k).

Quick Interview Mindset Reminders

• Memory vs. Time: Always mention trade-offs. (e.g., "We use a hash map to get $O(n)$ time at the cost of $O(n)$ space.")

• Grid Traversals (BFS/DFS): Know how to navigate a 2D matrix (like Number of Islands), as AI data often lives in 2D grids/images.

• Top-K Elements: Know how to use a Min-Heap / Priority Queue (crucial for LLM token sampling and recommendation systems).

Summary

• So, to conclude:
  1. Organize and sort the array
  2. De-duplicate elements before settling on your first value (a)
  3. Then move to sub loop and set the L pointer to i+1 from the current position and R pointer to the end of the array.
     1. You can shift the L pointer if the combination of elements (threesum) is less than 0
     2. You can shift the R pointer if the combination of elements (threesum) is greater than 0
  4. Finally, you end the loop once the three sum is equal to 0 and return the list of elements that produced it.

Implementation

• Optimal Implementation:
  • Time complexity - O(n${}^2$)
    • Sorting the array takes O($n$ log $n$)
    • The outer loop runs $n$ times. For each iteration, the inner two-pointer while loop scans the remainder of the array in $O(n)$ time.
    • $O(n\log n)+O(n^2)=O(n^2)$.
  • Space complexity = O(1)

class Solution:

    def threeSum(self, nums: list[int]) -> list[list[int]]:

        res = []

        nums.sort()

  

        for i, a in enumerate(nums):

            if i > 0 and a == nums[i - 1]:

                continue

            l, r = i + 1, len(nums) - 1

            while l < r:

                threesum = a + nums[l] + nums[r]

                if threesum > 0:

                    r -= 1

                elif threesum < 0:

                    l += 1

                else:

                    res.append([a, nums[l], nums[r]])

                    l += 1

                    while nums[l] == nums[l - 1] and l < r:

                        l += 1

        return res