4Sum

▶

Steps

setup

Sort the input array

The input array is sorted to facilitate pair sum mapping and to avoid duplicates in quadruplets.

💡 Sorting is essential because it allows efficient pairing and easy duplicate detection.

Line:

nums.sort()

💡 Sorted array enables systematic pair exploration and consistent quadruplet ordering.

setup

Initialize two_sum_map and result set

Create an empty hash map to store sums of pairs and an empty set to hold unique quadruplets.

💡 These data structures are crucial for efficient lookup and duplicate avoidance.

Line:

two_sum_map = defaultdict(list)
res = set()

💡 Preparing storage for pair sums and results sets the stage for the main algorithm.

fill_cells

Start outer loop for pair sums (i=0)

Begin iterating over the array with index i at 0 to form pairs with j > i.

💡 Outer loop controls the first element of each pair to be stored.

Line:

for i in range(n):

💡 We systematically consider each element as the first pair member.

fill_cells

Start inner loop for pair sums (j=1)

Set pointer j to 1 to pair with i=0 and calculate their sum.

💡 Inner loop finds all pairs with the first element fixed at i.

Line:

for j in range(i + 1, n):

💡 We explore all pairs starting with the element at i.

fill_cells

Record pair sum for indices (0,1)

Calculate sum of nums[0] + nums[1] = -2 + -1 = -3 and store indices in two_sum_map.

💡 Mapping sums to index pairs allows quick lookup of complementary pairs later.

Line:

two_sum_map[nums[i] + nums[j]].append((i, j))

💡 Each pair sum is stored with its indices for future quadruplet formation.

fill_cells

Advance inner loop (j=2) and record pair sum

Move j to 2, calculate sum nums[0] + nums[2] = -2 + 0 = -2, and store indices.

💡 Continuing to record all pairs starting with i=0.

Line:

two_sum_map[nums[i] + nums[j]].append((i, j))

💡 All pairs with i=0 are systematically recorded.

fill_cells

Complete pair sum mapping for i=0

Finish inner loop for i=0 by recording pairs (0,3), (0,4), and (0,5) with their sums.

💡 Completing all pairs for the first element ensures full coverage.

Line:

for j in range(i + 1, n):
    two_sum_map[nums[i] + nums[j]].append((i, j))

💡 All pairs starting at i=0 are now in the map for lookup.

compare

Iterate over two_sum_map keys to find complementary sums

For each sum1 in two_sum_map, compute sum2 = target - sum1 and check if sum2 exists in the map.

💡 Finding complementary sums is key to forming quadruplets that sum to target.

Line:

for sum1 in two_sum_map:
    sum2 = target - sum1
    if sum2 not in two_sum_map:
        continue

💡 Only pairs whose sums complement each other to target are combined.

compare

Combine pairs from sum1 and sum2 lists

For each pair (i,j) in list1 and (k,l) in list2, check if indices are distinct to form quadruplets.

💡 Ensuring indices do not overlap avoids invalid quadruplets.

Line:

for (i, j) in list1:
    for (k, l) in list2:
        if i != k and i != l and j != k and j != l:

💡 Distinct indices guarantee quadruplets use four unique elements.

insert

Add valid quadruplet to result set

Sort quadruplet values and add as a tuple to the result set to avoid duplicates.

💡 Sorting quadruplets ensures consistent ordering and easy duplicate detection.

Line:

quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
res.add(quad)

💡 Using a set with sorted tuples prevents duplicate quadruplets in the final answer.

compare

Continue combining pairs to find all quadruplets

Repeat the combination and validation process for all pairs in two_sum_map to find all quadruplets.

💡 Systematic combination ensures no quadruplet is missed.

Line:

for sum1 in two_sum_map:
    sum2 = target - sum1
    if sum2 in two_sum_map:
        ...

💡 The algorithm exhaustively explores all valid quadruplet combinations.

reconstruct

Convert result set to sorted list

Transform the set of quadruplets into a sorted list for the final output.

💡 Sorting the final list ensures consistent output order.

Line:

return [list(quad) for quad in sorted(res)]

💡 Final output is a list of unique quadruplets sorted lexicographically.

from typing import List
from collections import defaultdict

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    nums.sort()  # STEP 1
    n = len(nums)
    two_sum_map = defaultdict(list)  # STEP 2
    res = set()  # STEP 2
    for i in range(n):  # STEP 3
        for j in range(i + 1, n):  # STEP 4
            two_sum_map[nums[i] + nums[j]].append((i, j))  # STEP 5-7
    for sum1 in two_sum_map:  # STEP 8
        sum2 = target - sum1  # STEP 8
        if sum2 not in two_sum_map:  # STEP 8
            continue  # STEP 8
        list1 = two_sum_map[sum1]
        list2 = two_sum_map[sum2]
        for (i, j) in list1:  # STEP 9
            for (k, l) in list2:  # STEP 9
                if i != k and i != l and j != k and j != l:  # STEP 9
                    quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))  # STEP 10
                    res.add(quad)  # STEP 10
    return [list(quad) for quad in sorted(res)]  # STEP 12

if __name__ == '__main__':
    print(fourSum([1,0,-1,0,-2,2], 0))

📊

4Sum - Watch the Algorithm Execute, Step by Step

Watching each step reveals how pairs are combined and filtered, making the complex 4Sum problem intuitive and clear.

move_right

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: []

setup

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: []

move_right

i

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: []

record

i

-2

0

j

-1

1

0

2

0

3

1

4

2

5

Result: []

record

i

-2

0

j

-1

1

0

2

0

3

1

4

2

5

Result: []

record

i

-2

0

-1

1

j

0

2

0

3

1

4

2

5

Result: []

fill_cells

i

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: []

compare

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: []

compare

i

-2

0

j

-1

1

0

2

0

3

k

1

4

l

2

5

Result: []

record

i

-2

0

j

-1

1

0

2

0

3

k

1

4

l

2

5

Result: [[-2,-1,1,2]]

compare

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

reconstruct

-2

0

-1

1

0

2

0

3

1

4

2

5

Result: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Key Takeaways

✓ Sorting the array upfront simplifies pair sum mapping and duplicate avoidance.

Without sorting, it is much harder to systematically find and avoid duplicate quadruplets.

✓ Using a hash map to store pair sums allows efficient lookup of complementary pairs.

This approach reduces the problem from O(n^4) to roughly O(n^2) by reusing pair sums.

✓ Ensuring all indices in quadruplets are distinct is critical to avoid invalid combinations.

This step is subtle and easy to miss when reading code but is clearly visible in the visualization.

Practice

1. Consider the following Python code implementing the optimal two-pointer forward approach for backspace string compare. What is the value of the variable write after processing the input string S = "ab#c" inside the build function?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace the build function with input "ab#c"

   Start with write=0. Read 'a' -> arr[0]='a', write=1. Read 'b' -> arr[1]='b', write=2. Read '#' -> write=1 (backspace removes 'b'). Read 'c' -> arr[1]='c', write=2.

2. Step 2: Final value of write

   After processing, write=2, indicating the final string length is 2 ("ac").

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   write increments and decrements correctly for backspace [OK]

Hint: write increments on char, decrements on backspace if possible [OK]

Common Mistakes:

• Counting '#' as a character and incrementing write
• Not decrementing write on backspace
• Off-by-one errors in write pointer

2. You are given a sorted array of integers and a value K. You need to count the number of pairs (i, j) with i < j such that the absolute difference between the elements at these indices is at most K. Which algorithmic approach guarantees the most efficient solution for this problem?

easy

A. Use binary search to find the upper bound for each element and count pairs accordingly.

B. Use a brute force nested loop to check all pairs and count those with difference ≤ K.

C. Use dynamic programming to store counts of valid pairs up to each index.

D. Use a two-pointer sliding window approach to find pairs with difference ≤ K in O(n) time.

Solution

1. Step 1: Understand problem constraints and sorted input

   The array is sorted, so for each element, pairs with difference ≤ K lie within a contiguous range to the right.

2. Step 2: Identify optimal approach

   A two-pointer sliding window approach can find pairs with difference ≤ K in O(n) time by expanding and contracting the window efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers leverage sorted order for linear time counting [OK]

Hint: Two-pointer sliding window exploits sorted array for O(n) counting [OK]

Common Mistakes:

• Assuming binary search is always better than two pointers
• Using DP which is unnecessary and inefficient
• Choosing brute force due to simplicity

3. You are given an array of integers and need to reorder it so that all even numbers appear before all odd numbers. Which algorithmic approach guarantees an optimal in-place solution with O(n) time and O(1) space complexity?

easy

A. Using a two-pointer technique that partitions the array in a single pass by swapping elements

B. Using dynamic programming to track even and odd counts and reorder accordingly

C. Sorting the array using a comparison-based sort and then grouping evens and odds

D. Using a brute force approach by creating two separate arrays for evens and odds and concatenating them

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering the array so that evens come before odds, ideally in-place and efficiently.

2. Step 2: Identify the optimal approach

   The two-pointer technique allows scanning the array once, swapping evens to the front, achieving O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer partitioning is classic for in-place parity partitioning [OK]

Hint: Two-pointer partitioning solves in-place parity grouping [OK]

Common Mistakes:

• Assuming sorting is needed for parity grouping
• Thinking DP applies to simple partitioning
• Believing extra arrays are optimal for in-place constraints

4. You are given a sorted array of integers and a target sum. You need to find two distinct elements whose sum equals the target. Which approach guarantees an optimal solution in terms of time complexity and correctness?

easy

A. Use two pointers starting at opposite ends of the array, moving inward based on the sum comparison.

B. Use a hash map to store elements and check complements in a single pass.

C. Use dynamic programming to store sums of all pairs and check for the target.

D. Use a greedy approach by iterating from the start and picking the first pair that sums to the target.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, so two pointers at opposite ends can efficiently find pairs by comparing sums.

2. Step 2: Evaluate each approach

   Greedy fails because it may miss pairs; DP is unnecessary overhead; hash map works but uses extra space and is not optimal for sorted arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers exploit sorting for O(n) time and O(1) space [OK]

Hint: Sorted array + two pointers -> optimal pair search [OK]

Common Mistakes:

• Assuming greedy always works
• Using DP unnecessarily
• Ignoring sorted property

5. What is the space complexity of the recursive two-pointer approach to reverse a string of length n, and why might some candidates incorrectly think it is O(1)?

medium

A. O(1) because the swaps are done in-place without extra arrays.

B. O(log n) because recursion divides the problem in half each call.

C. O(n) because the recursion stack can grow up to n/2 calls.

D. O(n) because a new array is created to hold reversed characters.

Solution

1. Step 1: Analyze recursion stack usage

   Each recursive call processes one pair of characters, so maximum recursion depth is about n/2, leading to O(n) stack space.

2. Step 2: Understand why O(1) is incorrect

   Although swaps are in-place, recursion adds call frames on the stack, which consume O(n) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack depth proportional to input size, so space is O(n) [OK]

Hint: Recursion stack adds O(n) space despite in-place swaps [OK]

Common Mistakes:

• Ignoring recursion stack space
• Confusing in-place with constant space
• Assuming recursion halves problem size each call