Four Sum Problem All Unique Quadruplets in DSA Typescript - Execution Trace

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first number i

↓

Fix second number j

↓

Use two pointers left and right

↓

Calculate sum of nums[i

↓

If sum == target

→Add quadruplet

↓

Move left and right skipping duplicates

↓

If sum < target

→Move left pointer right

↓

If sum > target

→Move right pointer left

↓

Repeat until left >= right

↓

Repeat for all i and j

↓

Return all unique quadruplets

The array is sorted first. Then two nested loops fix the first two numbers. Two pointers find pairs that complete the quadruplet to the target sum, skipping duplicates to ensure uniqueness.

Execution Sample

DSA Typescript

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a,b) => a-b);
  const res: number[][] = [];
  for(let i=0; i<nums.length-3; i++) {
    if(i>0 && nums[i] === nums[i-1]) continue;
    for(let j=i+1; j<nums.length-2; j++) {
      if(j>i+1 && nums[j] === nums[j-1]) continue;
      let left = j+1, right = nums.length-1;
      while(left < right) {
        const sum = nums[i]+nums[j]+nums[left]+nums[right];
        if(sum === target) {
          res.push([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--;
        } else if(sum < target) left++;
        else right--;
      }
    }
  }
  return res;
}

This code finds all unique quadruplets in the array that sum to the target by sorting, fixing two numbers, and using two pointers to find the other two.

Execution Table

Step	Operation	i, j, left, right	Sum	Action	Quadruplets Found	Array State
1	Sort array	-	-	-	[]	[1, 0, -1, 0, -2, 2] → [-2, -1, 0, 0, 1, 2]
2	Fix i=0	i=0	-	-	[]	[-2, -1, 0, 0, 1, 2]
3	Fix j=1	i=0, j=1	-	-	[]	[-2, -1, 0, 0, 1, 2]
4	Set left=2, right=5	i=0, j=1, left=2, right=5	-	-	[]	[-2, -1, 0, 0, 1, 2]
5	Calculate sum	i=0, j=1, left=2, right=5	-2 + -1 + 0 + 2 = -1	sum < target(0), move left++	[]	[-2, -1, 0, 0, 1, 2]
6	left=3, right=5	i=0, j=1, left=3, right=5	-2 + -1 + 0 + 2 = -1	sum < target, move left++	[]	[-2, -1, 0, 0, 1, 2]
7	left=4, right=5	i=0, j=1, left=4, right=5	-2 + -1 + 1 + 2 = 0	sum == target, add quadruplet	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
8	Skip duplicates left and right	left=5, right=4	-	left >= right, end inner while	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
9	Increment j=2	i=0, j=2	-	-	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
10	Set left=3, right=5	i=0, j=2, left=3, right=5	-	-	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
11	Calculate sum	i=0, j=2, left=3, right=5	-2 + 0 + 0 + 2 = 0	sum == target, add quadruplet	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
12	Skip duplicates left and right	left=4, right=4	-	left >= right, end inner while	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
13	Increment j=3	i=0, j=3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
14	left=4, right=5	i=0, j=3, left=4, right=5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
15	Calculate sum	i=0, j=3, left=4, right=5	-2 + 0 + 1 + 2 = 1	sum > target, move right--	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
16	left=4, right=4	left >= right	-	end inner while	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
17	Increment i=1	i=1	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
18	Fix j=2	i=1, j=2	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
19	left=3, right=5	i=1, j=2, left=3, right=5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
20	Calculate sum	i=1, j=2, left=3, right=5	-1 + 0 + 0 + 2 = 1	sum > target, move right--	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
21	left=3, right=4	i=1, j=2, left=3, right=4	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
22	Calculate sum	i=1, j=2, left=3, right=4	-1 + 0 + 0 + 1 = 0	sum == target, add quadruplet	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
23	Skip duplicates left and right	left=4, right=3	-	left >= right, end inner while	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
24	Increment j=3	i=1, j=3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
25	left=4, right=5	i=1, j=3, left=4, right=5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
26	Calculate sum	i=1, j=3, left=4, right=5	-1 + 0 + 1 + 2 = 2	sum > target, move right--	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
27	left=4, right=4	left >= right	-	end inner while	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
28	Increment i=2	i=2	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
29	Fix j=3	i=2, j=3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
30	left=4, right=5	i=2, j=3, left=4, right=5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
31	Calculate sum	i=2, j=3, left=4, right=5	0 + 0 + 1 + 2 = 3	sum > target, move right--	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
32	left=4, right=4	left >= right	-	end inner while	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
33	i=3, loop ends	i=3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]

💡 i reaches 3, loop ends because less than 4 elements remain to form quadruplet

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 7	After Step 11	After Step 22	Final
i	-	0	0	0	0	0	1	3
j	-	-	1	1	1	2	2	3
left	-	-	-	2	4	3	4	-
right	-	-	-	5	5	5	5	-
Quadruplets	[]	[]	[]	[]	[[-2,-1,1,2]]	[[-2,-1,1,2],[-2,0,0,2]]	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Key Moments - 3 Insights

Why do we skip duplicates for i and j indices?

Skipping duplicates for i and j prevents adding the same quadruplet multiple times. See steps 2 and 3 where we continue if nums[i] or nums[j] equals the previous value, ensuring uniqueness.

Why do we move left and right pointers after finding a quadruplet?

After finding a quadruplet, we move left and right pointers skipping duplicates to avoid repeating the same quadruplet. This is shown in step 7 and 11 where left and right pointers move past duplicates.

Why does the inner while loop stop when left >= right?

The two pointers meet or cross when left >= right, meaning no more pairs exist between them. This ends the search for the current i and j. See step 8 and 16 for examples.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what quadruplet is added?

A [-2, -1, 1, 2]

B [-2, 0, 0, 2]

C [-1, 0, 0, 1]

D [-2, 0, 1, 2]

💡 Hint

Check the 'Quadruplets Found' column at step 7 in the execution table.

At which step does the condition left >= right first occur?

A Step 8

B Step 16

C Step 22

D Step 32

💡 Hint

Look for the 'Action' column mentioning 'left >= right' in the execution table.

If the array was not sorted first, what would happen to the quadruplets found?

A They would still be unique

B Duplicates might appear

C No quadruplets would be found

D The algorithm would run faster

💡 Hint

Sorting helps skip duplicates as shown in the concept flow and key moments.

Concept Snapshot

Four Sum Problem:
- Sort array first
- Use two nested loops to fix first two numbers
- Use two pointers to find remaining two numbers
- Skip duplicates for i, j, left, right
- Add quadruplets when sum equals target
- Return all unique quadruplets

Full Transcript

The Four Sum problem finds all unique quadruplets in an array that sum to a target value. First, the array is sorted to help skip duplicates. Then, two nested loops fix the first two numbers. For each pair, two pointers scan the remaining array to find pairs that complete the quadruplet. When the sum matches the target, the quadruplet is added to the result. After adding, pointers move skipping duplicates to avoid repeated quadruplets. The process continues until all quadruplets are found or no more pairs exist. The final result is a list of all unique quadruplets that sum to the target.

Practice

1. What is the main goal of the Four Sum Problem in data structures and algorithms?

easy

A. Sort the array in ascending order

B. Find all unique quadruplets in an array that sum up to a target value

C. Find the maximum element in the array

D. Count the number of pairs that sum to a target

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find all unique sets of four numbers in an array that add up to a given target sum.

2. Step 2: Identify the goal

   The goal is to return all quadruplets without duplicates that sum to the target value.

3. Final Answer:

   Find all unique quadruplets in an array that sum up to a target value -> Option B

4. Quick Check:

   Four Sum Problem = Find quadruplets summing to target [OK]

Hint: Look for four numbers adding exactly to target [OK]

Common Mistakes:

• Confusing with two sum or three sum problems
• Ignoring uniqueness of quadruplets
• Trying to find maximum or minimum instead of sum

2. Which of the following TypeScript function signatures correctly represents a function solving the Four Sum Problem?

easy

A. function fourSum(target: number, nums: number[]): void

B. function fourSum(nums: number): number

C. function fourSum(nums: string[], target: string): string[]

D. function fourSum(nums: number[], target: number): number[][]

Solution

1. Step 1: Analyze the function parameters and return type

   The function should take an array of numbers and a target number, and return an array of quadruplets (arrays of numbers).

2. Step 2: Match the correct signature

   function fourSum(nums: number[], target: number): number[][] matches this: input is number array and target number, output is array of number arrays.

3. Final Answer:

   function fourSum(nums: number[], target: number): number[][] -> Option D

4. Quick Check:

   Correct input/output types = function fourSum(nums: number[], target: number): number[][] [OK]

Hint: Look for input array and output array of arrays [OK]

Common Mistakes:

• Wrong parameter order or types
• Returning single number instead of array of quadruplets
• Using string types instead of number

3. What will be the output of the following TypeScript code snippet?

const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
console.log(fourSum(nums, target));

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  const quadruplets: number[][] = [];
  for (let i = 0; i < nums.length - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < nums.length - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let left = j + 1, right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          quadruplets.push([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--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return quadruplets;
}

medium

A. []

B. [[1, 0, -1, 0], [-2, 2, 0, 0]]

C. [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

D. [[0, 0, 0, 0]]

Solution

1. Step 1: Sort the array and initialize variables

   The array after sorting is [-2, -1, 0, 0, 1, 2]. We use nested loops and two pointers to find quadruplets summing to 0.

2. Step 2: Find all unique quadruplets summing to target

   By iterating and skipping duplicates, the quadruplets found are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

3. Final Answer:

   [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] -> Option C

4. Quick Check:

   Unique quadruplets summing to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array and use two pointers to find quadruplets [OK]

Common Mistakes:

• Not sorting array before processing
• Not skipping duplicates causing repeated quadruplets
• Incorrect pointer movement leading to missed quadruplets

4. Identify the bug in this TypeScript code snippet for the Four Sum Problem:

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  const quadruplets: number[][] = [];
  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      let left = j + 1, right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
          left++;
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return quadruplets;
}

medium

A. Missing checks to skip duplicate elements causing repeated quadruplets

B. Incorrect sorting order of the array

C. Wrong initialization of left and right pointers

D. Returning a single quadruplet instead of all quadruplets

Solution

1. Step 1: Review duplicate handling in loops

   The code does not skip duplicate values for i, j, left, or right indices, which can cause repeated quadruplets in the result.

2. Step 2: Identify missing duplicate checks

   Proper skipping of duplicates after pushing quadruplets and in outer loops is needed to ensure uniqueness.

3. Final Answer:

   Missing checks to skip duplicate elements causing repeated quadruplets -> Option A

4. Quick Check:

   Duplicate skipping missing = Missing checks to skip duplicate elements causing repeated quadruplets [OK]

Hint: Always skip duplicates after finding quadruplets [OK]

Common Mistakes:

• Not skipping duplicates in outer loops
• Not skipping duplicates after pushing quadruplet
• Assuming sorting fixes duplicates automatically

5. Given the array nums = [2, 2, 2, 2, 2] and target 8, what is the correct output of the Four Sum Problem solution that finds all unique quadruplets?

hard

A. [[2, 2, 2, 2]]

B. [[2, 2, 2, 2], [2, 2, 2, 2]]

C. []

D. [[2, 2, 2]]

Solution

1. Step 1: Understand the input and target

   The array has five identical elements 2, and the target sum is 8.

2. Step 2: Find unique quadruplets summing to 8

   Only one unique quadruplet [2, 2, 2, 2] sums to 8. Even though elements repeat, quadruplets must be unique sets.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option A

4. Quick Check:

   Unique quadruplet with sum 8 = [[2, 2, 2, 2]] [OK]

Hint: Check for unique quadruplets even if elements repeat [OK]

Common Mistakes:

• Returning duplicate quadruplets multiple times
• Returning empty list incorrectly
• Confusing triplets with quadruplets