Skip to main content
Talentd

4Sum - Solution & Explanation

MediumArrayTwo PointersSorting29 min readAsked at: Amazon, Microsoft, Apple +17
Practice this problem

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.

 

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.

In this C solution, a simple bubble sort algorithm is used to sort the array. The quadruplets are found by applying two nested loops fixing two elements and then using the two-pointer technique on the remaining array to find pairs that sum up to the required target. Duplication is avoided by skipping identical elements during iteration.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), where n is the number of elements in the array due to three nested loops.
Space Complexity: O(1), excluding the space required for the output storage.

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.

This solution uses a hash map to store potential pairs and provides an immediate reference to check against the target. Developing all valid pairs without duplicates requires keeping unique property checks on loop iterations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.

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.

Code

PythonJavaC++GoTypeScriptJavaScriptC#PHP

Python

Java

C++

Go

TypeScript

JavaScript

C#

PHP

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 number of elements in the array due to three nested loops.
Space Complexity: O(1), excluding the space required for the output storage.

Approach 2: Hash Map with Two Sum Reduction

Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.

Sorting + Double Pointers—

Detailed 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.

Video Solution

4 Sum | Brute - Better - Optimal with Codes • take U forward • 413,896 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice 4Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

3Sum

Next

4Sum II