DSA Tracker

Visualize

4Sum

Fix two indices, then run two-sum on the sorted tail

time O(n^3)space O(1) beyond the output

Checking all four indices costs O(n^4). Sorting first collapses one whole dimension: once two indices are frozen, the rest is the classic sorted two-sum, where a sum that is too small can only be raised by abandoning the smallest value and one that is too large only lowered by abandoning the largest. Each discarded value is gone for good, so the tail scan is linear. Sorting also puts equal values next to each other, which is why duplicates can be skipped by a neighbour comparison instead of de-duplicating the answer list at the end.

Details

Animated on: nums = [1, 0, -1, 0, -2, 2], target = 0 — find every unique quadruplet that sums to the target.

Problem:4SumMedium

Pattern:Two Pointers

Fix two indices, then run two-sum on the sorted tail

step 1 / 16

1
[0]
0
[1]
-1
[2]
0
[3]
-2
[4]
2
[5]

nums = [1, 0, -1, 0, -2, 2], target = 0. Unsorted, nothing tells us which way to search: a sum that is too small could be fixed by swapping in any of the remaining values.

Pseudocode
1FUNCTION fourSum(nums, target)
2  SORT nums
3  FOR i <- 0 TO LENGTH(nums) - 4
4    IF i > 0 AND nums[i] = nums[i - 1] THEN CONTINUE
5    FOR j <- i + 1 TO LENGTH(nums) - 3
6      IF j > i + 1 AND nums[j] = nums[j - 1] THEN CONTINUE
7      l <- j + 1
8      r <- LENGTH(nums) - 1
9      WHILE l < r
10        s <- nums[i] + nums[j] + nums[l] + nums[r]
11        IF s = target THEN APPEND (nums[i], nums[j], nums[l], nums[r]) TO out
12        IF s <= target THEN l <- l + 1
13        IF s >= target THEN r <- r - 1
14  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 16 steps
  1. nums = [1, 0, -1, 0, -2, 2], target = 0. Unsorted, nothing tells us which way to search: a sum that is too small could be fixed by swapping in any of the remaining values.
  2. Sorted to [-2, -1, 0, 0, 1, 2]. Now the array itself gives the direction: too small can only be fixed by taking a larger value from the left, too large by taking a smaller one from the right. That is what makes two pointers legal.
  3. Freeze the pair nums[0] = -2 and nums[1] = -1. What is left is a plain two-sum on the sorted tail nums[2..5]: find two values adding to 0 - (-2) - (-1) = 3.
  4. nums[2] + nums[5] = 2 falls 1 short of 3. nums[5] = 2 is already the largest value left, so no choice of r can rescue nums[2] = 0 — it can be dropped for good. Move l right.
  5. nums[3] + nums[5] = 2 falls 1 short of 3. nums[5] = 2 is already the largest value left, so no choice of r can rescue nums[3] = 0 — it can be dropped for good. Move l right.
  6. nums[4] + nums[5] = 1 + 2 = 3, exactly the 3 this pair needed, so the four add to 0. Record [-2, -1, 1, 2]. Both ends move: keeping either one would need the other to stay put too, and it cannot.
  7. Freeze the pair nums[0] = -2 and nums[2] = 0. What is left is a plain two-sum on the sorted tail nums[3..5]: find two values adding to 0 - (-2) - (0) = 2.
  8. nums[3] + nums[5] = 0 + 2 = 2, exactly the 2 this pair needed, so the four add to 0. Record [-2, 0, 0, 2]. Both ends move: keeping either one would need the other to stay put too, and it cannot.
  9. nums[3] = 0 repeats nums[2], so the pair (-2, 0) was already scanned at j = 2. Re-running it would re-find the exact same quadruplets, so skip j instead of de-duplicating the answer list afterwards.
  10. Freeze the pair nums[1] = -1 and nums[2] = 0. What is left is a plain two-sum on the sorted tail nums[3..5]: find two values adding to 0 - (-1) - (0) = 1.
  11. nums[3] + nums[5] = 2 overshoots 1 by 1. nums[3] = 0 is the smallest value left, so nums[5] = 2 is too big for every partner it has — move r left.
  12. nums[3] + nums[4] = 0 + 1 = 1, exactly the 1 this pair needed, so the four add to 0. Record [-1, 0, 0, 1]. Both ends move: keeping either one would need the other to stay put too, and it cannot.
  13. nums[3] = 0 repeats nums[2], so the pair (-1, 0) was already scanned at j = 2. Re-running it would re-find the exact same quadruplets, so skip j instead of de-duplicating the answer list afterwards.
  14. Freeze the pair nums[2] = 0 and nums[3] = 0. What is left is a plain two-sum on the sorted tail nums[4..5]: find two values adding to 0 - (0) - (0) = 0.
  15. nums[4] + nums[5] = 3 overshoots 0 by 3. nums[4] = 1 is the smallest value left, so nums[5] = 2 is too big for every partner it has — move r left, which leaves fewer than two values and finishes this pair.
  16. Every pair has been fixed once and its tail scanned once: 3 quadruplets — [-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]. Two nested loops over a linear two-pointer sweep, so O(n^3) instead of the O(n^4) of checking all four indices.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve 4Sum in the editorAll Two Pointers problemsBack to roadmap