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

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first number i

↓

Fix second number j

↓

Set left = j+1, right = end

↓

While left < right

↓

Calculate sum

↓

sum == target?

Yes→Add quadruplet

| No↓

sum < target?

Yes→left++

| No↓

right--

↓

Skip duplicates for i, j, left, right

↓

Repeat until all quadruplets found

↓

Return all unique quadruplets

We sort the array, then use two nested loops to fix the first two numbers. For the remaining two numbers, we use two pointers moving inward to find pairs that sum to the target minus the fixed numbers, skipping duplicates to ensure uniqueness.

Execution Sample

DSA Javascript

function fourSum(nums, target) {
  nums.sort((a,b) => a-b);
  const res = [];
  const n = nums.length;
  for(let i=0; i<n-3; i++) {
    if(i > 0 && nums[i] === nums[i-1]) continue;
    for(let j=i+1; j<n-2; j++) {
      if(j > i+1 && nums[j] === nums[j-1]) continue;
      let left = j+1, right = n-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 with duplicate skips, and using two pointers for the other two.

Execution Table

Step	Operation	i, j, left, right	Sum	Action	Quadruplets Found	Visual State
1	Sort array	-	-	-	[]	[1, 0, -1, 0, -2, 2] → [-2, -1, 0, 0, 1, 2]
2	Fix i=0	i=0	-	-	[]	i=0 → nums[i]=-2
3	Fix j=1	i=0, j=1	-	-	[]	j=1 → nums[j]=-1
4	Set left=2, right=5	i=0, j=1, left=2, right=5	-	-	[]	left=2 → 0, right=5 → 2
5	Calculate sum	i=0, j=1, left=2, right=5	-2 + -1 + 0 + 2 = -1	sum < target(0)	[]	No quadruplet, move left++
6	Move left	i=0, j=1, left=3, right=5	-	-	[]	left=3 → 0
7	Calculate sum	i=0, j=1, left=3, right=5	-2 + -1 + 0 + 2 = -1	sum < target(0)	[]	No quadruplet, move left++
8	Move left	i=0, j=1, left=4, right=5	-	-	[]	left=4 → 1
9	Calculate sum	i=0, j=1, left=4, right=5	-2 + -1 + 1 + 2 = 0	sum == target	[[-2,-1,1,2]]	Add quadruplet, skip duplicates, left++, right--
10	Skip duplicates left	i=0, j=1, left=5, right=4	-	-	[[-2,-1,1,2]]	left=5, right=4 → left >= right, exit while
11	Increment j	i=0, j=2	-	-	[[-2,-1,1,2]]	j=2 → nums[j]=0
12	Set left=3, right=5	i=0, j=2, left=3, right=5	-	-	[[-2,-1,1,2]]	left=3 → 0, right=5 → 2
13	Calculate sum	i=0, j=2, left=3, right=5	-2 + 0 + 0 + 2 = 0	sum == target	[[-2,-1,1,2],[-2,0,0,2]]	Add quadruplet, skip duplicates, left++, right--
14	Skip duplicates left	i=0, j=2, left=4, right=4	-	-	[[-2,-1,1,2],[-2,0,0,2]]	left=4, right=4 → left >= right, exit while
15	Increment j	i=0, j=3	-	-	[[-2,-1,1,2],[-2,0,0,2]]	j=3 → nums[j]=0 (duplicate j skip in next iteration)
16	Increment i	i=1	-	-	[[-2,-1,1,2],[-2,0,0,2]]	i=1 → nums[i]=-1
17	Fix j=2	i=1, j=2	-	-	[[-2,-1,1,2],[-2,0,0,2]]	j=2 → nums[j]=0
18	Set left=3, right=5	i=1, j=2, left=3, right=5	-	-	[[-2,-1,1,2],[-2,0,0,2]]	left=3 → 0, right=5 → 2
19	Calculate sum	i=1, j=2, left=3, right=5	-1 + 0 + 0 + 2 = 1	sum > target(0)	[[-2,-1,1,2],[-2,0,0,2]]	sum > target, move right--
20	Move right	i=1, j=2, left=3, right=4	-	-	[[-2,-1,1,2],[-2,0,0,2]]	right=4 → 1
21	Calculate sum	i=1, j=2, left=3, right=4	-1 + 0 + 0 + 1 = 0	sum == target	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	Add quadruplet, skip duplicates, left++, right--
22	Skip duplicates left	i=1, j=2, left=4, right=3	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	left=4, right=3 → left >= right, exit while
23	Increment j	i=1, j=3	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	j=3 → nums[j]=0 (duplicate j skip in next iteration)
24	Increment i	i=2	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	i=2 → nums[i]=0
25	Fix j=3	i=2, j=3	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	j=3 → nums[j]=0
26	Set left=4, right=5	i=2, j=3, left=4, right=5	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	left=4 → 1, right=5 → 2
27	Calculate sum	i=2, j=3, left=4, right=5	0 + 0 + 1 + 2 = 3	sum > target(0)	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	sum > target, move right--
28	Move right	i=2, j=3, left=4, right=4	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	right=4 → 1
29	left >= right	i=2, j=3, left=4, right=4	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	left >= right, exit while
30	End loops	-	-	-	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	All quadruplets found, return result

💡 All quadruplets found or loops exhausted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 9	After Step 13	After Step 21	Final
i	-	0	0	0	0	1	2
j	-	-	1	1	2	2	3
left	-	-	-	4	4	4	4
right	-	-	-	5	5	4	4
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, j, left, and right pointers?

Skipping duplicates prevents adding the same quadruplet multiple times. For example, after adding a quadruplet, we move left and right pointers past any identical numbers (see steps 9 and 13 in execution_table). This ensures uniqueness.

Why do we use two pointers (left and right) after fixing i and j?

Two pointers efficiently find pairs that sum to the remaining target. Instead of nested loops, moving left and right inward adjusts the sum to reach the target quickly (see steps 5-10).

What happens when left pointer crosses right pointer?

When left >= right, it means all pairs for current i and j are checked. We then move to the next j or i (see steps 10, 14, 22, 29).

Visual Quiz - 3 Questions

Look at the execution_table at step 9. What quadruplet is added to the result?

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

B [-2, 0, 0, 2]

C [-1, 0, 0, 1]

D [0, 0, 1, 2]

💡 Hint

Check the 'Quadruplets Found' column at step 9 in execution_table.

At which step does the left pointer first move from index 2 to 3?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'left' pointer changes in execution_table between steps 5 and 8.

If the array was not sorted, how would the execution_table change?

A The two-pointer approach would not work correctly, so quadruplets might be missed or duplicated.

B The quadruplets would be found faster.

C The sum calculation would be different.

D No change; sorting is optional.

💡 Hint

Refer to the concept_flow where sorting is the first step before two-pointer usage.

Concept Snapshot

Four Sum Problem:
- Sort the array first.
- Fix two numbers with nested loops (i, j).
- Use two pointers (left, right) to find pairs summing to target - nums[i] - nums[j].
- Skip duplicates for i, j, left, right to ensure unique quadruplets.
- Return all unique quadruplets found.

Full Transcript

The Four Sum problem finds all unique sets of four numbers in an array that add up to a target sum. We start by sorting the array to make it easier to avoid duplicates and use the two-pointer technique. We fix the first two numbers using nested loops, then use two pointers to find the remaining two numbers that complete the quadruplet. We carefully skip duplicates at every step to ensure each quadruplet is unique. The process continues until all quadruplets are found or all combinations are checked. This method is efficient and avoids unnecessary repeated work.

Practice

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

easy

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

B. Sort the array in ascending order

C. Find the maximum element in the array

D. Count the number of pairs with a given sum

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Differentiate from other problems

   This is different from sorting, finding max, or counting pairs because it specifically looks for quadruplets with a sum equal to the target.

3. Final Answer:

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

4. Quick Check:

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

Hint: Look for four numbers adding to target, not sorting or max [OK]

Common Mistakes:

• Confusing with sorting or max element problems
• Looking for pairs instead of quadruplets
• Ignoring uniqueness of quadruplets

2. Which of the following is the correct way to start sorting an array nums in JavaScript before solving the Four Sum Problem?

easy

A. nums.sort()

B. nums.sort((a, b) => b - a)

C. nums.sorted()

D. nums.sort((a, b) => a - b)

Solution

1. Step 1: Understand JavaScript sort behavior

   By default, nums.sort() sorts elements as strings, which can give wrong order for numbers.

2. Step 2: Use numeric comparison function

   Using nums.sort((a, b) => a - b) sorts numbers in ascending order correctly, which is needed for the Four Sum algorithm.

3. Final Answer:

   nums.sort((a, b) => a - b) -> Option D

4. Quick Check:

   Numeric ascending sort = nums.sort((a, b) => a - b) [OK]

Hint: Use numeric compare function for sorting numbers [OK]

Common Mistakes:

• Using default sort without compare function
• Using descending order when ascending is needed
• Using non-existent method like sorted()

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

const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
// Assume findFourSum returns all unique quadruplets summing to target
const result = findFourSum(nums, target);
console.log(result);

Given findFourSum correctly implements the Four Sum algorithm, what is the expected output?

medium

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

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

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

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

Solution

1. Step 1: Sort the array and find quadruplets

   Sorted array is [-2, -1, 0, 0, 1, 2]. The unique quadruplets summing to 0 are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

2. Step 2: Verify quadruplets sum to target

   Each quadruplet sums to 0, matching the target, and all are unique sets.

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort array first, then find quadruplets summing to target [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate quadruplets
• Incorrect quadruplet sums

4. Identify the error in the following snippet for solving the Four Sum Problem:

function fourSum(nums, target) {
  nums.sort();
  const quadruplets = [];
  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      let left = j + 1;
      let 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. The loops do not cover all indices correctly

B. The array is not sorted numerically before processing

C. The quadruplets array is not returned

D. The sum calculation is incorrect

Solution

1. Step 1: Check sorting method

   The code uses nums.sort() without a compare function, which sorts elements as strings, causing incorrect order for numbers.

2. Step 2: Impact on algorithm correctness

   Incorrect sorting leads to wrong quadruplets or missed solutions because the two-pointer approach depends on sorted numeric order.

3. Final Answer:

   The array is not sorted numerically before processing -> Option B

4. Quick Check:

   Missing numeric sort compare function = The array is not sorted numerically before processing [OK]

Hint: Always use numeric compare in sort for number arrays [OK]

Common Mistakes:

• Using default sort without compare function
• Not returning the result array
• Incorrect loop ranges (not here though)
• Wrong sum calculation (correct here)

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

hard

A. [[2, 2, 2]]

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

C. [[2, 2, 2, 2]]

D. []

Solution

1. Step 1: Understand the input and target

   All elements are 2, and target is 8. Four 2's sum to 8 exactly.

2. Step 2: Identify unique quadruplets

   Even though there are multiple 2's, only one unique quadruplet [2, 2, 2, 2] exists that sums to 8.

3. Final Answer:

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

4. Quick Check:

   Unique quadruplet summing to 8 = [[2, 2, 2, 2]] [OK]

Hint: Duplicates form one unique quadruplet if sum matches target [OK]

Common Mistakes:

• Listing duplicate quadruplets multiple times
• Returning empty when quadruplet exists
• Confusing triplets with quadruplets