4Sum

📋

Problem

Imagine you are a treasure hunter trying to find four unique gems whose combined value matches exactly a target sum, but you only have a list of gem values.

Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n, a, b, c, and d are distinct indices, and nums[a] + nums[b] + nums[c] + nums[d] == target. The solution set must not contain duplicate quadruplets.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9-10^9 ≤ target ≤ 10^9

Edge cases: Empty array → []Array with less than 4 elements → []All elements are the same and sum matches target → one quadruplet

</>

IDE

def fourSum(nums: list[int], target: int) -> list[list[int]]:public List<List<Integer>> fourSum(int[] nums, int target)vector<vector<int>> fourSum(vector<int>& nums, int target)function fourSum(nums, target)

def fourSum(nums, target):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    // Write your solution here
    return {};
}

function fourSum(nums, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1, 0, 0, -1], [-2, -1, 1, 2]]Not sorting input or not sorting quadruplets before adding, causing duplicates or missing quadruplets.✅ Sort input array first and sort quadruplets before adding to result; skip duplicates in loops and pointers.

Wrong: [[2, 2, 2, 2], [2, 2, 2, 2]]Not skipping duplicates properly, resulting in repeated quadruplets.✅ Add duplicate skipping conditions in all loops and pointer movements.

Wrong: [[1, 2, 3, 4]]Returning quadruplets that do not sum to target due to incorrect sum check or off-by-one errors.✅ Verify sum equals target exactly before adding quadruplet.

Wrong: Timeout or no outputUsing brute force O(n^4) approach on large inputs causing TLE.✅ Implement sorting + two pointers with deduplication to achieve O(n^3) time complexity.

✓

Test Cases

Try testing your code with empty and very small inputs to catch base case bugs.

Look for tricky cases that break greedy or naive pointer logic.

Prepare to optimize your solution to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,0,-1,0,-2,2],"target":0}

Expected[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

⏱ Performance - must finish in 2000ms

After sorting, we find all quadruplets that sum to zero without duplicates.

💡 Sort the array first to use two pointers effectively.

💡 Use nested loops for first two numbers and two pointers for the last two.

💡 Skip duplicates by checking previous values before moving pointers.

Why it failed: Failed to find all unique quadruplets or included duplicates. Fix by sorting and skipping duplicates properly.

✓ Correctly found all unique quadruplets summing to target.

t1_02basic

Input{"nums":[2,2,2,2,2],"target":8}

Expected[[2,2,2,2]]

⏱ Performance - must finish in 2000ms

All elements are 2 and sum to 8 with quadruplet [2,2,2,2]. Only one unique quadruplet.

💡 Check for duplicates to avoid repeated quadruplets.

💡 Even if all elements are same, only one quadruplet should be returned.

💡 Use conditions to skip over repeated elements in loops.

Why it failed: Returned duplicates or missed the quadruplet. Fix by adding duplicate checks in loops.

✓ Correctly returned the single unique quadruplet.

t2_01edge

Input{"nums":[],"target":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array returns empty list as no quadruplets exist.

💡 Handle empty input arrays explicitly.

💡 Check if length of nums is less than 4 and return empty immediately.

💡 No quadruplets possible if less than 4 elements.

Why it failed: Code does not handle empty input or small arrays, causing errors or wrong output. Add length check for nums < 4.

✓ Correctly returns empty list for empty input.

t2_02edge

Input{"nums":[1,2,3],"target":6}

Expected[]

⏱ Performance - must finish in 2000ms

Array length less than 4 means no quadruplets possible.

💡 Check array length before processing.

💡 Return empty list if nums length < 4.

💡 No quadruplets can be formed with fewer than 4 elements.

Why it failed: Fails to return empty for input with less than 4 elements. Add early return for length check.

✓ Correctly returns empty list for input with less than 4 elements.

t2_03edge

Input{"nums":[0,0,0,0],"target":0}

Expected[[0,0,0,0]]

⏱ Performance - must finish in 2000ms

All elements zero and sum zero, only one quadruplet possible.

💡 Handle duplicates carefully to avoid multiple identical quadruplets.

💡 Check for skipping duplicates in all loops and pointers.

💡 Return only one quadruplet when all elements are identical.

Why it failed: Returns multiple duplicate quadruplets. Fix by skipping duplicates in loops and pointers.

✓ Correctly returns single quadruplet for identical elements.

t3_01corner

Input{"nums":[1,0,-1,0,-2,2],"target":1}

Expected[[-2,0,1,2],[-1,0,0,2]]

⏱ Performance - must finish in 2000ms

Target 1 requires careful pointer movement; greedy approach fails here.

💡 Greedy approach picking largest or smallest first can miss quadruplets.

💡 Use sorting and two pointers with nested loops to explore all combinations.

💡 Check all quadruplets by fixing first two numbers and moving two pointers.

Why it failed: Greedy approach fails to find all quadruplets summing to target. Fix by using nested loops and two pointers.

✓ Correctly finds all quadruplets for non-zero target.

t3_02corner

Input{"nums":[1,1,1,1,2,2,2,2],"target":6}

Expected[[1,1,2,2]]

⏱ Performance - must finish in 2000ms

Tests correct handling of duplicates and exact boundary sums.

💡 Check that duplicates are skipped properly to avoid repeated quadruplets.

💡 Ensure sum equals target exactly, not just less than or greater.

💡 Use conditions to skip duplicates in all loops and pointers.

Why it failed: Fails to skip duplicates or includes quadruplets with sum != target. Fix by adding duplicate checks and exact sum condition.

✓ Correctly returns unique quadruplets matching target.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7,8],"target":26}

Expected[[5,6,7,8]]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors and correct pointer boundaries.

💡 Check loop boundaries carefully to avoid missing quadruplets.

💡 Ensure pointers do not cross and indices are distinct.

💡 Verify sum calculation includes all four elements.

Why it failed: Off-by-one errors cause missing quadruplets or index errors. Fix loop and pointer boundaries.

✓ Correctly finds quadruplet at upper boundary.

t4_01performance

Input{"nums":[-50000,-49999,-49998,-49997,-49996,-49995,-49994,-49993,-49992,-49991,-49990,-49989,-49988,-49987,-49986,-49985,-49984,-49983,-49982,-49981,-49980,-49979,-49978,-49977,-49976,-49975,-49974,-49973,-49972,-49971,-49970,-49969,-49968,-49967,-49966,-49965,-49964,-49963,-49962,-49961,-49960,-49959,-49958,-49957,-49956,-49955,-49954,-49953,-49952,-49951,-49950,-49949,-49948,-49947,-49946,-49945,-49944,-49943,-49942,-49941,-49940,-49939,-49938,-49937,-49936,-49935,-49934,-49933,-49932,-49931,-49930,-49929,-49928,-49927,-49926,-49925,-49924,-49923,-49922,-49921,-49920,-49919,-49918,-49917,-49916,-49915,-49914,-49913,-49912,-49911,-49910,-49909,-49908,-49907,-49906,-49905,-49904,-49903,-49902,-49901],"target":-199800}

Expected[]

⏱ Performance - must finish in 2000ms

Large input n=100 tests O(n^3) complexity; must complete within 2 seconds.

💡 O(n^4) brute force will time out; optimize to O(n^3) with sorting and two pointers.

💡 Use early pruning and skip duplicates to reduce search space.

💡 Avoid nested loops beyond three levels and use two pointers for last two elements.

Why it failed: TLE due to O(n^4) brute force approach. Fix by implementing sorting + two pointers with deduplication for O(n^3).

✓ Algorithm runs within time limit using O(n^3) approach.

Practice

1. You are given an integer array and asked to find all unique triplets that sum to zero. Which approach guarantees an optimal solution in terms of time complexity and handles duplicates efficiently?

easy

A. Sort the array, fix one element, and use a two-pointer approach to find pairs that sum to the negative of the fixed element, skipping duplicates.

B. Use a greedy approach by sorting and picking the smallest and largest elements to form triplets.

C. Use dynamic programming to build up solutions for smaller subsets and combine them to find triplets.

D. Use three nested loops to check all triplets and store unique sorted triplets in a set.

Solution

1. Step 1: Understand problem constraints

   We need all unique triplets summing to zero, efficiently handling duplicates.

2. Step 2: Identify approach that handles duplicates and optimizes search

   Sorting and fixing one element allows using a two-pointer approach to find pairs summing to the complement, skipping duplicates efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two-pointer approach is O(n^2) and handles duplicates [OK]

Hint: Sorting + two-pointer handles duplicates and runs in O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using DP which doesn't fit this problem
• Greedy approach misses some triplets

2. What is the time complexity of the optimal two-pointer approach for the 3Sum Smaller problem when the input array has length n?

medium

A. O(n^2) because the outer loop runs n times and the inner two-pointer scan runs in O(n)

B. O(n^3) because of the nested loops

C. O(n log n) due to sorting dominating the complexity

D. O(n^2 log n) because each two-pointer step involves a binary search

Solution

1. Step 1: Identify loops and sorting cost

   Sorting takes O(n log n). The main loop runs O(n) times.

2. Step 2: Analyze inner two-pointer loop

   For each i, two pointers scan the remaining array once, total O(n) per i.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is O(n log n + n^2) -> O(n^2) dominates [OK]

Hint: Two pointers scan each element once per outer iteration [OK]

Common Mistakes:

• Confusing two-pointer scan as O(n^2) per iteration
• Ignoring sorting cost or assuming it dominates
• Assuming binary search is used inside two-pointer

3. What is the time complexity of the binary search based algorithm for counting pairs with absolute difference at most K in a sorted array of length n?

medium

A. O(n²)

B. O(n log n)

C. O(n)

D. O(log n)

Solution

1. Step 1: Identify outer loop complexity

   The algorithm iterates over each element once, so outer loop is O(n).

2. Step 2: Identify inner operation complexity

   For each element, a binary search (bisect_right) is performed in O(log n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Overall complexity is O(n) * O(log n) = O(n log n) [OK]

Hint: Binary search inside a loop yields O(n log n) [OK]

Common Mistakes:

• Assuming O(n) because binary search is fast
• Mistaking nested loops for O(n²)
• Ignoring binary search cost

4. The following code attempts to find the minimum difference between k closest elements but contains a subtle bug. Identify the bug.

medium

A. Not sorting the array before sliding window causes incorrect results.

B. Using max and min inside the loop is inefficient but not a bug.

C. The loop boundary should be len(arr) - k instead of len(arr) - k + 1.

D. The initial value of min_diff should be 0 instead of infinity.

Solution

1. Step 1: Analyze the approach

   The code uses a sliding window but does not sort the array first.

2. Step 2: Understand impact of missing sort

   Without sorting, the window elements are not guaranteed to be contiguous in sorted order, so max-min difference may not be minimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting is essential before sliding window to ensure correctness [OK]

Hint: Always sort before sliding window for min difference [OK]

Common Mistakes:

• Ignoring sorting leads to wrong min difference
• Confusing inefficiency with correctness
• Off-by-one loop boundary errors

5. What is the time complexity of the optimal two-pointer approach for removing duplicates from a sorted array of length n?

medium

A. O(n) because each element is visited at most twice

B. O(n log n) due to sorting overhead

C. O(n²) due to nested comparisons

D. O(1) since it modifies the array in-place

Solution

1. Step 1: Identify loops and operations

   The algorithm uses a single for loop iterating over n elements once, with constant time operations inside.

2. Step 2: Confirm no nested loops or sorting

   No nested loops or sorting steps; each element is compared once or twice, so total time is linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear scan with two pointers yields O(n) time [OK]

Hint: Single pass over array means O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Thinking in-place means O(1) time