Bird
Raised Fist0
DSA Javaprogramming~10 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Concept Flow - Four Sum Problem All Unique Quadruplets
Sort the array
↓
Fix first element i
↓
Fix second element j
↓
Use two pointers left and right
↓
Check sum of nums[i
↓
Repeat until left >= right
↓
Move j to next unique element
↓
Move i to next unique element
↓
End when i reaches length-4
The algorithm sorts the array, then uses two nested loops to fix the first two numbers. For the remaining two numbers, it uses two pointers moving inward to find quadruplets that sum to the target, skipping duplicates to ensure uniqueness.
Execution Sample
DSA Java
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
// Find all unique quadruplets that sum to target
This code finds all unique sets of four numbers in the array that add up to zero.
Execution Table
StepOperationi,j,left,rightSumQuadruplet AddedPointer ChangesVisual State
1Sort array----[-2, -1, 0, 0, 1, 2]
2Fix i=0i=0---i=0 (-2)
3Fix j=1i=0, j=1---j=1 (-1)
4Set left=2, right=5i=0, j=1, left=2, right=5---left=2 (0), right=5 (2)
5Calculate sum0,1,2,5-2 + -1 + 0 + 2 = -1Noleft++left=3 (0), right=5 (2)
6Calculate sum0,1,3,5-2 + -1 + 0 + 2 = -1Noleft++left=4 (1), right=5 (2)
7Calculate sum0,1,4,5-2 + -1 + 1 + 2 = 0Yes [-2,-1,1,2]left++, right--left=5, right=4 (stop)
8Move j to next uniquei=0, j=2---j=2 (0)
9Set left=3, right=5i=0, j=2, left=3, right=5---left=3 (0), right=5 (2)
10Calculate sum0,2,3,5-2 + 0 + 0 + 2 = 0Yes [-2,0,0,2]left++, right--left=4 (1), right=4 (stop)
11Move j to next uniquei=0, j=3---j=3 (0) duplicate skipped, move to j=4
12Move j to 4i=0, j=4---j=4 (1)
13Set left=5, right=5i=0, j=4, left=5, right=5---left=5, right=5 (stop)
14Move i to next uniquei=1---i=1 (-1)
15Fix j=2i=1, j=2---j=2 (0)
16Set left=3, right=5i=1, j=2, left=3, right=5---left=3 (0), right=5 (2)
17Calculate sum1,2,3,5-1 + 0 + 0 + 2 = 1Noright--left=3 (0), right=4 (1)
18Calculate sum1,2,3,4-1 + 0 + 0 + 1 = 0Yes [-1,0,0,1]left++, right--left=4, right=3 (stop)
19Move j to next uniquei=1, j=3---j=3 (0) duplicate skipped, move to j=4
20Move j to 4i=1, j=4---j=4 (1)
21Set left=5, right=5i=1, j=4, left=5, right=5---left=5, right=5 (stop)
22Move i to next uniquei=2---i=2 (0)
23Fix j=3i=2, j=3---j=3 (0)
24Set left=4, right=5i=2, j=3, left=4, right=5---left=4 (1), right=5 (2)
25Calculate sum2,3,4,50 + 0 + 1 + 2 = 3Noright--left=4 (1), right=4 (stop)
26Move j to next uniquei=2, j=4---j=4 (1)
27Set left=5, right=5i=2, j=4, left=5, right=5---left=5, right=5 (stop)
28Move i to next uniquei=3---i=3 (0) duplicate skipped, move to i=4
29Move i to 4i=4---i=4 (1)
30Fix j=5i=4, j=5---j=5 (2)
31Set left=6, right=5left > right stop---No valid left/right, stop
32End----i reached length-4, algorithm ends
💡 i reached length-4, no more quadruplets possible
Variable Tracker
VariableStartAfter Step 2After Step 14After Step 22After Step 29Final
i-01244
j-12355
left--334-
right--555-
Quadruplets Found[][[-2,-1,1,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]][[-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 duplicate values for i and j?
Skipping duplicates for i and j avoids adding the same quadruplet multiple times. For example, after adding quadruplets with i=0 and j=2 (value 0), we skip the next j=3 which is also 0 (see steps 11 and 19). This ensures uniqueness as shown in the execution_table.
Why do we move left and right pointers differently based on sum?
If the sum is less than target, moving left pointer right increases sum because array is sorted. If sum is greater, moving right pointer left decreases sum. This is shown in steps 5-7 and 17-18 where pointer moves adjust sum towards target.
Why does the inner while loop stop when left >= right?
When left meets or passes right, all pairs for current i and j are checked. Continuing would repeat or reverse pairs. This stopping condition is shown in steps 7, 10, 18, and 25.
Visual Quiz - 3 Questions
Test your understanding
Look at the execution_table at step 7. What quadruplet was added?
A[-2, -1, 1, 2]
B[-2, 0, 0, 2]
C[-1, 0, 0, 1]
D[0, 0, 1, 2]
💡 Hint
Check the 'Quadruplet Added' column at step 7 in the execution_table.
At which step does the condition left >= right first stop the inner loop?
AStep 7
BStep 10
CStep 18
DStep 25
💡 Hint
Look at the 'Pointer Changes' and 'Visual State' columns to see when left passes right.
If the array was not sorted, how would the pointer movement logic change?
APointers would still move left and right based on sum comparison
BPointer movement would not guarantee finding all quadruplets correctly
CWe would only need one pointer instead of two
DSorting is irrelevant for this algorithm
💡 Hint
Refer to the concept_flow where sorting is the first step before pointer usage.
Concept Snapshot
Four Sum Problem:
- Sort array first
- Use two nested loops to fix first two numbers (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
- Stop inner loop when left >= right
- Time complexity approx O(n^3)
Full Transcript
The Four Sum problem finds all unique quadruplets in an array that sum to a target value. The array is first sorted to allow efficient two-pointer searching. Two nested loops fix the first two numbers, i and j. Then two pointers, left and right, scan the remaining array to find pairs that complete the quadruplet sum. If the sum is less than the target, the left pointer moves right to increase sum. If greater, the right pointer moves left to decrease sum. When the sum equals the target, the quadruplet is added to the result, and pointers move skipping duplicates to avoid repeated quadruplets. The inner loop stops when left meets or passes right. The outer loops also skip duplicates for i and j. This approach ensures all unique quadruplets are found efficiently. The execution table traces each step, showing pointer positions, sums, quadruplets added, and array state. Key moments clarify why duplicates are skipped and how pointer movements work. The visual quiz tests understanding of quadruplet additions, loop stopping conditions, and the importance of sorting.

Practice

(1/5)
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 that sum to a target

Solution

  1. Step 1: Understand the problem statement

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

  2. Step 2: Identify the expected output

    We want all unique quadruplets, meaning no repeated sets, that sum exactly 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 = unique quadruplets summing to target [OK]
Hint: Look for four numbers adding to target without duplicates [OK]
Common Mistakes:
  • Confusing Four Sum 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 Java code snippets correctly initializes an empty list to store quadruplets for the Four Sum problem?
easy
A. List quadruplets = new List<>();
B. List quadruplets = new ArrayList<>();
C. ArrayList<int> quadruplets = new ArrayList<>();
D. List<List> quadruplets = new ArrayList();

Solution

  1. Step 1: Check Java syntax for list initialization

    Correct generic syntax for a list of lists of integers is List quadruplets = new ArrayList<>();

  2. Step 2: Identify errors in other options

    List quadruplets = new List<>(); uses raw List without generics and wrong constructor; ArrayList<int> quadruplets = new ArrayList<>(); uses primitive int which is invalid; List<List> quadruplets = new ArrayList(); mixes generics incorrectly.

  3. Final Answer:

    List quadruplets = new ArrayList<>(); -> Option B

  4. Quick Check:

    Correct generic list initialization = List quadruplets = new ArrayList<>(); [OK]
Hint: Use List with ArrayList constructor [OK]
Common Mistakes:
  • Using raw types without generics
  • Trying to use primitive types in generics
  • Incorrect constructor calls for List
3. What will be the output of the following Java code snippet for the Four Sum problem?
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
List result = fourSum(nums, target);
System.out.println(result);

Assuming fourSum correctly finds all unique quadruplets summing to target.
medium
A. [[-2, -1, 0, 1], [0, 0, 0, 0]]
B. [[1, 0, -1, 0]]
C. [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
D. []

Solution

  1. Step 1: Sort and find quadruplets summing to zero

    Sorted array: [-2, -1, 0, 0, 1, 2]. Quadruplets summing to 0 are [-2,-1,1,2], [-2,0,0,2], and [-1,0,0,1].

  2. Step 2: Verify uniqueness and completeness

    All quadruplets are unique and sum exactly to target 0. No other quadruplets exist.

  3. Final Answer:

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

  4. Quick Check:

    Unique quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]
Hint: Sort array first, then find quadruplets with two pointers [OK]
Common Mistakes:
  • Not sorting array before processing
  • Including duplicate quadruplets
  • Missing some valid quadruplets
4. Identify the bug in this Java snippet for the Four Sum problem:
for (int i = 0; i < nums.length - 3; i++) {
  for (int j = i + 1; j < nums.length - 2; j++) {
    int left = j + 1, right = nums.length - 1;
    while (left < right) {
      int sum = nums[i] + nums[j] + nums[left] + nums[right];
      if (sum == target) {
        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }
}
medium
A. Sum calculation uses wrong indices
B. Incorrect initialization of left and right pointers
C. Wrong loop conditions for i and j
D. Missing checks to skip duplicate elements for i, j, left, and right

Solution

  1. Step 1: Analyze loop and pointer usage

    Loops and pointers are correctly set to find quadruplets, and sum calculation is correct.

  2. Step 2: Identify missing duplicate skipping

    Code lacks checks to skip duplicate values for i, j, left, and right after finding a quadruplet, which can cause duplicate quadruplets in result.

  3. Final Answer:

    Missing checks to skip duplicate elements for i, j, left, and right -> Option D

  4. Quick Check:

    Duplicate skipping missing = Missing checks to skip duplicate elements for i, j, left, and right [OK]
Hint: Always skip duplicates after adding quadruplet to avoid repeats [OK]
Common Mistakes:
  • Not skipping duplicates causing repeated quadruplets
  • Changing pointers incorrectly inside loops
  • Incorrect loop boundaries causing index errors
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: Check if quadruplets sum to target

    All elements are 2, so quadruplet [2, 2, 2, 2] sums to 8.

  2. Step 2: Ensure uniqueness of quadruplets

    Even though elements repeat, only one unique quadruplet exists. Duplicates must be avoided.

  3. Final Answer:

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

  4. Quick Check:

    Unique quadruplet summing to 8 = [[2, 2, 2, 2]] [OK]
Hint: Same numbers can form one unique quadruplet if sum matches target [OK]
Common Mistakes:
  • Returning duplicate quadruplets multiple times
  • Returning empty list when quadruplet exists
  • Confusing triple with quadruplet
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard