Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

4Sum solution and explanation

MediumArraySortingTwo Pointers6 min read42.0% acceptanceUpdated 9 Apr 2026
Asked atCapgeminiSinglestoreCloudflareGoogleAmazonMeta
+14 moreBloombergNVIDIAMicrosoftTCSInfosysServiceNowAppleZohoAccentureYandexD. E. ShawDoorDashRubrikLinkedIn
Practise 4Sum
28:47
4 Sum | Brute - Better - Optimal with Codestake U forward · 28:47 · 413K viewsWatch on YouTube
9 more videos on this problem
  1. 4 Sum | Brute - Better - Optimal with Codestake U forward · 28:47 · 413K views
  2. 4Sum - Leetcode 18 - PythonNeetCode · 15:28 · 122K views
  3. 4 Sum Problem | Leetcode #18Techdose · 24:30 · 60K views
  4. 4Sum - Leetcode 18 - Two Pointers (Python)Greg Hogg · 4:05 · 12K views
  5. LeetCode 18 | 4Sum | Solution Explained (Java + Whiteboard)Xavier Elon · 11:14 · 10K views
  6. Hard Microsoft Coding Interview Question - 4Sum - LeetCode 18AlgoJS · 6:15 · 8K views
  7. [LeetCode]18. 4Sum 中文山景城一姐 · 6:25 · 2K views
  8. Python Leetcode Solution 18: 4SumNian Li · 11:03 · 2K views
  9. Leetcode 18. 4Sum, PythonNeedCode⚡ · 11:10 · 993 views
  10. 4Sum Python Solution - LeetCode #18Professor Oakes · 8:21 · 885 views

The problem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

Approach overview

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.

Approach 1: Approach 1: Sort and Two-pointer Technique

This approach employs sorting the array and fixing two pointers while searching for the other two via a two-pointer method. This reduces the dimensionality of the problem stepwise.

  1. Sort the input array.
  2. Fix the first two elements one by one and then use the two-pointer method for the remaining elements.
  3. Use the sorted nature of the array to avoid going over the same quadruplets more than once, thus skipping duplicates.
def fourSum(nums, target):
    nums.sort()
    results = []
    n = len(nums)
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            k, l = j + 1, n - 1
            while k < l:
                sum_ = nums[i] + nums[j] + nums[k] + nums[l]
                if sum_ == target:
                    results.append([nums[i], nums[j], nums[k], nums[l]])
                    while k < l and nums[k] == nums[k + 1]:
                        k += 1
                    while k < l and nums[l] == nums[l - 1]:
                        l -= 1
                    k += 1
                    l -= 1
                elif sum_ < target:
                    k += 1
                else:
                    l -= 1
    return results

# Example usage
nums = [1, 0, -1, 0, -2, 2]
target = 0
result = fourSum(nums, target)
for r in result:
    print(r)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int k = j + 1, l = n - 1;
                while (k < l) {
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        while (k < l && nums[k] == nums[k + 1]) k++;
                        while (k < l && nums[l] == nums[l - 1]) l--;
                        k++; l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        FourSum solver = new FourSum();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> result = solver.fourSum(nums, target);
        for (List<Integer> res : result) {
            System.out.println(res);
        }
    }
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int k = j + 1, l = n - 1;
            while (k < l) {
                int sum = nums[i] + nums[j] + nums[k] + nums[l];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[k], nums[l]});
                    while (k < l && nums[k] == nums[k + 1]) k++;
                    while (k < l && nums[l] == nums[l - 1]) l--;
                    k++; l--;
                } else if (sum < target) {
                    k++;
                } else {
                    l--;
                }
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> result = fourSum(nums, target);
    for (auto &quad: result) {
        cout << "[";
        for (int i = 0; i < quad.size(); i++) {
            cout << quad[i] << (i == quad.size() - 1 ? "" : ", ");
        }
        cout << "]\n";
    }
    return 0;
}
function fourSum(nums, target) {
    nums.sort((a, b) => a - b);
    const results = [];
    const n = nums.length;
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            let k = j + 1, l = n - 1;
            while (k < l) {
                const sum = nums[i] + nums[j] + nums[k] + nums[l];
                if (sum === target) {
                    results.push([nums[i], nums[j], nums[k], nums[l]]);
                    while (k < l && nums[k] === nums[k + 1]) k++;
                    while (k < l && nums[l] === nums[l - 1]) l--;
                    k++; l--;
                } else if (sum < target) {
                    k++;
                } else {
                    l--;
                }
            }
        }
    }
    return results;
}

// Example Usage
const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
console.log(fourSum(nums, target));
#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes) {
    sort(nums, numsSize);
    int **result = (int **)malloc(sizeof(int *) * 1000);
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(sizeof(int) * 1000);

    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int k = j + 1, l = numsSize - 1;
            while (k < l) {
                int sum = nums[i] + nums[j] + nums[k] + nums[l];
                if (sum == target) {
                    result[*returnSize] = (int *)malloc(sizeof(int) * 4);
                    result[*returnSize][0] = nums[i];
                    result[*returnSize][1] = nums[j];
                    result[*returnSize][2] = nums[k];
                    result[*returnSize][3] = nums[l];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                    while (k < l && nums[k] == nums[k + 1]) k++;
                    while (k < l && nums[l] == nums[l - 1]) l--;
                    k++; l--;
                } else if (sum < target) {
                    k++;
                } else {
                    l--;
                }
            }
        }
    }
    return result;
}

int main() {
    int nums[] = {1, 0, -1, 0, -2, 2};
    int numsSize = sizeof(nums) / sizeof(int);
    int target = 0;
    int returnSize;
    int *returnColumnSizes;
    int **result = fourSum(nums, numsSize, target, &returnSize, &returnColumnSizes);
    for (int i = 0; i < returnSize; i++) {
        printf("[%d, %d, %d, %d]\n", result[i][0], result[i][1], result[i][2], result[i][3]);
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);
    return 0;
}
using System;
using System.Collections.Generic;

class FourSumSolution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        List<IList<int>> result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int k = j + 1, l = n - 1;
                while (k < l) {
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        result.Add(new List<int>{nums[i], nums[j], nums[k], nums[l]});
                        while (k < l && nums[k] == nums[k + 1]) k++;
                        while (k < l && nums[l] == nums[l - 1]) l--;
                        k++; l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        return result;
    }

    static void Main() {
        var solver = new FourSumSolution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var result = solver.FourSum(nums, target);
        foreach (var r in result) {
            Console.WriteLine("[{0}]", string.Join(", ", r));
        }
    }
}

Python offers a succinct implementation using inbuilt list sorting and dynamic arrays. Two-index approach post looping avoids redundant processing of identical sums and handles all possible quadruplet combinations sequentially to match the target.

Complexity

Time Complexity: O(n^3), where n is the length of the array.
Space Complexity: O(n) due to storage requirements for potential duplicates.

Try this approach in the editor

Approach 2: Approach 2: Hash Map with Two Sum Reduction

This method reduces the four-sum problem by first reducing it to a three-sum problem, and then a two-sum problem using hash maps.

  1. Use a nested loop to fix two elements and use a hash map for the remaining part.
  2. Hash map stores required pairs for convenience and direct lookup, helping to skip duplicates.
def fourSum(nums, target):
    nums.sort()
    results = []
    n = len(nums)
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            seen = {}
            for k in range(j + 1, n):
                complement = target - nums[i] - nums[j] - nums[k]
                if complement in seen:
                    results.append([nums[i], nums[j], nums[seen[complement]], nums[k]])
                    while k + 1 < n and nums[k] == nums[k + 1]:
                        k += 1
                seen[nums[k]] = k
    return results

# Example usage
nums = [1, 0, -1, 0, -2, 2]
target = 0
result = fourSum(nums, target)
for r in result:
    print(r)
import java.util.*;

public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                Map<Integer, Integer> map = new HashMap<>();
                for (int k = j + 1; k < n; k++) {
                    if (map.containsKey(nums[k])) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[map.get(nums[k])], nums[k]));
                        while (k + 1 < n && nums[k] == nums[k + 1]) k++;
                    } else {
                        map.put(target - nums[i] - nums[j] - nums[k], k);
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        FourSum fs = new FourSum();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> result = fs.fourSum(nums, target);
        for (List<Integer> quad : result) {
            System.out.println(quad);
        }
    }
}
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            unordered_map<int, int> map;
            for (int k = j + 1; k < n; k++) {
                if (map.count(nums[k])) {
                    result.push_back({nums[i], nums[j], nums[map[nums[k]]], nums[k]});
                    while (k + 1 < n && nums[k] == nums[k + 1]) k++;
                } else {
                    map[target - nums[i] - nums[j] - nums[k]] = k;
                }
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> result = fourSum(nums, target);
    for (auto &quad : result) {
        cout << "[";
        for (int i = 0; i < quad.size(); i++) {
            cout << quad[i] << (i == quad.size() - 1 ? "" : ", ");
        }
        cout << "]\n";
    }
    return 0;
}
function fourSum(nums, target) {
    nums.sort((a, b) => a - b);
    const results = [];
    const n = nums.length;
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            const seen = {};
            for (let k = j + 1; k < n; k++) {
                const complement = target - nums[i] - nums[j] - nums[k];
                if (seen[complement] !== undefined) {
                    results.push([nums[i], nums[j], nums[k], complement]);
                    while (k + 1 < n && nums[k] === nums[k + 1]) k++;
                }
                seen[nums[k]] = k;
            }
        }
    }
    return results;
}

// Example Usage
const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
console.log(fourSum(nums, target));
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 10007

struct ListNode {
    int val;
    struct ListNode *next;
};

void insert(struct ListNode **hashTable, int key, int val) {
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->val = val;
    int index = abs(key % HASH_SIZE);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

struct ListNode *search(struct ListNode **hashTable, int key) {
    int index = abs(key % HASH_SIZE);
    return hashTable[index];
}

void freeList(struct ListNode *head) {
    while (head) {
        struct ListNode *temp = head;
        head = head->next;
        free(temp);
    }
}

int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes) {
    *returnSize = 0;
    int **result = (int **)malloc(1000 * sizeof(int *));
    *returnColumnSizes = (int *)malloc(1000 * sizeof(int));
    int *temp = (int *)malloc(4 * sizeof(int));

    struct ListNode *hashTable[HASH_SIZE];
    memset(hashTable, 0, sizeof(hashTable));

    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int complement = target - nums[i] - nums[j];
            struct ListNode *node = search(hashTable, complement);
            while (node) {
                int k = node->val;
                if (nums[k] != nums[j] && nums[j] != nums[i]) {
                    temp[0] = nums[i];
                    temp[1] = nums[j];
                    temp[2] = nums[k];
                    temp[3] = complement - nums[k];
                    result[*returnSize] = (int *)malloc(4 * sizeof(int));
                    memcpy(result[*returnSize], temp, 4 * sizeof(int));
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                }
                node = node->next;
            }
            insert(hashTable, nums[j], j);
        }
    }

    for (int i = 0; i < HASH_SIZE; i++) {
        freeList(hashTable[i]);
    }
    free(temp);
    return result;
}

int main() {
    int nums[] = {1, 0, -1, 0, -2, 2};
    int numsSize = sizeof(nums) / sizeof(int);
    int target = 0;
    int returnSize;
    int *returnColumnSizes;
    int **result = fourSum(nums, numsSize, target, &returnSize, &returnColumnSizes);
    for (int i = 0; i < returnSize; i++) {
        printf("[%d, %d, %d, %d]\n", result[i][0], result[i][1], result[i][2], result[i][3]);
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);
    return 0;
}
using System;
using System.Collections.Generic;

class FourSumSolution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        List<IList<int>> result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                HashSet<int> seen = new HashSet<int>();
                for (int k = j + 1; k < n; k++) {
                    int complement = target - nums[i] - nums[j] - nums[k];
                    if (seen.Contains(complement)) {
                        result.Add(new List<int>{nums[i], nums[j], nums[k], complement});
                        while (k + 1 < n && nums[k] == nums[k + 1]) k++;
                    }
                    seen.Add(nums[k]);
                }
            }
        }
        return result;
    }

    static void Main() {
        var solver = new FourSumSolution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var result = solver.FourSum(nums, target);
        foreach (var r in result) {
            Console.WriteLine("[{0}]", string.Join(", ", r));
        }
    }
}

Python's solution with hash maps avails quicker comparison for each pair of sums, thus regularly reviewing progress without overlap. Element recurrence detection uses dictionary keys.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n), derived from hash table demands.

Try this approach in the editor

Approach 3: Sorting + Double Pointers

We notice that the problem requires us to find non-repeating quadruplets. Therefore, we can first sort the array, which makes it easy to skip duplicate elements.

Next, we enumerate the first two elements of the quadruplet, nums[i] and nums[j], where i \lt j. During the enumeration process, we skip duplicate nums[i] and nums[j]. Then, we use two pointers k and l to point to the two ends behind nums[i] and nums[j]. Let x = nums[i] + nums[j] + nums[k] + nums[l], we compare x with target and perform the following operations:

  • If x \lt target, then update k = k + 1 to get a larger x;
  • If x \gt target, then update l = l - 1 to get a smaller x;
  • Otherwise, it means that a quadruplet (nums[i], nums[j], nums[k], nums[l]) is found. Add it to the answer, then we update the pointers k and l, and skip all duplicate elements to prevent the answer from containing duplicate quadruplets, and continue to find the next quadruplet.

The time complexity is O(n^3), and the space complexity is O(log n). Here, n is the length of the array.

function fourSum(nums: number[], target: number): number[][] {
    const n = nums.length;
    const ans: number[][] = [];
    if (n < 4) {
        return ans;
    }
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            let [k, l] = [j + 1, n - 1];
            while (k < l) {
                const x = nums[i] + nums[j] + nums[k] + nums[l];
                if (x < target) {
                    ++k;
                } else if (x > target) {
                    --l;
                } else {
                    ans.push([nums[i], nums[j], nums[k++], nums[l--]]);
                    while (k < l && nums[k] === nums[k - 1]) {
                        ++k;
                    }
                    while (k < l && nums[l] === nums[l + 1]) {
                        --l;
                    }
                }
            }
        }
    }
    return ans;
}
func fourSum(nums []int, target int) (ans [][]int) {
	n := len(nums)
	if n < 4 {
		return
	}
	sort.Ints(nums)
	for i := 0; i < n-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < n-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			k, l := j+1, n-1
			for k < l {
				x := nums[i] + nums[j] + nums[k] + nums[l]
				if x < target {
					k++
				} else if x > target {
					l--
				} else {
					ans = append(ans, []int{nums[i], nums[j], nums[k], nums[l]})
					k++
					l--
					for k < l && nums[k] == nums[k-1] {
						k++
					}
					for k < l && nums[l] == nums[l+1] {
						l--
					}
				}
			}
		}
	}
	return
}
class Solution {
    /**
     * @param int[] $nums
     * @param int $target
     * @return int[][]
     */

    function fourSum($nums, $target) {
        $result = [];
        $n = count($nums);

        sort($nums);

        for ($i = 0; $i < $n - 3; $i++) {
            if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
                continue;
            }

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

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

                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];

                    if ($sum === $target) {
                        $result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];

                        while ($left < $right && $nums[$left] === $nums[$left + 1]) {
                            $left++;
                        }

                        while ($left < $right && $nums[$right] === $nums[$right - 1]) {
                            $right--;
                        }

                        $left++;
                        $right--;
                    } elseif ($sum < $target) {
                        $left++;
                    } else {
                        $right--;
                    }
                }
            }
        }
        return $result;
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Sort and Two-pointer Technique

Time Complexity: O(n^3), where n is the length of the array.
Space Complexity: O(n) due to storage requirements for potential duplicates.

Approach 2: Hash Map with Two Sum Reduction

Time Complexity: O(n^2)
Space Complexity: O(n), derived from hash table demands.

Sorting + Double Pointers–

Complexity analysis

ApproachTimeSpaceWhen to Use
Sort + Two PointersO(n^3)O(1)Best general solution. Efficient duplicate handling and common interview pattern.
Hash Map with Two Sum ReductionO(n^3)O(n)Useful when using hash-based complement lookup or extending the Two Sum pattern.

Frequently asked questions

Is 4Sum easy or hard?

4Sum is generally classified as a medium-level problem. The logic becomes straightforward if you already understand the 3Sum pattern, but handling duplicates and maintaining O(n^3) efficiency can make the implementation tricky.

How to solve 4Sum in O(n)?

Solving 4Sum in O(n) time is not possible for the general unsorted case because the algorithm must consider combinations of four elements. The best commonly accepted complexity is O(n^3) using sorting and the two-pointer technique.

What is the best approach for 4Sum?

The most common solution sorts the array and then fixes two indices while using a two-pointer search for the remaining pair. This reduces the problem from four nested loops to O(n^3) time after sorting. Duplicate skipping ensures each quadruplet appears only once.

What data structure is used in 4Sum?

Arrays are the primary structure since the input is a list of numbers. The optimal approach relies on sorting and the two-pointer technique, while an alternative solution may use a hash set or hash map for complement lookups.

What is the time complexity of 4Sum?

The optimal practical solution runs in O(n^3) time. After sorting the array in O(n log n), two nested loops choose the first two numbers and a two-pointer scan finds the remaining pair in linear time.

4Sum Python or Java solution approach?

Most Python and Java solutions first sort the array, then use two nested loops and two pointers to find the remaining pair. The pointer movement adjusts based on whether the current sum is smaller or larger than the target.

Is 4Sum asked at Google, Amazon, or Meta?

4Sum and its variations appear frequently in technical interviews at large companies such as Amazon, Google, and Meta. Interviewers often use it to test understanding of sorting, two pointers, duplicate handling, and how to extend the 2Sum or 3Sum patterns.

Comments

Next problem · similarTwo SumEasy
Now write it yourselfClose this page and solve 4Sum in the editor, without looking.
Practise 4Sum