3Sum Closest

▶

Steps

setup

Sort the array

The input array is sorted to enable the two-pointer technique. Sorted array is [-4, -1, 1, 2].

💡 Sorting is essential because it allows us to move pointers in a controlled way to increase or decrease sums.

Line:

nums.sort()

💡 Sorted array enables efficient pointer movement to find sums closer to the target.

setup

Initialize closest sum

Initialize closest_sum with the sum of the first three elements: -4 + (-1) + 1 = -4.

💡 Starting with the first triplet sum gives a baseline to compare future sums against.

Line:

closest_sum = nums[0] + nums[1] + nums[2]

💡 We have a starting closest sum to update as we find better sums.

traverse

Fix first element i=0

Start the outer loop with i=0, fixing the first element at index 0 (-4).

💡 Fixing one element lets us find pairs with two pointers to complete the triplet.

Line:

for i in range(n - 2):
    left, right = i + 1, n - 1

💡 We will now try pairs between left=1 and right=3 to find sums with nums[i].

compare

Calculate current sum with i=0, left=1, right=3

Calculate sum of elements at i=0 (-4), left=1 (-1), right=3 (2): sum = -4 + (-1) + 2 = -3.

💡 We check this triplet sum against the target and closest sum to decide next steps.

Line:

current_sum = nums[i] + nums[left] + nums[right]

💡 Current sum is -3, which is closer to target 1 than initial closest sum -4.

insert

Update closest sum to -3

Since |-3 - 1| < |-4 - 1|, update closest_sum to -3.

💡 Updating closest_sum keeps track of the best sum found so far.

Line:

if abs(current_sum - target) < abs(closest_sum - target):
    closest_sum = current_sum

💡 We track the closest sum dynamically as we find better candidates.

shrink

Move left pointer right because current_sum < target

Since current_sum (-3) < target (1), move left pointer from 1 to 2 to increase sum.

💡 Moving left pointer right increases the sum because array is sorted.

Line:

if current_sum < target:
    left += 1

💡 Pointer movement is guided by comparison to target to approach it efficiently.

compare

Calculate current sum with i=0, left=2, right=3

Calculate sum of elements at i=0 (-4), left=2 (1), right=3 (2): sum = -4 + 1 + 2 = -1.

💡 Check if this new triplet sum is closer to target than previous closest sum.

Line:

current_sum = nums[i] + nums[left] + nums[right]

💡 Current sum is -1, closer to target 1 than previous closest sum -3.

insert

Update closest sum to -1

Since |-1 - 1| < |-3 - 1|, update closest_sum to -1.

💡 We keep updating closest_sum as we find sums closer to the target.

Line:

if abs(current_sum - target) < abs(closest_sum - target):
    closest_sum = current_sum

💡 Tracking the closest sum dynamically helps us find the best answer efficiently.

shrink

Move left pointer right again because current_sum < target

Since current_sum (-1) < target (1), move left pointer from 2 to 3.

💡 Moving left pointer right tries to increase sum to get closer to target.

Line:

if current_sum < target:
    left += 1

💡 Pointer movement is a key step to explore new triplets efficiently.

traverse

End inner loop for i=0 as left >= right

Since left pointer (3) is not less than right pointer (3), inner while loop ends for i=0.

💡 When pointers meet or cross, all pairs for fixed i are checked.

Line:

while left < right:

💡 We finished exploring all pairs with i=0 fixed.

traverse

Fix first element i=1

Move to next fixed element i=1 at index 1 (-1). Initialize left=2 and right=3.

💡 We now explore pairs with the second element fixed.

Line:

for i in range(n - 2):
    left, right = i + 1, n - 1

💡 New fixed element means new pairs to check for closer sums.

compare

Calculate current sum with i=1, left=2, right=3

Calculate sum of elements at i=1 (-1), left=2 (1), right=3 (2): sum = -1 + 1 + 2 = 2.

💡 Check if this sum is closer to target than previous closest sum.

Line:

current_sum = nums[i] + nums[left] + nums[right]

💡 Current sum 2 is closer to target 1 than previous closest sum -1.

insert

Update closest sum to 2

Since |2 - 1| < |-1 - 1|, update closest_sum to 2.

💡 We found a sum even closer to the target, so update closest_sum.

Line:

if abs(current_sum - target) < abs(closest_sum - target):
    closest_sum = current_sum

💡 Tracking closest sum ensures we remember the best answer found.

shrink

Since current_sum > target, move right pointer left

Because current_sum (2) > target (1), move right pointer from 3 to 2 to try smaller sums.

💡 Moving right pointer left decreases the sum to approach the target.

Line:

else:
    right -= 1

💡 Pointer movement is guided by sum comparison to target for efficient search.

traverse

End inner loop for i=1 as left >= right

Since left pointer (2) is not less than right pointer (2), inner while loop ends for i=1.

💡 All pairs for fixed i=1 have been checked.

Line:

while left < right:

💡 Finished exploring pairs for this fixed element.

reconstruct

Return closest sum 2 as final answer

All triplets checked; return closest_sum = 2 as the sum closest to target 1.

💡 The algorithm finishes by returning the best sum found.

Line:

return closest_sum

💡 The closest sum found is the final answer to the problem.

def threeSumClosest(nums, target):
    nums.sort()  # STEP 1
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]  # STEP 2
    for i in range(n - 2):  # STEP 3, 11
        left, right = i + 1, n - 1
        while left < right:  # STEP 10, 15
            current_sum = nums[i] + nums[left] + nums[right]  # STEP 4, 7, 12
            if current_sum == target:
                return current_sum
            if abs(current_sum - target) < abs(closest_sum - target):  # STEP 5, 8, 13
                closest_sum = current_sum
            if current_sum < target:  # STEP 6, 9
                left += 1
            else:  # STEP 14
                right -= 1
    return closest_sum  # STEP 16

📊

3Sum Closest - Watch the Algorithm Execute, Step by Step

Watching each pointer move and each sum comparison helps you understand how the algorithm narrows down to the closest sum efficiently without checking all triplets.

move_right

-4

0

-1

1

1

2

2

3

record

-4

0

-1

1

1

2

2

3

Result: -4

compare

i

-4

0

left

-1

1

1

2

right

2

3

Result: -4

compare

i

-4

0

left

-1

1

1

2

right

2

3

Result: -4

record

i

-4

0

left

-1

1

1

2

right

2

3

Result: -3

move_left

i

-4

0

-1

1

left

1

2

right

2

3

Result: -3

compare

i

-4

0

-1

1

left

1

2

right

2

3

Result: -3

record

i

-4

0

-1

1

left

1

2

right

2

3

Result: -1

move_left

i

-4

0

-1

1

1

2

right

2

3

Result: -1

traverse

i

-4

0

-1

1

1

2

right

2

3

Result: -1

traverse

-4

0

i

-1

1

left

1

2

right

2

3

Result: -1

compare

-4

0

i

-1

1

left

1

2

right

2

3

Result: -1

record

-4

0

i

-1

1

left

1

2

right

2

3

Result: 2

move_right

-4

0

i

-1

1

right

1

2

2

3

Result: 2

traverse

-4

0

i

-1

1

right

1

2

2

3

Result: 2

record

-4

0

-1

1

1

2

2

3

Result: 2

Key Takeaways

✓ Sorting the array is crucial to enable the two-pointer technique for efficient sum exploration.

Without sorting, we cannot reliably move pointers to increase or decrease sums.

✓ The two-pointer approach reduces the problem from O(n^3) to O(n^2) by smartly moving pointers based on sum comparisons.

This visualizes how pointer movements correspond to increasing or decreasing sums.

✓ Updating the closest sum dynamically ensures we always remember the best candidate without checking all triplets.

Seeing the closest_sum update step-by-step clarifies why early returns or pointer moves are made.

Practice

1. Consider the following Python function that finds the minimum difference between k closest elements in an array. What is the returned value when arr = [4, 1, 7, 9] and k = 2?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 4, 7, 9].

2. Step 2: Slide window of size 2 and compute differences

   Windows: [1,4] diff=3, [4,7] diff=3, [7,9] diff=2. Minimum difference is 2.

3. Step 3: Re-examine calculations

   Check carefully: differences are 3, 3, and 2. Minimum is 2, so answer is 2.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Minimum difference between any two sorted elements is 2 [OK]

Hint: Sort array, check adjacent pairs for min difference [OK]

Common Mistakes:

• Off-by-one error in window boundaries
• Confusing difference calculation with max-min of unsorted subset
• Returning 0 prematurely without checking all windows

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. Consider the following buggy code for Two Sum II using binary search. Which line contains the subtle bug that may cause incorrect results?

medium

A. Line checking if j != -1

B. Line calling binary_search with left=0 instead of i+1

C. Line returning [i + 1, j + 1]

D. Line calculating complement = target - numbers[i]

Solution

1. Step 1: Identify binary search call parameters

   Binary search should start from i+1 to avoid reusing the same element or previous elements.

2. Step 2: Analyze impact of starting from 0

   Starting from 0 may find the same element at index i, causing incorrect pairs or duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct binary search range is i+1 to n-1, not 0 to n-1 [OK]

Hint: Binary search must exclude current index to avoid duplicates [OK]

Common Mistakes:

• Searching entire array instead of subarray
• Off-by-one in indices
• Incorrect complement calculation

4. Examine the following code snippet intended to check if a string is a valid palindrome ignoring case and non-alphanumeric characters. Which line contains a subtle bug that can cause incorrect results on inputs like "A man, a plan, a canal: Panama"?

def isPalindrome(s: str) -> bool:
    cleaned = [ch for ch in s if ch.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left].lower() != cleaned[right].lower():
            return False
        left += 1
        right -= 1
    return True

medium

A. Line 5: if cleaned[left].lower() != cleaned[right].lower(): (case normalization done here)

B. Line 2: cleaned = [ch for ch in s if ch.isalnum()] (missing lowercasing during cleaning)

C. Line 4: while left < right: (correct loop condition)

D. Line 7: right -= 1 (correct pointer decrement)

Solution

1. Step 1: Identify where case normalization occurs

   Case normalization is done inside the loop condition, not during cleaning.

2. Step 2: Understand impact of missing lowercasing in cleaning

   Since cleaned list stores original case, repeated .lower() calls in loop are inefficient but correct; however, this is not a bug causing incorrect results.

3. Step 3: Re-examine line 2

   Line 2 does not lowercase characters, but line 5 does, so no bug here.

4. Step 4: Check for subtle bug

   Actually, no bug in case normalization, but if line 2 did not skip non-alphanumeric characters, that would cause errors. Here, line 2 correctly filters non-alnum.

5. Step 5: Reconsider options

   None of the lines have a bug causing incorrect results on the example input.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Missing lowercasing in cleaning is not a bug since it's done later [OK]

Hint: Case normalization can be done either during cleaning or comparison [OK]

Common Mistakes:

• Not skipping non-alphanumeric characters
• Not normalizing case consistently
• Off-by-one errors in pointer movement

5. 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