How do you solve 4Sum?

Sort nums. Use two nested loops to fix the first two numbers (i and j). For each pair, use two pointers (left and right) to find pairs summing to target - nums[i] - nums[j]. Move pointers inward based on comparison with the remaining target, skipping duplicates to ensure unique quadruplets. Collect all valid quadruplets in the result list and return it.

What pattern does 4Sum use?

The Pattern: Two Pointers (Nested Loops with Two-Pointer Pair Search) The Heuristic: When searching for k-sum problems, reduce the problem by fixing k-2 elements and use the two-pointer technique to find the remaining pair efficiently, while skipping duplicates to avoid repeated solutions.

4Sum | Two Pointers

Q: What is the time complexity of 4Sum?

O(n^3). Sorting takes O(n log n). The two nested loops run O(n^2) times, and for each pair, the two-pointer search runs in O(n), resulting in O(n^3) total time.

Problem

Given an integer array nums and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that a, b, c, and d are distinct indices and nums[a] + nums[b] + nums[c] + nums[d] == target.

1 ≤ nums.length ≤ 200
−10⁹ ≤ nums[i] ≤ 10⁹
−10⁹ ≤ target ≤ 10⁹

Example

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

Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

The brute-force approach would check all quadruplets, which is O(n^4) and infeasible for large inputs. The optimal approach sorts the array to enable skipping duplicates and uses nested loops combined with a two-pointer technique to find pairs that sum to the remaining target. For example, after fixing nums[i] = -2 and nums[j] = -1, the two pointers search for pairs summing to 3. The algorithm carefully moves pointers inward, skipping duplicates to avoid repeated quadruplets. This process repeats for all valid i and j, efficiently enumerating unique quadruplets.

Approach

Straightforward Solution

A brute-force approach enumerates all quadruplets with four nested loops, resulting in O(n^4) time complexity, which is impractical for larger inputs.

Core Observation

The problem requires finding quadruplets summing to a target, which can be decomposed into fixing two numbers and searching for two others that sum to the remaining target. Sorting the array enables efficient duplicate skipping and two-pointer search.

Path to Optimal

Preview

Sorting the array allows skipping duplicates and applying the two-pointer technique for the innermost pair search. Fixing the first two numbers with nested loops reduces the problem to a two-sum variant solvable in O(n) time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort nums. Use two nested loops to fix the first two numbers (i and j)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^3)

Sorting takes O(n log n). The two nested loops run O(n^2) times, and for each pair, the two-pointer search runs in O(n), resulting in O(n^3) total time.

Space

O(n)

Sorting requires O(n) auxiliary space depending on the sorting algorithm. The output list space is not counted as auxiliary space.

Solution

Python

1class Solution:
  def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
      nums.sort()
      result = []
      n = len(nums)
6
      for i in range(n - 3):
          if i > 0 and nums[i] == nums[i - 1]:
              continue
10
          for j in range(i + 1, n - 2):
              if j > i + 1 and nums[j] == nums[j - 1]:
                  continue
14
              left = j + 1
              right = n - 1
17
              while left < right:
                  current_sum = nums[i] + nums[j] + nums[left] + nums[right]
20
                  if current_sum == target:
                      result.append([nums[i], nums[j], nums[left], nums[right]])
23
                      left += 1
                      right -= 1
26
                      while left < right and nums[left] == nums[left - 1]:
                          left += 1
29
                      while left < right and nums[right] == nums[right + 1]:
                          right -= 1
32
                  elif current_sum < target:
                      left += 1
                  else:
                      right -= 1
37
      return result

Step-by-Step Solution

1

Sort the Array and Initialize Result Container

3nums.sort()
4result = []
5n = len(nums)

Objective

To prepare the input for efficient duplicate skipping and two-pointer searching by sorting, and to create a container for storing valid quadruplets.

Key Insight

Sorting the array is essential because it enables the two-pointer technique and makes duplicate detection straightforward by comparing adjacent elements. Initializing the result list upfront provides a place to accumulate valid quadruplets as they are found.

Interview Quick-Check

Core Logic

Sorting transforms the problem into a structured search space where duplicates are adjacent, enabling efficient skipping.

Common Pitfalls & Bugs

Forgetting to sort the array leads to incorrect duplicate detection and inefficient searching.

2

Fix the First Number and Skip Its Duplicates

To iterate over the array fixing the first number of the quadruplet and skip duplicates to avoid repeated quadruplets starting with the same number.

3

Fix the Second Number and Skip Its Duplicates

To fix the second number of the quadruplet for each fixed first number and skip duplicates to maintain uniqueness.

4

Use Two Pointers to Find Remaining Pair Summing to Target

To use two pointers to efficiently find pairs that, combined with the fixed first and second numbers, sum to the target.

5

Return the List of Unique Quadruplets

To return the accumulated list of unique quadruplets that sum to the target.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 8 Critical

if i > 0 and nums[i] == nums[i - 1]:

Skip duplicate first numbers to avoid repeated quadruplets.

Since the array is sorted, duplicates appear consecutively; skipping repeated values here prevents generating quadruplets with the same first element multiple times.

Line 12 Critical

if j > i + 1 and nums[j] == nums[j - 1]:

Skip duplicate second numbers to avoid repeated quadruplets.

Skipping duplicates at this level prevents quadruplets with the same first two numbers from being counted multiple times, ensuring uniqueness.

Line 3 Critical

nums.sort()

Sort the input array to enable efficient two-pointer searching and duplicate skipping.

Sorting is essential because it structures the data, allowing the two-pointer technique to work correctly and enabling straightforward detection and skipping of duplicates by comparing adjacent elements.

Full line-by-line criticality + rationale for all 26 lines available on Pro.

Test Your Understanding

Why is it necessary to skip duplicates at each level of the nested loops and during the two-pointer search?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct 4Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the 4Sum drill

or drill a free problem

1	`class Solution:`
2	`def fourSum(self, nums: list[int], target: int) -> list[list[int]]:`
3	`nums.sort()`
4	`result = []`
5	`n = len(nums)`
6
7	`for i in range(n - 3):`
8	`if i > 0 and nums[i] == nums[i - 1]:`
9	`continue`
10
11	`for j in range(i + 1, n - 2):`
12	`if j > i + 1 and nums[j] == nums[j - 1]:`
13	`continue`
14
15	`left = j + 1`
16	`right = n - 1`
17
18	`while left < right:`
19	`current_sum = nums[i] + nums[j] + nums[left] + nums[right]`
20
21	`if current_sum == target:`
22	`result.append([nums[i], nums[j], nums[left], nums[right]])`
23
24	`left += 1`
25	`right -= 1`
26
27	`while left < right and nums[left] == nums[left - 1]:`
28	`left += 1`
29
30	`while left < right and nums[right] == nums[right + 1]:`
31	`right -= 1`
32
33	`elif current_sum < target:`
34	`left += 1`
35	`else:`
36	`right -= 1`
37
38	`return result`