3Sum

Learning goal: Translate 3Sum into a sequence of sorted two-sum searches while preserving only unique triples.

Core idea A brute-force solution checks every choice of three indices, which takes cubic time. Instead, we sort the values and make one index responsible for the first value of a triple. The remaining two values must add to the negation of that fixed value, so the problem becomes a two-pointer search on a sorted suffix.

Algorithm plan

• Sort nums in nondecreasing order.
• Fix each candidate nums[i] as the first value.
• Search between left = i + 1 and right = n - 1.
• Move pointers according to whether the current sum is too small or too large.
• Skip equal neighboring values at the fixed position and after finding a pair.

Micro-example For [-1, 0, 1, 2, -1, -4], sorting gives [-4, -1, -1, 0, 1, 2]. Fixing -1 means the other two values must sum to 1.

Pitfalls

• Checking triples before sorting makes pointer movement invalid.
• Returning index triples instead of value triples can obscure duplicates.
• Stopping after the first answer misses other pairs for the same fixed value.

Recap

• Sort first to create order and expose duplicates.
• Fix one value and solve a two-sum suffix.
• Uniqueness is part of the algorithm, not a cleanup step.

Learning goal: Explain why pointer movement is safe after sorting and how the target is derived.

Core idea Once the array is sorted, increasing left increases the pair sum, while decreasing right decreases it. This lets us eliminate many candidate pairs without revisiting them. For a fixed value nums[i], the required pair target is -nums[i], because nums[i] + nums[left] + nums[right] = 0.

Pointer rules

Because the suffix is sorted, these movements never discard a possible solution incorrectly. After recording a triple, moving both pointers also avoids reusing the same pair positions.

Micro-example With fixed -4, the target pair sum is 4. The pair (-1, 2) sums to 1, which is too small, so left must move to a larger value.

Pitfalls

• Moving the wrong pointer can skip valid pairs.
• Comparing only the total to zero is not enough; the array must be sorted.
• The target changes whenever the fixed index changes.

Recap

• Sorted order gives monotonic pointer movement.
• Smaller sums require moving left; larger sums require moving right.
• Every fixed value has its own pair target.

Learning goal: Build the complete 3Sum algorithm, including duplicate handling at every level.

Core idea The outer loop chooses the first value, and the inner loop scans the suffix with two pointers. Sorting makes duplicate values adjacent, so equal candidates can be skipped locally instead of storing every result in a set. This is both simpler and more efficient in practice.

Algorithm plan

• Sort nums.
• For each i from 0 through n - 3:
  • If i > 0 and nums[i] == nums[i - 1], skip this fixed value.
  • Set left = i + 1 and right = n - 1.
  • While left < right, compute the three-value sum.
  • Move left or right based on the sum.
  • When the sum is zero, record the triple and skip equal values from both sides.

nums.sort()
for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    left, right = i + 1, len(nums) - 1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total < 0: left += 1
        elif total > 0: right -= 1
        else:
            answer.append([nums[i], nums[left], nums[right]])
            left += 1; right -= 1

Micro-example After finding [-1, -1, 2], move both pointers. If the next left value equals the old left value, skip it before searching again.

Pitfalls

• Skipping duplicates only for i still allows repeated triples from left or right.
• Skip the outer duplicate only when i > 0.
• The inner loop must stop when left meets right.

Recap

• Three dedupe opportunities matter: fixed value, left value, and right value.
• Sorting supports both pointer movement and adjacent duplicate skipping.
• The result is accumulated directly in sorted triple order.

Learning goal: Trace every meaningful pointer decision on one complete input.

Core idea Use the example [-1, 0, 1, 2, -1, -4] from the problem statement. After sorting, the array is [-4, -1, -1, 0, 1, 2]. We process each outer index, record both valid triples, and explicitly skip the repeated fixed -1.

Trace plan

• i = 0, fixed -4: every pair is too small, so left advances until the search ends.
• i = 1, fixed -1: pair target is 1; (-1, 2) and (0, 1) both succeed.
• i = 2, fixed -1: skip it because the same fixed value was already processed.
• i = 3, fixed 0: the remaining pair is too large, so right moves left.

Micro-example For i = 1, left = 2, and right = 5, the values are -1 and 2; together with the fixed -1, the total is zero. After recording that triple, both pointers move inward to search for a different pair.

Pitfalls

• The second -1 at index 2 must not launch a duplicate search.
• After [-1, -1, 2], do not leave a pointer on an equal neighboring value.
• A failed outer iteration is still useful: it proves its suffix has no valid pair.

Recap

• The sorted example produces exactly [-1, -1, 2] and [-1, 0, 1].
• Pointer movement finds pairs without nested enumeration.
• Outer-level skipping prevents the same value triple from being rediscovered.

Learning goal: Diagnose duplicate-output bugs and recognize the boundary cases that the sorted algorithm handles naturally.

Core idea The most common mistake is producing duplicate triples. Skipping equal values only for the outer index is insufficient: after a match, equal adjacent values at left or right can recreate the same value combination. Deduplication must happen at every level where a candidate value is chosen.

Duplicate checklist

• Outer level: skip nums[i] when it equals nums[i - 1].
• After a match: advance left while it equals its previous value.
• After a match: retreat right while it equals its previous value.
• Never skip arbitrary values before checking their sum; only equal neighbors after sorting are safe to skip.

Micro-example In [-1, -1, 0, 1, 2], fixing the first -1 can find [-1, 0, 1]. The second -1 must be skipped, or that same value triple appears again.

Pitfalls

• Arrays with fewer than three values return no triples.
• An all-zero array should return exactly [[0, 0, 0]].
• Negative values are not special; sorting and comparisons work uniformly.
• If the fixed value is positive, the remaining sorted values are also positive, so the loop can optionally break early.

Recap

• Adjacent equality is meaningful only because the array is sorted.
• Deduplicate fixed values and matched pointer values.
• Empty results and all-duplicate inputs require no special data structure.

Learning goal: Justify the quadratic running time and distinguish algorithmic space from the sort's implementation space.

Core idea Sorting costs O(n log n). The outer loop runs O(n) times, and each two-pointer scan moves inward at most O(n) times, so the search phase costs O(n²). The quadratic phase dominates the sort for the stated asymptotic bound.

Complexity accounting

Micro-example For six values, sorting is small, but the important scaling fact is that each fixed index performs one linear scan rather than a quadratic pair enumeration.

Pitfalls

• Do not call the solution O(n log n); the repeated suffix scans make it O(n²).
• In-place sorting can use O(1) auxiliary space, but some language libraries allocate O(n).
• Output storage is not counted as auxiliary working space.

Recap

• Time: O(n²) after sorting.
• Auxiliary space: O(1) with an in-place sort, or O(n) when the sort needs storage.
• The reusable pattern is: sort, fix one value, scan two pointers, and deduplicate every level.