4Sum LeetCode 18 — k-Sum Pattern Guide

LeetCode 18 asks you to find all unique quadruplets in an integer array nums that sum to a given target. The output is a list of lists — order within each quadruplet does not matter, but no duplicate quadruplets are allowed in the result.

The brute-force approach of checking every combination of four indices runs in O(n^4), which is far too slow for n up to 200. The optimal solution reduces the problem layer by layer, arriving at an O(n^3) algorithm using sorting and two pointers.

Key constraints to keep in mind: the array length is 1 to 200, values range from -10^9 to 10^9, and the target can also be as large as 10^9 in absolute value. The wide value range means integer overflow is a real concern in Java and C++.

2Sum is the base case: given a sorted array and a target, use two pointers from both ends — left and right — and move them inward based on whether the current sum is too small or too large. This finds all pairs in O(n).

3Sum extends this by fixing one element with an outer loop, then applying 2Sum on the remaining suffix. For each fixed element nums[i], you solve the 2Sum on nums[i+1..n-1] with target - nums[i]. This gives O(n^2) total.

4Sum extends 3Sum by adding another outer loop. Fix nums[i] and nums[j], then solve the inner 2Sum on nums[j+1..n-1] with target - nums[i] - nums[j]. Two nested loops plus one O(n) two-pointer pass equals O(n^3).

Start by sorting the array. Sorting is required for two pointers to work and also makes it trivial to skip duplicate values. Once sorted, the outer loop index i runs from 0 to n-4, and the inner loop index j runs from i+1 to n-3.

For every (i, j) pair, set left = j+1 and right = n-1. The two-pointer target for this inner search is remain = target - nums[i] - nums[j]. If nums[left] + nums[right] == remain, you have found a quadruplet; append it and advance both pointers. If the sum is too small, advance left. If too large, retreat right.

The outer two loops cover all O(n^2) pairs, and each pair triggers an O(n) two-pointer scan, giving the overall O(n^3) complexity. Space complexity is O(1) excluding the output list.

Because the array is sorted, duplicate values are adjacent. After processing a value at position i, skip all subsequent positions where nums[i] == nums[i-1]. The same rule applies at each of the four pointer positions independently.

For the outer loop i: at the start of each iteration (when i > 0), skip if nums[i] == nums[i-1]. For the inner loop j: when j > i+1, skip if nums[j] == nums[j-1]. For the two pointers after recording a result: advance left while nums[left] == nums[left-1], and retreat right while nums[right] == nums[right+1].

The critical rule is to skip duplicates AFTER processing the first occurrence, not before. If you skip at the beginning of the loop without checking whether you already processed that value, you will miss valid quadruplets that happen to start with a repeated element.

Two pruning conditions applied at the outer loop (i) can cut runtime significantly on nearly-sorted or bounded inputs. First: if nums[i] * 4 > target, break entirely — since the array is sorted, every element from i onward is at least nums[i], so no quadruplet starting here or later can be small enough. Second: if nums[i] + nums[n-1] * 3 < target, continue — the best possible quadruplet using nums[i] as the smallest element is still below target, so skip this i.

Apply the same two pruning conditions at the inner loop (j): if nums[i] + nums[j] * 3 > target, break; if nums[i] + nums[j] + nums[n-1] * 2 < target, continue. These four pruning checks add no asymptotic cost but dramatically reduce the practical number of two-pointer passes on typical inputs.

Together, the pruning turns a worst-case O(n^3) algorithm into something that runs noticeably faster on real LeetCode test cases with duplicate-heavy or extreme-value inputs.

In Python, the implementation is clean and concise. Sort the array, run two nested for loops for i and j with duplicate-skip guards, then run the two-pointer inner loop. Python integers are arbitrary precision so there is no overflow concern. The entire solution is under 25 lines.

In Java, the structure is identical but you must cast to long before summing: long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]. Without the cast, nums[i] + nums[j] is computed as 32-bit int and can silently overflow before the comparison. This is a common source of wrong answers that passes all small test cases but fails on edge inputs.

Both implementations share the same structure: sort, nested loops with pruning and duplicate skipping, two-pointer inner loop with result collection. Time complexity O(n^3), space complexity O(1) excluding output. On LeetCode 18, this passes all 295 test cases.

4Sum sits at the top of a natural family: Two Sum (O(n) with hashmap or O(n log n) sorted), 3Sum (O(n^2)), and 4Sum (O(n^3)). The pattern extends: you could write a recursive k-sum function that fixes one element and calls itself for (k-1)-Sum until it reaches the 2Sum base case. This recursive formulation is occasionally asked in advanced interviews.

Container With Most Water also uses two pointers on a sorted-like structure, but it is a maximization problem rather than an exact-sum search. Trapping Rain Water uses two pointers differently again — tracking max heights from each side. Two Sum remains the foundational problem, and its hashmap variant appears in k-sum solutions when you want to optimize beyond the sorted two-pointer approach.

When you encounter any k-sum problem in an interview, the mental checklist is: sort the array, fix k-2 elements with nested loops, apply two-pointer 2Sum at the innermost level, and add duplicate skipping and pruning at every level. This pattern is reliable, generalizable, and demonstrates algorithmic maturity to your interviewer.