18. 4Sum

4Sum (LeetCode 18) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

• NeetCode 250 · #31 of 250 · Two Pointers

How to solve 4Sum

4Sum is a Converging Two Pointers problem, part of Two Pointers. Learn converging two pointers for sorted arrays. Solve two sum, three sum, and container problems efficiently.

Work towards the solution in these steps:

1. Start by considering how sorting the array can help simplify the problem and avoid duplicate quadruplets.
2. Think about fixing two elements and then using a two-pointer approach to find the other two elements that sum up to the remaining target.
3. Use a nested loop to iterate over the first two elements, and inside that, apply the two-pointer technique on the sorted array for the last two elements.

The reference solution runs in O(n^3) time and O(k) space.

The 4Sum solution and editorial walks through the full approach with reference code.

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

Topics and companies

Topics: Array, Two Pointers, Sorting.

Reported in interviews at Amazon, Bloomberg.

How to practise 4Sum on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^3) time and O(k) space.

Open 4Sum in the code editor, or read the 4Sum editorial for a worked solution with its approach and complexity analysis.

Where 4Sum sits in the DSA pattern sheet

• Two Pointers pattern guide
• Converging (Sorted Array Target Sum) subpattern
• The full DSA patterns sheet

Problems related to 4Sum

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

• Boats to Save People — Medium, same subpattern
• Container With Most Water — Medium, same subpattern
• Squares of a Sorted Array — Easy, same subpattern
• 3Sum Closest — Medium, same subpattern
• 3Sum Smaller — Medium, same subpattern
• 3Sum — Medium, same subpattern

4Sum FAQ