4Sum - Video Solutions

Problem Overview: 4Sum asks you to find all unique quadruplets [a, b, c, d] in an array such that their sum equals a given target. The main challenge is avoiding duplicate quadruplets while keeping the algorithm efficient. A naive four‑nested‑loop solution works but is far too slow for typical constraints.

Approach 1: Sort and Two-pointer Technique (Time: O(n^3), Space: O(1) extra)

Start by sorting the array. Sorting makes duplicate handling straightforward and enables the two-pointer pattern. Fix the first element with index i, then fix the second element with index j. The remaining two numbers are found using two pointers: one starting at j + 1 and the other at the end of the array. Compute the sum of the four elements and move pointers inward depending on whether the sum is smaller or larger than the target. Skip duplicates for i, j, and the pointer values to ensure each quadruplet appears once.

This approach works because sorting allows efficient pruning and duplicate elimination. Instead of checking every possible quadruple explicitly, the two-pointer step finds matching pairs in linear time. Overall complexity becomes O(n^3) after the O(n log n) sort. This pattern frequently appears in problems related to Two Pointers, Sorting, and advanced Array search techniques.

Approach 2: Hash Map with Two Sum Reduction (Time: O(n^3), Space: O(n))

This method reduces the 4Sum problem into repeated 2Sum searches. Iterate through pairs of indices (i, j) as the first two numbers. For the remaining portion of the array, compute the required complement target - nums[i] - nums[j]. A hash map or set tracks numbers seen while scanning the rest of the array, allowing constant‑time lookup for the complement pair.

Each iteration effectively becomes a classic 2Sum search using hashing. The key advantage is simpler pointer logic and direct complement lookups. However, handling duplicates becomes more complex, and the extra hash structure increases memory usage to O(n). Runtime still reaches O(n^3) because the outer two loops remain.

Recommended for interviews: The sorted two‑pointer solution is the expected approach. Interviewers want to see that you recognize the pattern: extend the 3Sum technique by fixing two indices and applying two pointers for the remaining pair. The brute-force four-loop idea shows baseline understanding, but the O(n^3) two-pointer optimization demonstrates stronger algorithmic thinking and familiarity with common array patterns.