3Sum

▶

Steps

setup

Sort the input array

The input array is sorted to [-4, -1, -1, 0, 1, 2]. Sorting helps easily skip duplicates and enables efficient complement search.

💡 Sorting is crucial because it groups duplicates together and allows the algorithm to avoid repeated triplets.

Line:

nums.sort()

💡 Sorted array is the foundation for the two-pointer and hash set approach.

setup

Fix i at index 0

Set pointer i to index 0, fixing the first element of the triplet as -4. Initialize an empty hash set for seen values.

💡 Fixing i lets us find pairs that sum to -nums[i], here 4, using the hash set.

Line:

for i in range(n):
    if i > 0 and nums[i] == nums[i-1]:
        continue
    seen = set()

💡 Starting the main loop with i=0 to find pairs summing to 4.

fill_cells

Start inner loop with j=1, complement=5

Set pointer j to index 1. Calculate complement = -nums[i] - nums[j] = 4 - (-1) = 5. Check if complement 5 is in seen set (empty now).

💡 We look for a number 5 that pairs with nums[j] to sum to -nums[i]. Since seen is empty, no match.

Line:

j = i + 1
while j < n:
    complement = -nums[i] - nums[j]

💡 No triplet found yet; we add nums[j] to seen for future complements.

fill_cells

Move j to 2, complement=5

Move j to index 2. Calculate complement = 4 - (-1) = 5 again. Check if 5 in seen {-1}. Not found, add nums[j] = -1 to seen.

💡 Even though nums[j] is duplicate -1, we add it to seen to track all values after i.

Line:

if complement in seen:
    ...
seen.add(nums[j])
j += 1

💡 Seen now has {-1}, but duplicates do not affect complement search.

fill_cells

Move j to 3, complement=4

j moves to index 3. complement = 4 - 0 = 4. Check if 4 in seen {-1}. Not found, add nums[j] = 0 to seen.

💡 We continue scanning for complements to sum zero with fixed i.

Line:

complement = -nums[i] - nums[j]
if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now contains {-1, 0}.

fill_cells

Move j to 4, complement=3

j moves to index 4. complement = 4 - 1 = 3. Check if 3 in seen {-1, 0}. Not found, add nums[j] = 1 to seen.

💡 No complement found yet; keep adding to seen.

Line:

if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now contains {-1, 0, 1}.

fill_cells

Move j to 5, complement=2

j moves to index 5. complement = 4 - 2 = 2. Check if 2 in seen {-1, 0, 1}. Not found, add nums[j] = 2 to seen.

💡 No complement found, add 2 to seen.

Line:

if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now contains {-1, 0, 1, 2}.

setup

Move i to 1, skip duplicates check

Move i to index 1. Since nums[1] = -1 is not equal to nums[0] = -4, do not skip. Initialize empty seen set.

💡 Skipping duplicates for i avoids repeated triplets.

Line:

for i in range(n):
    if i > 0 and nums[i] == nums[i-1]:
        continue
    seen = set()

💡 New fixed element -1 to find pairs summing to 1.

fill_cells

j=2, complement=2 not in seen

Set j=2. complement = -nums[i] - nums[j] = 1 - (-1) = 2. Check if 2 in seen (empty). Not found, add nums[j] = -1 to seen.

💡 Start scanning for pairs that sum to 1.

Line:

j = i + 1
while j < n:
    complement = -nums[i] - nums[j]

💡 Seen now {-1}.

fill_cells

j=3, complement=1 not in seen

j=3. complement = 1 - 0 = 1. Check if 1 in seen {-1}. Not found, add nums[j] = 0 to seen.

💡 Continue scanning for complements.

Line:

if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now {-1, 0}.

fill_cells

j=4, complement=0 found in seen

j=4. complement = 1 - 1 = 0. Check if 0 in seen {-1, 0}. Found! Triplet [-1, 0, 1] found and added to result.

💡 Finding complement in seen means a valid triplet is found.

Line:

if complement in seen:
    triplet = sorted([nums[i], complement, nums[j]])
    res.append(triplet)

💡 Triplet sums to zero and is unique due to sorting and skipping duplicates.

fill_cells

Skip duplicate j=5 after triplet

After recording triplet, check for duplicates at j+1. j=5 is next, nums[5]=2 different from nums[4]=1, so no skip. Add nums[4]=1 to seen and move j to 5.

💡 Skipping duplicates after triplet avoids repeated triplets.

Line:

while j + 1 < n and nums[j] == nums[j + 1]:
    j += 1
seen.add(nums[j])
j += 1

💡 Duplicates handled carefully to avoid repeats.

fill_cells

j=5, complement=-1 found in seen

j=5. complement = 1 - 2 = -1. Check if -1 in seen {-1, 0, 1}. Found! Triplet [-1, -1, 2] found and added to result.

💡 Another valid triplet found using complement in seen.

Line:

if complement in seen:
    triplet = sorted([nums[i], complement, nums[j]])
    res.append(triplet)

💡 Triplet sums to zero and is unique.

setup

Move i to 2, skip duplicate fixed element

Move i to index 2. nums[2] = -1 equals nums[1] = -1, so skip this i to avoid duplicate triplets.

💡 Skipping duplicate fixed elements prevents repeated triplets.

Line:

if i > 0 and nums[i] == nums[i-1]:
    continue

💡 Duplicate fixed elements are ignored.

setup

Move i to 3, fix element 0

i moves to index 3, fixing element 0. Initialize empty seen set for scanning pairs summing to 0.

💡 New fixed element 0 to find pairs summing to 0.

Line:

seen = set()

💡 Ready to scan j for pairs.

fill_cells

j=4, complement=-1 not in seen

j=4. complement = -nums[i] - nums[j] = 0 - 1 = -1. Check if -1 in seen (empty). Not found, add nums[j] = 1 to seen.

💡 Scanning for pairs that sum to 0 with fixed i=0.

Line:

complement = -nums[i] - nums[j]
if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now {1}.

fill_cells

j=5, complement=-2 not in seen

j=5. complement = 0 - 2 = -2. Check if -2 in seen {1}. Not found, add nums[j] = 2 to seen.

💡 No complement found, add to seen.

Line:

if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now {1, 2}.

setup

Move i to 4, fix element 1

i moves to index 4, fixing element 1. Initialize empty seen set for scanning pairs summing to -1.

💡 New fixed element 1 to find pairs summing to -1.

Line:

seen = set()

💡 Ready to scan j for pairs.

fill_cells

j=5, complement=-3 not in seen

j=5. complement = -nums[i] - nums[j] = -1 - 2 = -3. Check if -3 in seen (empty). Not found, add nums[j] = 2 to seen.

💡 No complement found, add to seen.

Line:

if complement in seen:
    ...
seen.add(nums[j])

💡 Seen now {2}.

setup

Move i to 5, end loop

i moves to index 5, but since we need at least two elements after i for pairs, loop ends.

💡 No more triplets possible with i at last or second last index.

Line:

for i in range(n):
    ...

💡 All triplets found.

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()  # STEP 1
    n = len(nums)
    res = []
    for i in range(n):  # STEP 2,8,14,15,18,20
        if i > 0 and nums[i] == nums[i-1]:  # STEP 14
            continue
        seen = set()  # STEP 2,8,15,18
        j = i + 1
        while j < n:  # STEP 3-7,9-13,16-17,19
            complement = -nums[i] - nums[j]  # STEP 3,4,5...
            if complement in seen:  # STEP 11,13
                triplet = sorted([nums[i], complement, nums[j]])
                res.append(triplet)  # record triplet
                while j + 1 < n and nums[j] == nums[j + 1]:  # skip duplicates
                    j += 1
            seen.add(nums[j])
            j += 1
    return res

📊

3Sum - Watch the Algorithm Execute, Step by Step

Watching each pointer move and each decision to add or skip elements reveals how the algorithm efficiently finds unique triplets summing to zero without brute force.

setup

-4

0

-1

1

-1

2

0

3

1

4

2

5

Result: []

setup

i

-4

0

-1

1

-1

2

0

3

1

4

2

5

Result: []

compare

i

-4

0

j

-1

1

-1

2

0

3

1

4

2

5

Result: []

compare

i

-4

0

-1

1

j

-1

2

0

3

1

4

2

5

Result: []

compare

i

-4

0

-1

1

-1

2

j

0

3

1

4

2

5

Result: []

compare

i

-4

0

-1

1

-1

2

0

3

j

1

4

2

5

Result: []

compare

i

-4

0

-1

1

-1

2

0

3

1

4

j

2

5

Result: []

setup

-4

0

i

-1

1

-1

2

0

3

1

4

2

5

Result: []

compare

-4

0

i

-1

1

j

-1

2

0

3

1

4

2

5

Result: []

compare

-4

0

i

-1

1

-1

2

j

0

3

1

4

2

5

Result: []

record

-4

0

i

-1

1

-1

2

0

3

j

1

4

2

5

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

move_right

-4

0

i

-1

1

-1

2

0

3

1

4

j

2

5

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

record

-4

0

i

-1

1

-1

2

0

3

1

4

j

2

5

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

prune

-4

0

-1

1

i

-1

2

0

3

1

4

2

5

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

setup

-4

0

-1

1

-1

2

i

0

3

1

4

2

5

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

compare

-4

0

-1

1

-1

2

i

0

3

j

1

4

2

5

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

compare

-4

0

-1

1

-1

2

i

0

3

1

4

j

2

5

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

setup

-4

0

-1

1

-1

2

0

3

i

1

4

2

5

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

compare

-4

0

-1

1

-1

2

0

3

i

1

4

j

2

5

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

prune

-4

0

-1

1

-1

2

0

3

1

4

i

2

5

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

Key Takeaways

✓ Sorting the array upfront allows efficient duplicate skipping and simplifies complement search.

Without sorting, handling duplicates and searching complements would be more complex and error-prone.

✓ Using a hash set for each fixed element i lets us find pairs summing to -nums[i] in linear time.

This avoids the O(n^2) brute force by quickly checking complements in constant time.

✓ Skipping duplicates for both fixed elements and inner scanning pointers prevents repeated triplets in the result.

This subtle step ensures the output contains unique triplets without extra overhead.

Practice

1. You are given an array of integers and need to move all zero elements to the end while maintaining the relative order of non-zero elements. Which algorithmic approach guarantees an optimal in-place solution with O(n) time and O(1) space complexity?

easy

A. Use an extra array to copy all non-zero elements first, then fill the rest with zeroes.

B. Use a greedy approach that swaps zeroes with the next non-zero element found by scanning from the end.

C. Use dynamic programming to track the minimum swaps needed to move zeroes to the end.

D. Use a two-pointer approach that overwrites non-zero elements at the front and fills zeroes after all non-zero elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires moving zeroes to the end while preserving the order of non-zero elements, with optimal time and space.

2. Step 2: Identify the approach that meets constraints

   The two-pointer overwrite approach scans once, writes non-zero elements in order, then fills zeroes, achieving O(n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two-pointer overwrite is the classic optimal solution [OK]

Hint: Two-pointer overwrite ensures order and in-place operation [OK]

Common Mistakes:

• Confusing greedy swaps with in-place overwrite
• Using extra space when not allowed
• Applying DP unnecessarily

2. The following code attempts to move zeroes to the end of the array in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    # Bug introduced here
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = nums[i]

What is the bug in this code?

medium

A. The variable lastNonZeroFoundAt is incremented incorrectly.

B. The first loop does not correctly identify non-zero elements.

C. The second loop does not fill zeroes after lastNonZeroFoundAt, leaving old values intact.

D. The assignment inside the first loop overwrites zeroes incorrectly.

Solution

1. Step 1: Analyze second loop behavior

   The second loop assigns nums[i] = nums[i], which does nothing and fails to fill zeroes.

2. Step 2: Identify correct fix

   It should assign nums[i] = 0 to move zeroes to the end properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Zeroes remain unfilled, causing incorrect output [OK]

Hint: Second loop must fill zeroes, not copy existing values [OK]

Common Mistakes:

• Forgetting to fill zeroes after moving non-zero elements
• Misunderstanding loop purpose

3. Suppose the problem is extended so that the backspace character '#' can be repeated multiple times consecutively, and you want to optimize the algorithm to handle very long sequences of '#' efficiently. Which modification to the two-pointer forward approach is most appropriate?

hard

A. Process the strings from the end with two pointers, skipping characters affected by consecutive backspaces on the fly.

B. Modify the algorithm to skip over consecutive '#' characters by counting them and adjusting the write pointer accordingly in one step.

C. Use a stack to push characters and pop for each '#' to handle multiple backspaces efficiently.

D. Preprocess the strings by removing all '#' characters before comparison.

Solution

1. Step 1: Understand the challenge with consecutive backspaces

   Multiple consecutive '#' characters can cause multiple deletions, which can be inefficient if processed one by one in a forward pass.

2. Step 2: Identify the best approach

   Processing from the end with two pointers allows skipping over characters affected by multiple backspaces efficiently without reconstructing strings or counting '#' explicitly.

3. Step 3: Why other options fail

   Counting '#' forward is complex and error-prone; stacks use extra space; preprocessing removes needed info and breaks order.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backward two-pointer approach handles consecutive backspaces efficiently [OK]

Hint: Backward two-pointer skips multiple backspaces efficiently [OK]

Common Mistakes:

• Trying to count '#' forward complicates logic
• Using stacks increases space unnecessarily
• Preprocessing removes order and breaks correctness

4. Suppose the problem changes: you want to count pairs with absolute difference at most K, but now the array can contain duplicate elements and you want to count pairs where elements can be reused multiple times (i.e., pairs (i, j) with i ≤ j). Which modification to the binary search approach correctly handles this variant?

hard

A. Start binary search from i instead of i + 1 and count pairs where j ≥ i, adjusting count accordingly.

B. Use brute force nested loops to count all pairs with i ≤ j and difference ≤ K, as binary search cannot handle reuse.

C. Use two pointers with left starting at 0 and right starting at 0, moving right pointer forward and counting pairs including i = j.

D. Keep the same code but change bisect_right to bisect_left to include duplicates and allow i ≤ j pairs.

Solution

1. Step 1: Understand reuse and duplicates impact

   Allowing i ≤ j means pairs with the same element twice are valid; binary search must include current index.

2. Step 2: Modify binary search start index

   Starting bisect_right from i (not i+1) includes pairs where i == j; counting j ≥ i pairs correctly.

3. Step 3: Adjust counting logic

   Count pairs as j - i + 1 if including i == j, or carefully count pairs with j ≥ i.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Starting search at i and counting pairs with j ≥ i handles reuse correctly [OK]

Hint: Start binary search at i to include pairs with i == j [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right incorrectly
• Ignoring pairs where i == j
• Assuming two pointers cannot handle reuse

5. Suppose the input array can contain any integer values, not just 0, 1, and 2, but you still want to sort it in a single pass using a similar three-pointer approach. Which modification to the Dutch National Flag algorithm is necessary to handle this general case correctly?

hard

A. Use counting sort instead, as three pointers only work for three distinct values

B. Extend the algorithm to dynamically partition into k segments with k pointers

C. Map the values to 0,1,2 first, then apply the original algorithm

D. Use quicksort partitioning with recursive calls instead of pointers

Solution

1. Step 1: Understand limitation of original algorithm

   The Dutch National Flag algorithm is designed specifically for three distinct values and uses three pointers to partition accordingly.

2. Step 2: Generalize to k distinct values

   For more than three distinct values, the algorithm must be extended to k pointers or multiple passes to partition into k segments, as a single pass with three pointers cannot correctly sort arbitrary values.

3. Step 3: Evaluate other options

   Counting sort is two-pass, mapping values is not always feasible, and quicksort is general but not single pass.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Generalizing requires more pointers or passes, not just three pointers [OK]

Hint: Three pointers only for three distinct values [OK]

Common Mistakes:

• Trying to map values first
• Using quicksort for single pass
• Assuming counting sort is single pass