Hints — p26 3Sum

Read one at a time.

Hint 1 — Don’t go cubic. Three nested loops is O(N³) = 2.7×10¹⁰ at N=3000 — TLE. You need O(N²). When you see “find triples with sum = target,” the meta-pattern is fix one element, two-sum the rest.

Hint 2 — Sort first. Sorting (O(N log N), absorbed into O(N²)) unlocks two things: (a) converging two-pointer for the inner two-sum (no hash needed), and (b) dedup by skipping equal-value runs.

Hint 3 — Three dedups, not one. Duplicates appear in three places. (a) Outer loop: if i > 0 and nums[i] == nums[i-1]: continue. (b) After a hit, advance lo past equal values: while lo < hi and nums[lo] == nums[lo-1]: lo += 1. (c) Same for hi. Missing any → duplicate triplets in output.

Hint 4 — Move rule (and why it works). At state (i, lo, hi), compute s = nums[lo] + nums[hi]. If s < -nums[i], the sum is too small — lo must advance (any smaller hi would only shrink the sum further). If s > -nums[i], hi must retreat. If ==, record the triplet and advance BOTH.

Hint 5 — Loop bounds + pruning. while lo < hi (strict, not <=). Outer loop bound: range(n - 2) — last i is n-3. Pruning: once nums[i] > 0, no remaining triplet can sum to 0 (sorted ascending means rest are all ≥ 0) — break.

If still stuck: look at three_sum in solution.py — it’s 20 lines and the dedups are commented.