DSA SheetMedium
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

4Sum

MediumEditorial · 8 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A sorted array with two fixed indices and two inward-moving pointersA sorted row of array values has i and then j marked as the two fixed positions. In the suffix after j, left is marked near the beginning and right at the end, so the two pointers face inward. A note beside the row says that a sum below target moves left to the right, while a sum above target moves right to the left. The picture emphasizes that each pointer move changes the sum in the needed direction without skipping a possible pair.122357791113Sorted array — values increase left → right0123456789i (fixed)j (fixed)left starts at j + 1right starts at lastsum < target: move left →sum > target: move right ←current sum = 23 < target 24Only left moving right can increase the sum; only right moving left can decrease it.

Approach

  1. Sort nums so every quadruplet has one ordered representation and equal values become adjacent, which makes duplicate prevention possible with local comparisons.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(log n) extraThe 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.

Common mistakestwo lines that make otherwise convincing submissions fail

Previous · 3Sum Closest