4Sum — Editorial — LearnYard

Opening the reading…

Intuitionwhy four choices become two fixed choices and one shrinking pair

A quadruplet is valid when four different positions contribute values whose sum is target, but the order of those positions does not matter. Sorting gives every quadruplet a canonical nondecreasing order. Once the array is sorted, equal values sit together, so choosing the first occurrence of a value at each decision point is enough to represent all value combinations without repeating one.

Fix the first two values, nums[i] and nums[j]. The remaining task is to find two values after j whose sum is target - nums[i] - nums[j]. Because that suffix is sorted, left and right tell you whether the current sum is too small or too large: move left rightward to increase the sum, or move right leftward to decrease it. After finding a pair, move both pointers and skip equal neighbors.

Approach

Sort nums so every quadruplet has one ordered representation and equal values become adjacent, which makes duplicate prevention possible with local comparisons.

Create an empty answer list and loop i through possible first positions, stopping before there are fewer than three positions after i because no quadruplet can be formed there.

Skip i when nums[i] equals the previous value, because the earlier occurrence already explores exactly the same first value and would produce duplicate quadruplets.

For each i, loop j through possible second positions and skip repeated nums[j] values within that i, because the same first two values would repeat the same remaining-pair search.

Set left to j + 1 and right to the final index, then scan while left is less than right; the ordering guarantees that increasing left raises the pair sum and decreasing right lowers it.

Compute the four-value sum in long long before comparing it with target, because four values near the integer limits can overflow int and reverse the comparison.

When the sum equals target, append the four sorted values, move both pointers inward, and skip equal neighbors so the same quadruplet is not appended again from repeated values.

When the sum is below target, increment left; otherwise decrement right, because only those respective moves can bring the sorted pair sum toward target.

Complexitythe cubic scan is the cost of choosing two fixed positions

MEASURE	BOUND	WHY
Time	O(n^3)	Sorting costs O(n log n). The outer index i has O(n) choices, the inner index j has O(n) choices, and each fixed pair performs an O(n) inward scan; the pointers only move inward, so one scan does not revisit an index. The cubic term dominates.
Space	O(log n) extra	The answer itself is required output and is excluded. Apart from it, the scan stores only a fixed number of indices and sum variables; std::sort may use O(log n) recursion stack space, so the bound is O(log n) and does not degrade for any arrangement of the input.

Here n is the length of nums. The number of returned quadruplets is output storage and is excluded from the extra-space bound.

Annotated solutionC++ · sorted nested choices with a two-pointer suffix scan

CPPSort once, choose the first two values, and scan the remaining pair from both ends.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());

        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1;
                int right = n - 1;

                while (left < right) {
                    long long sum = 1LL * nums[i] + nums[j]
                                  + nums[left] + nums[right];

                    if (sum == target) {
                        ans.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;

                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return ans;
    }
};

The duplicate checks belong at three different moments. The i check prevents repeating the first value, the j check prevents repeating the second value for the same i, and the two checks after a match prevent repeating either member of the final pair. Skipping only at the outer loops is not enough: repeated left or right values can still append the same quadruplet multiple times.