Four Sum Problem All Unique Quadruplets in DSA Rust - Time & Space Complexity

Time Complexity: Four Sum Problem All Unique Quadruplets

O(n³)

Understanding Time Complexity

We want to understand how the time needed to find all unique sets of four numbers that add up to a target grows as the input list gets bigger.

How does the number of steps change when the list size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn four_sum(nums: &mut Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    nums.sort();
    let mut result = Vec::new();
    let n = nums.len();
    for i in 0..n-3 {
        for j in i+1..n-2 {
            let (mut left, mut right) = (j+1, n-1);
            while left < right {
                let sum = nums[i] + nums[j] + nums[left] + nums[right];
                if sum == target {
                    result.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                    left += 1;
                    right -= 1;
                } else if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
    }
    result
}

This code finds all unique quadruplets in the list that add up to the target by sorting and using nested loops with two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two nested loops plus a two-pointer scan inside the innermost loop.
• How many times: Outer loop runs about n times, second loop about n times, and the two-pointer scan runs up to n times in total for each pair.

How Execution Grows With Input

As the list size grows, the number of steps grows roughly with the cube of the size times a linear scan.

Input Size (n)	Approx. Operations
10	About 1,000 steps
100	About 1,000,000 steps
1000	About 1,000,000,000 steps

Pattern observation: The steps increase very quickly, roughly by the cube of the input size times a linear factor.

Final Time Complexity

Time Complexity: O(n³)

This means if the list doubles in size, the time needed grows about eight times, because of the three nested loops and the two-pointer scan.

Common Mistake

[X] Wrong: "The two-pointer scan inside the innermost loop makes the complexity O(n⁴) because it looks like four loops."

[OK] Correct: The two-pointer scan moves pointers inward and does not restart fully each time, so it runs in linear time per pair, not a full loop, keeping the total complexity at O(n³).

Interview Connect

Understanding this complexity helps you explain how nested loops and pointer techniques combine, a skill useful for many array and search problems.

Self-Check

"What if we used a hash map to store pairs sums instead of two pointers? How would the time complexity change?"

Practice

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

easy

A. Count the number of pairs with a given sum

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

C. Find the maximum element in the array

D. Sort the array in ascending order

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the goal

   The goal is not sorting or counting pairs, but specifically finding quadruplets whose sum equals the target.

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 with target sum [OK]

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

Common Mistakes:

• Confusing Four Sum with sorting problems
• Looking for pairs instead of quadruplets
• Ignoring uniqueness of quadruplets

2. Which Rust syntax correctly declares a vector of integers named nums?

easy

A. let nums = {1, 2, 3, 4};

B. let nums = [1, 2, 3, 4];

C. let nums = (1, 2, 3, 4);

D. let nums = vec![1, 2, 3, 4];

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are created using vec![elements] macro, which creates a growable array.

2. Step 2: Check each option

   let nums = vec![1, 2, 3, 4]; uses vec![1, 2, 3, 4] which is correct. let nums = [1, 2, 3, 4]; is an array, not a vector. let nums = (1, 2, 3, 4); is a tuple. let nums = {1, 2, 3, 4}; is invalid syntax.

3. Final Answer:

   let nums = vec![1, 2, 3, 4]; -> Option D

4. Quick Check:

   Vector syntax = vec![...] [OK]

Hint: Use vec! macro for vectors, arrays use brackets only [OK]

Common Mistakes:

• Using array syntax when vector is needed
• Confusing tuples with vectors
• Using curly braces which are invalid here

3. What is the output of the following Rust code snippet that finds quadruplets summing to 0?

let nums = vec![1, 0, -1, 0, -2, 2];
let target = 0;
// Assume function four_sum returns Vec of quadruplets
let result = four_sum(nums, target);
println!("{:?}", result);

Assuming four_sum is correctly implemented, what is the printed output?

medium

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

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

C. [[0, 0, 0, 0]]

D. []

Solution

1. Step 1: Understand the input and target

   The input array is [1, 0, -1, 0, -2, 2] and target sum is 0. We want all unique quadruplets that sum to 0.

2. Step 2: Identify all quadruplets summing to 0

   Possible quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. These are unique and sum to 0.

3. Final Answer:

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

4. Quick Check:

   Quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array and find quadruplets summing to target [OK]

Common Mistakes:

• Returning incomplete quadruplets
• Ignoring duplicates
• Returning empty list incorrectly

4. Identify the bug in this Rust code snippet for the Four Sum problem:

fn four_sum(nums: Vec<i32>, target: i32) -> Vec {
    let mut nums = nums;
    nums.sort();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        for j in i+1..nums.len() {
            let mut left = j + 1;
            let mut right = nums.len() - 1;
            while left < right {
                let sum = nums[i] + nums[j] + nums[left] + nums[right];
                if sum == target {
                    result.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                    left += 1;
                    right -= 1;
                } else if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
    }
    result
}

What is the main issue causing duplicate quadruplets in the result?

medium

A. The vector nums is not sorted before processing

B. The while loop condition left < right is incorrect and should be left <= right

C. The code does not skip duplicate values for i, j, left, and right indices after finding a quadruplet

D. The function does not return the result vector

Solution

1. Step 1: Analyze duplicate handling in loops

   The code finds quadruplets but does not skip over duplicate values for indices i, j, left, and right after adding a quadruplet, causing duplicates in the result.

2. Step 2: Check other options

   The vector is sorted correctly, the while loop condition is correct, and the function returns the result vector properly.

3. Final Answer:

   The code does not skip duplicate values for i, j, left, and right indices after finding a quadruplet -> Option C

4. Quick Check:

   Skipping duplicates needed to avoid repeated quadruplets [OK]

Hint: Skip duplicates after adding quadruplet to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates for all pointers
• Changing loop conditions incorrectly
• Forgetting to sort the array

5. Given the array nums = [2, 2, 2, 2, 2] and target 8, what is the correct output of a Four Sum function that returns all unique quadruplets summing to the target?

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 contains five 2's and the target sum is 8. We need quadruplets of four numbers summing to 8.

2. Step 2: Identify unique quadruplets

   Only one unique quadruplet exists: [2, 2, 2, 2]. Although multiple combinations exist, 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: Avoid duplicates; only one quadruplet of identical numbers [OK]

Common Mistakes:

• Returning duplicate quadruplets multiple times
• Returning empty list incorrectly
• Returning triples instead of quadruplets