visual walkthrough
4Sum
Generalises the k-sum reduction and overflow awareness.
The idea
It is 3Sum with one more loop. Sort, fix two numbers, then squeeze the remaining pair with two pointers, skipping repeated values so each quadruplet appears once.
Each extra fixed number multiplies the work by n, but the final pair always costs just one pass.
Complexity
| approach | time | space |
|---|---|---|
| Four loops | O(n⁴) | O(1) |
| Sort + two pointers | O(n³) | O(1) |