Log inSign up
mediumLeetCodeNot Started

4Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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.

---

### Constraints: - 1 <= nums.length <= 200 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9

---

### Important Interview Warning: - Watch out for integer overflow when adding 4 numbers whose values can each be up to 10^9. Use 64-bit integer (long long in C++, long in Java) for intermediate sums.

Example 1 · Example 1 (Zero Target with Mixed Signs):

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Explanation: Distinct quadruplets whose sum equals 0: (-2) + (-1) + 1 + 2 = 0; (-2) + 0 + 0 + 2 = 0; (-1) + 0 + 0 + 1 = 0.

Example 2 · Example 2 (Identical Elements Positive Target):

Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[2, 2, 2, 2]]
Explanation: Only one distinct quadruplet of four 2s sums to 8.

Example 3 · Example 3 (No Valid Quadruplet):

Input: nums = [1, 2, 3, 4], target = 100
Output: []
Explanation: The maximum possible sum is 1 + 2 + 3 + 4 = 10 < 100. No quadruplet can achieve target 100.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing
  • Basic Time & Space Complexity Analysis

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Generalize two-pointer K-sum algorithms from 2Sum and 3Sum to 4Sum.
  • Master multi-level duplicate skipping at outer, middle, and inner pointer steps.
  • Prevent 32-bit integer overflow bugs during intermediate multi-element sum operations.
  • Implement clean, standalone solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • K-Sum problem family (2Sum -> 3Sum -> 4Sum -> K-Sum).
  • Requirement to return unique tuples without duplicates.
  • Target can be negative, zero, or large positive values.

Algorithmic Decision Tree:

  • For 2Sum: Hash Map or Two Pointers (O(N) or O(N log N)).
  • For 3Sum: Sort + 1 Pivot + Two Pointers (O(N2)).
  • For 4Sum: Sort + 2 Pivots + Two Pointers (O(N3)).
  • For K-Sum: Recursively reduce to 2Sum base case with two pointers (O(N^(K-1))).

Connected Patterns:

3Sum: Triplets with target sum 0.3Sum Closest: Finding closest sum to target.4Sum II: Four distinct arrays using hash map pair decomposition.

1. Four Nested Loops with Hash Set (Brute Force)

Intuition

Iterate through every distinct quadruplet index combination (i, j, k, l) and store sorted quadruplets in a set.

Algorithm

  1. 1. Create a set to store unique quadruplets.
  2. 2. Loop i from 0 to N - 1.
  3. 3. Nested loop j from i + 1 to N - 1.
  4. 4. Nested loop k from j + 1 to N - 1.
  5. 5. Nested loop l from k + 1 to N - 1: - If nums[i] + nums[j] + nums[k] + nums[l] == target: sort and insert into set.
  6. 6. Return the list of unique quadruplets.

Brute Force 4-Nested Loops Quadruplet Scan

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-2, -1, 0, 0, 1, 2]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1: Fix indices i=0, j=1, k=2, l=3
Visual state
Values and pointers at this exact step
array
S
-2
-1
0
0
1
2
0
↑ i=0, j=1
1
2
3
↑ k=2, l=3
4
5
Variables at this step
i
0
j
1
k
2
l
3
Sum
-3
Target
0
Match
NO
Check / comparison
nums[0]+nums[1]+nums[2]+nums[3] = -2 + -1 + 0 + 0 = -3 != 0.
Decision / next transition
Sum is -3 != target (0). Advance innermost loop l to index 4.
Why this step matters

Phase 1 — Step 1: Step 1: Fix indices i=0, j=1, k=2, l=3. Quadruplet [-2, -1, 0, 0] sums to -3. No match.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> fourSum(vector<int>& nums, int target) {
17 int n = nums.size();
18 set<vector<int>> st;
19 for (int i = 0; i < n; i++) {
20 for (int j = i + 1; j < n; j++) {
21 for (int k = j + 1; k < n; k++) {
22 for (int l = k + 1; l < n; l++) {
23 long long sum = (long long)nums[i] + nums[j] + nums[k] + nums[l];
24 if (sum == target) {
25 vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
26 sort(quad.begin(), quad.end());
27 st.insert(quad);
28 }
29 }
30 }
31 }
32 }
33 return vector<vector<int>>(st.begin(), st.end());
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {1, 0, -1, 0, -2, 2};
40 int target = 0;
41 vector<vector<int>> res = sol.fourSum(nums, target);
42 cout << "Unique Quadruplets:" << endl;
43 for (const auto& quad : res) {
44 cout << "[" << quad[0] << ", " << quad[1] << ", " << quad[2] << ", " << quad[3] << "] ";
45 }
46 cout << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N^4) — Four nested loops produce N*(N-1)*(N-2)*(N-3)/24 iterations, leading to O(N4) operations.
  • Space complexity: O(2 * K) where K is number of unique quadruplets — A hash set is used to store unique quadruplets.

Why Brute Force Doesn't Scale:

For N = 200, N4 = 1,600,000,000 checks which exceeds the standard 1-second limit. By sorting first (O(N log N)), fixing two indices i and j takes O(N2), and finding the remaining two elements with two converging pointers takes O(N). Total operations drop to ~2003 / 24 ≈ 330,000 operations, which runs in less than 5 milliseconds.

At N = 200: Brute Force = ~1.6 billion ops (~15s). Optimal = ~330k ops (< 5ms).

2. Three Loops with Hash Set (Better)

Intuition

Fix indices i, j, k and use a hash set of intermediate elements to look up required fourth element fourth = target - (nums[i] + nums[j] + nums[k]).

Algorithm

  1. 1. Initialize set st for unique quadruplets.
  2. 2. Loop i from 0 to N - 1.
  3. 3. Loop j from i + 1 to N - 1.
  4. 4. Initialize local hash set seen.
  5. 5. Loop k from j + 1 to N - 1: - fourth = target - (nums[i] + nums[j] + nums[k]) - If fourth in seen: sort [nums[i], nums[j], nums[k], fourth] and insert into st. - seen.insert(nums[k])
  6. 6. Return list of quadruplets.

3 Nested Loops + Hash Set Lookup

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-2, -1, 0, 0, 1, 2]
Current operationSTEP 1 OF 7
Phase 1 — HashSet is empty Store 0 in set: Step 1: We reduce complexity by looking up the 4th value in a hash set
Visual state
Values and pointers at this exact step
array
S
-2
-1
0
0
1
2
0
↑ i=0, j=1
1
2
↑ k=2
3
4
5
Variables at this step
Triad Sum
-3
Needed
3
HashSet
{ 0 }
Check / comparison
Fix i=0 (-2), j=1 (-1). At k=2 (0), required 4th = 0 - (-2 + -1 + 0) = 3.
Decision / next transition
HashSet is empty. Store 0 in set.
Why this step matters

Phase 1 — HashSet is empty Store 0 in set: Step 1: We reduce complexity by looking up the 4th value in a hash set. Target remainder is 3. Set {} does not contain 3. Add 0.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> fourSum(vector<int>& nums, int target) {
17 int n = nums.size();
18 set<vector<int>> st;
19 for (int i = 0; i < n; i++) {
20 for (int j = i + 1; j < n; j++) {
21 unordered_set<long long> seen;
22 for (int k = j + 1; k < n; k++) {
23 long long fourth = (long long)target - ((long long)nums[i] + nums[j] + nums[k]);
24 if (seen.find(fourth) != seen.end()) {
25 vector<int> quad = {nums[i], nums[j], nums[k], (int)fourth};
26 sort(quad.begin(), quad.end());
27 st.insert(quad);
28 }
29 seen.insert(nums[k]);
30 }
31 }
32 }
33 return vector<vector<int>>(st.begin(), st.end());
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {1, 0, -1, 0, -2, 2};
40 int target = 0;
41 vector<vector<int>> res = sol.fourSum(nums, target);
42 cout << "Unique Quadruplets:" << endl;
43 for (const auto& quad : res) {
44 cout << "[" << quad[0] << ", " << quad[1] << ", " << quad[2] << ", " << quad[3] << "] ";
45 }
46 cout << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N^3 * log(no. of unique quadruplets)) — Three nested loops yield O(N3) time. Hash set lookups run in O(1) average time.
  • Space complexity: O(N) for hash set + O(2 * K) for output set — Local hash set consumes O(N) memory.

3. Sorting + Two Fixed Pivots + Two Pointers (Optimal)

Intuition

Sort the array, fix pivot indices i and j, then use converging pointers left and right with duplicate skipping to achieve O(N3) time and O(1) extra space.

Algorithm

  1. 1. Sort array nums in ascending order.
  2. 2. Loop i from 0 to N - 4: - If i > 0 and nums[i] == nums[i-1], continue. - Loop j from i + 1 to N - 3: - If j > i + 1 and nums[j] == nums[j-1], continue. - left = j + 1, right = N - 1. - While left < right: - sum = (long long)nums[i] + nums[j] + nums[left] + nums[right] - If sum < target: left++ - Else if sum > target: right-- - Else: ans.push_back([nums[i], nums[j], nums[left], nums[right]]), left++, right--, skip duplicate nums[left] and nums[right].
  3. 3. Return ans.

Sort + Two Nested Loops + Two Pointers (L & R)

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [-2, -1, 0, 0, 1, 2]
Current operationSTEP 1 OF 8
Phase 1 — Step 1: Step 1: Sort array
Visual state
Values and pointers at this exact step
array
S
-2
-1
0
0
1
2
0
↑ i=0, j=1
1
2
↑ L=2
3
4
5
↑ R=5
Variables at this step
i
0
j
1
L
2
R
5
Sum
-1
Target
0
Action
L++
Check / comparison
Sum = nums[i]+nums[j]+nums[L]+nums[R] = -2 + -1 + 0 + 2 = -1 < 0.
Decision / next transition
Sum (-1) < target (0). Advance left pointer L to increase sum.
Why this step matters

Phase 1 — Step 1: Step 1: Sort array. Fix i=0 (-2), j=1 (-1). Pointers L=2 (0), R=5 (2). Current sum is -1. Too small, increment L.

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> fourSum(vector<int>& nums, int target) {
17 int n = nums.size();
18 vector<vector<int>> ans;
19 sort(nums.begin(), nums.end());
20
21 for (int i = 0; i < n; i++) {
22 if (i > 0 && nums[i] == nums[i - 1]) continue;
23 for (int j = i + 1; j < n; j++) {
24 if (j > i + 1 && nums[j] == nums[j - 1]) continue;
25 int left = j + 1, right = n - 1;
26 while (left < right) {
27 long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
28 if (sum < target) {
29 left++;
30 } else if (sum > target) {
31 right--;
32 } else {
33 ans.push_back({nums[i], nums[j], nums[left], nums[right]});
34 left++;
35 right--;
36 while (left < right && nums[left] == nums[left - 1]) left++;
37 while (left < right && nums[right] == nums[right + 1]) right--;
38 }
39 }
40 }
41 }
42 return ans;
43 }
44};
45
46int main() {
47 Solution sol;
48 vector<int> nums = {1, 0, -1, 0, -2, 2};
49 int target = 0;
50 vector<vector<int>> res = sol.fourSum(nums, target);
51 cout << "Unique Quadruplets:" << endl;
52 for (const auto& quad : res) {
53 cout << "[" << quad[0] << ", " << quad[1] << ", " << quad[2] << ", " << quad[3] << "] ";
54 }
55 cout << endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N log N + N^3) = O(N^3) — Sorting takes O(N log N). The two outer loops run O(N2) times and the inner two-pointer scan runs in O(N) time, yielding O(N3) overall.
  • Space complexity: O(1) auxiliary (or O(log N) for sorting stack) — No extra data structures or hash sets are allocated; quadruplets are filtered in-place.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.1. 4 Nested Loops (Brute Force)O(N^4)O(N)Test every combination of 4 elements and store sorted tuples in a set.Quad-nested loop takes 2004 = 1.6 billion operations.
2.2. 3 Loops + Hash Set (Better)O(N^3)O(N)Fix 3 elements and check for the 4th element (target - sum3) in a hash set.Hash set overhead and memory allocation.
3.3. Sort + 2 Pivots + Two Pointers (Optimal)OptimalO(N^3)O(1) auxiliarySort array, fix i and j, use two pointers for remaining pair with inline duplicate pruning.Optimal bound for general 4Sum on a single array.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Failing to use 64-bit integer (long long / long) for the sum calculation: Causes negative overflow on test cases like [1000000000, 1000000000, 1000000000, 1000000000].

Pitfall 2:

Skipping duplicates on index j with nums[j] == nums[j-1] without checking j > i + 1: Skips valid pairs where nums[i] == nums[j].

Pitfall 3:

Incrementing only left pointer without decrementing right pointer after a match.

Crucial Edge Cases to Validate:

  • Array with length < 4: Immediately returns empty list.
  • Target with potential 32-bit integer overflow: Long long casts prevent arithmetic overflow bugs.
  • Array where all elements are identical (e.g. [2, 2, 2, 2, 2] target 8): Duplicate skipping returns exactly one quadruplet [[2, 2, 2, 2]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly mention using 64-bit integers to guard against overflow — interviewers love this attention to detail.
  2. Demonstrate how sorting enables in-place duplicate removal without allocating a Hash Set.
  3. Mention how this generalizes to K-Sum using recursion.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for undefined?

2.Why is the brute force approach suboptimal for large inputs in undefined?

3.Which data structure or technique enables the optimal solution for undefined?

Back to DSA Sheet