Arrays Playlist: 4-Sum Problem (Brute, Better & Optimal Solutions)

The 4-Sum Problem requires finding all unique quadruplets in an integer array whose elements sum up to a specific target value. Building directly upon the foundational two-pointer logic of the 3-Sum problem, this lesson demonstrates how to optimize a multi-variable search from a naive $O(N^4)$ brute-force implementation down to an $O(N^3)$ optimal two-pointer approach that completely eliminates auxiliary hash sets.

1. Problem Understanding & Core Constraints

Given an array of integers nums and an integer target, you must return all unique quadruplets [nums[i], nums[j], nums[k], nums[l]] such that:

1. Distinct Indices: $i, j, k,$ and $l$ are all pairwise distinct ($i \neq j \neq k \neq l$).
2. Target Condition: $\text{nums}[i] + \text{nums}[j] + \text{nums}[k] + \text{nums}[l] == \text{target}$.
3. No Duplicate Quadruplets: The final result set must contain no repeated quadruplet values, regardless of index ordering.

Note on Variable Overflow: Because the sum involves adding four integers, the intermediate summation can exceed standard 32-bit signed integer bounds ($[-2^{31}, 2^{31}-1]$). To prevent integer overflow, intermediate sums must be computed using 64-bit integer types (long long in C++, long in Java).

2. Core Mental Model: The N-Sum Evolution

To solve $N$-Sum problems efficiently, reduce the search space by converting combinations of dynamic variables into fixed pointers paired with known lookup techniques:

By fixing $N-2$ pointers, any $N$-Sum problem can be reduced to a 2-pointer search on a sorted sequence.

3. Brute Force Approach (4-Loop Combination)

Intuition

The most naive approach generates all possible combinations of 4 distinct indices using four nested loops (i, j, k, l). For every combination:

1. Compute the sum.
2. If the sum equals target, sort the quadruplet to establish a canonical order.
3. Insert the sorted quadruplet into a global lookup set (std::set / HashSet) to automatically discard duplicate quadruplets.

Vertical Execution Flow

Code Implementation (C++)

#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSumBrute(vector<int>& nums, int target) {
    int n = nums.size();
    set<vector<int>> st;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    // Accumulate in long long to prevent 32-bit overflow
                    long long sum = (long long)nums[i] + nums[j];
                    sum += nums[k];
                    sum += nums[l];

                    if (sum == target) {
                        vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
                        sort(temp.begin(), temp.end());
                        st.insert(temp);
                    }
                }
            }
        }
    }

    vector<vector<int>> ans(st.begin(), st.end());
    return ans;
}

Complexity Analysis

• Time Complexity: $O(N^4 \times \log(\text{number of quadruplets}))$ — Four nested loops run in $O(N^4)$, and set insertion takes logarithmic time relative to the number of stored quadruplets.
• Space Complexity: $O(2 \times \text{number of unique quadruplets})$ — Memory required for the set and the output list.

4. Pitfall Analysis: Unrestricted Hash Lookup Edge Case

Before moving to a 3-loop solution, it is important to understand why searching for the 4th element across the entire array introduces subtle bugs:

To avoid re-using indices or picking elements outside the active window, any hash set lookup must strictly operate on elements strictly situated between pointers $j$ and $k$.

5. Better Approach (3 Loops + In-Between Hash Set)

Intuition

Eliminate the fourth loop (l) by fixing three pointers (i, j, k) and calculating the exact 4th required value:

Instead of searching the whole array, maintain a dynamic unordered_set that collects elements as $k$ moves forward. This guarantees that any matched 4th element lies strictly between index $j$ and index $k$.

Execution Flow

Code Implementation (C++)

#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSumBetter(vector<int>& nums, int target) {
    int n = nums.size();
    set<vector<int>> st;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            unordered_set<long long> hashset;
            for (int k = j + 1; k < n; k++) {
                long long sum = (long long)nums[i] + nums[j] + nums[k];
                long long fourth = (long long)target - sum;

                if (hashset.find(fourth) != hashset.end()) {
                    vector<int> temp = {(int)nums[i], (int)nums[j], (int)nums[k], (int)fourth};
                    sort(temp.begin(), temp.end());
                    st.insert(temp);
                }
                // Store current element in hashset AFTER checking, making it available for subsequent iterations
                hashset.insert(nums[k]);
            }
        }
    }

    return vector<vector<int>>(st.begin(), st.end());
}

Complexity Analysis

• Time Complexity: $O(N^3 \times \log(\text{set size}))$ — Three nested loops with lookup/insertion operations into the quadruplet set.
• Space Complexity: $O(N) + O(2 \times \text{unique quadruplets})$ — $O(N)$ for the intermediate hash set, plus storage for unique quadruplets.

6. Optimal Approach (Sorting + Two Pointers)

Intuition

To reach optimal efficiency:

1. Eliminate the Hash Set lookup overhead.
2. Eliminate the duplicate-filtering std::set data structure.

By sorting the array upfront, we can fix $i$ and $j$, and use two dynamic pointers ($k$ and $l$) moving toward each other to find target sums in linear time $O(N)$. Duplicate values are skipped natively by checking adjacent elements.

Pointer Layout Mechanics

Sorted Array: [ -2,  -1,   0,   0,   1,   2 ]
                ^     ^    ^              ^
                |     |    |              |
                i     j    k              l
                         (left)        (right)

• If $\text{Sum} == \text{Target}$: Record the quadruplet [nums[i], nums[j], nums[k], nums[l]]. Advance $k$ forward and $l$ backward. Skip all identical values for $k$ and $l$.
• If $\text{Sum} < \text{Target}$: The current total is too small. Increment $k$ ($k++$) to pick a larger value.
• If $\text{Sum} > \text{Target}$: The current total is too large. Decrement $l$ ($l--$) to pick a smaller value.

7. Duplicate Prevention Rules

To avoid redundant quadruplets without using a std::set, skip duplicate values across all four pointers directly in the code:

1. Outer Pointer ($i$):
   • Skip if i > 0 and nums[i] == nums[i - 1].
2. Second Pointer ($j$):
   • Skip if j > i + 1 and nums[j] == nums[j - 1].
3. Inner Dynamic Pointer ($k$):
   • After finding a match, advance k while k < l and nums[k] == nums[k - 1].
4. Inner Dynamic Pointer ($l$):
   • After finding a match, decrement l while k < l and nums[l] == nums[l + 1].

8. Optimal Complete Implementation

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ans;

        // Step 1: Sort the array to enable two-pointer traversal and duplicate skipping
        sort(nums.begin(), nums.end());

        for (int i = 0; i < n; i++) {
            // Skip duplicate values for pointer i
            if (i > 0 && nums[i] == nums[i - 1]) continue;

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

                // Two pointers for the remaining range
                int k = j + 1;
                int l = n - 1;

                while (k < l) {
                    long long sum = (long long)nums[i] + nums[j] + nums[k] + nums[l];

                    if (sum == target) {
                        vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
                        ans.push_back(temp);

                        k++;
                        l--;

                        // Skip duplicate values for pointer k
                        while (k < l && nums[k] == nums[k - 1]) k++;
                        // Skip duplicate values for pointer l
                        while (k < l && nums[l] == nums[l + 1]) l--;
                    } 
                    else if (sum < target) {
                        k++; // Sum too small -> increment left pointer
                    } 
                    else {
                        l--; // Sum too large -> decrement right pointer
                    }
                }
            }
        }

        return ans;
    }
};

9. Algorithmic Complexity Comparison

Summary and Key Takeaways

• Pattern Extension: The 4-Sum problem extends 3-Sum by adding a second fixed loop. In general, an $N$-Sum problem can be solved in $O(N^{k-1})$ time by fixing $k-2$ pointers and using two pointers for the rest.
• Scope Restriction for Hashing: When using hash-based lookups for multi-variable combinations, only insert elements visited within the active loop window (e.g., between $j$ and $k$) to avoid reusing the same indices.
• Sorting Enables Dual Optimizations: Sorting the array up front allows us to use two pointers ($O(N)$ instead of $O(N^2)$ search) and skip duplicates natively without extra memory structures.
• Pointer Skipping Order: Always update dynamic pointers $k$ and $l$ at least once upon finding a valid target sum before triggering while loops to skip adjacent duplicates.
• Preventing Integer Overflow: Always accumulate variable additions into 64-bit integer primitives (long long in C++, long in Java) before comparing against target thresholds.