Four Sum Problem All Unique Quadruplets in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Quadruplets for a Given Array

What is the output of the following Rust code that finds all unique quadruplets in the array that sum to the target 0?

DSA Rust

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

fn main() {
    let nums = vec![1, 0, -1, 0, -2, 2];
    let target = 0;
    let result = four_sum(nums, target);
    println!("{:?}", result);
}

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

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

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

D [[-2, -2, 1, 3], [-1, 0, 0, 1]]

💡 Hint

Remember to sort the array and skip duplicates to find unique quadruplets.

The code sorts the array and uses two nested loops with two pointers to find quadruplets summing to the target. It skips duplicates to ensure unique quadruplets. The correct output matches option C.

🧠 Conceptual

intermediate

Number of Unique Quadruplets for a Given Input

Given the array [2, 2, 2, 2, 2] and target 8, how many unique quadruplets does the Four Sum algorithm find?

A 1

B 5

C 0

D 10

💡 Hint

All elements are the same; consider how many unique quadruplets can be formed.

Since all elements are 2, the only quadruplet summing to 8 is [2, 2, 2, 2]. The algorithm returns one unique quadruplet.

🔧 Debug

advanced

Identify the Error in Quadruplet Search Code

What error will the following Rust code produce when run?

DSA Rust

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

fn main() {
    let nums = vec![1, 0, -1, 0, -2, 2];
    let target = 0;
    let result = four_sum(nums, target);
    println!("{:?}", result);
}

A Compilation error due to missing semicolon

B Infinite loop causing program to hang

C No error, prints correct quadruplets

D Index out of bounds panic at runtime

💡 Hint

Check how the code handles duplicate skipping and index boundaries.

The code does not skip duplicates and does not check if left+1 or right-1 are valid before incrementing/decrementing, causing potential index out of bounds panic.

🚀 Application

advanced

Find Quadruplets Summing to Target in Large Array

Given a sorted array of 10,000 integers ranging from -5000 to 5000, which approach is best to find all unique quadruplets that sum to a target value efficiently?

A Use a hash map to store all pairs and then find complements

B Use two nested loops and two pointers to find quadruplets

C Use four nested loops to check all quadruplets

D Sort the array and use binary search for each triple to find the fourth

💡 Hint

Consider time complexity and how sorting helps two pointers.

Two nested loops combined with two pointers after sorting gives O(n^3) time, which is more efficient than four nested loops (O(n^4)) and simpler than hash map or binary search approaches for this problem.

❓ Predict Output

expert

Output of Four Sum with Negative and Positive Numbers

What is the output of the following Rust code snippet?

DSA Rust

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

fn main() {
    let nums = vec![-3, -1, 0, 2, 4, 5];
    let target = 2;
    let result = four_sum(nums, target);
    println!("{:?}", result);
}

A [[-3, -1, 2, 4]]

B []

C [[-3, -1, 0, 6]]

D [[-3, 0, 2, 3], [-1, 0, 2, 1]]

💡 Hint

Check sums carefully and remember the array is sorted.

Only the quadruplet [-3, -1, 2, 4] sums to 2. Other options contain numbers not in the array or sums that do not match target.

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