3Sum Closest

📋

Problem

Imagine you are planning a group trip and want to pick three activities whose total cost is as close as possible to your budget without going over.

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

3 ≤ n ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4-10^5 ≤ target ≤ 10^5

Edge cases: All elements are the same → sum is triple that elementArray contains negative and positive numbers → closest sum may cross zeroTarget is smaller than any possible sum → closest sum is minimum triple sum

</>

IDE

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

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

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: -1Returning the sum of the first three elements without checking all triplets.✅ Implement sorting and use two pointers to check all triplets for closest sum.

Wrong: 0Incorrect initialization of closest sum to zero causing wrong comparisons.✅ Initialize closest sum to sum of first three elements or use float('inf') and update properly.

Wrong: 3Failing to update closest sum when a closer sum is found due to incorrect comparison logic.✅ Update closest sum only if abs(current_sum - target) < abs(closest_sum - target).

Wrong: TLEUsing brute force O(n^3) approach on large inputs.✅ Use sorting and two pointers to achieve O(n^2) time complexity.

✓

Test Cases

Focus on handling edge cases like minimum and maximum values and exact target matches.

Pay attention to pointer boundaries and duplicate handling to avoid missing valid triplets.

Optimize your solution to O(n^2) time complexity to handle large inputs efficiently.

t1_01basic

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

Expected2

⏱ Performance - must finish in 2000ms

The sum that is closest to the target is 2 (-1 + 2 + 1 = 2).

💡 Sort the array first to use two pointers effectively.

💡 Fix one element and use two pointers to find the closest sum to target.

💡 Update closest sum when a closer sum is found during pointer moves.

Why it failed: Failed basic canonical case: likely incorrect pointer movement or update logic. Fix by sorting array and correctly updating closest sum when abs(current_sum - target) < abs(closest_sum - target).

✓ Correctly handles canonical example with proper two-pointer approach.

t1_02basic

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

Expected0

⏱ Performance - must finish in 2000ms

Sum of three zeros is 0, which is closest to target 1.

💡 Consider cases where all elements are identical.

💡 Sum of any three elements is triple that element.

💡 Return triple of the element if no closer sum found.

Why it failed: Fails when all elements are identical: likely missing handling of identical elements or incorrect initialization of closest sum. Fix by initializing closest sum properly and checking all triplets.

✓ Correctly handles all identical elements case.

t2_01edge

Input{"nums":[-10000,-10000,-10000],"target":-30000}

Expected-30000

⏱ Performance - must finish in 2000ms

Sum of three minimum elements equals target exactly.

💡 Check behavior with minimum possible values.

💡 Sum of three smallest elements may equal or be closest to target.

💡 Ensure no overflow and correct sum calculation with large negatives.

Why it failed: Fails minimum boundary test: likely incorrect handling of large negative values or overflow. Fix by using appropriate data types and summation logic.

✓ Correctly handles minimum boundary values.

t2_02edge

Input{"nums":[10000,10000,10000],"target":30000}

Expected30000

⏱ Performance - must finish in 2000ms

Sum of three maximum elements equals target exactly.

💡 Check behavior with maximum possible values.

💡 Sum of three largest elements may equal or be closest to target.

💡 Ensure no overflow and correct sum calculation with large positives.

Why it failed: Fails maximum boundary test: likely incorrect handling of large positive values or overflow. Fix by using appropriate data types and summation logic.

✓ Correctly handles maximum boundary values.

t2_03edge

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

Expected3

⏱ Performance - must finish in 2000ms

Sum of 0 + 1 + 2 = 3 matches target exactly.

💡 Check cases where target equals sum of some triplet exactly.

💡 Sorting helps find exact matches quickly.

💡 Return immediately if exact sum found.

Why it failed: Fails exact boundary test: likely missing early exit on exact match. Fix by returning sum immediately when current_sum == target.

✓ Correctly handles exact boundary sums.

t3_01corner

Input{"nums":[-1,2,1,-4,5],"target":10}

Expected8

⏱ Performance - must finish in 2000ms

Closest sum to 10 is 8 (2 + 1 + 5).

💡 Beware of greedy approaches that pick largest elements first.

💡 Sorting and two pointers help avoid greedy traps.

💡 Check all triplets systematically to find closest sum.

Why it failed: Fails greedy trap test: likely picks largest elements without checking all combinations. Fix by sorting and using two pointers to explore all valid triplets.

✓ Correctly avoids greedy trap and finds closest sum.

t3_02corner

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

Expected2

⏱ Performance - must finish in 2000ms

Closest sum to 3 is 2 (-1 + 1 + 2 or 0 + 1 + 1).

💡 Watch for off-by-one errors in pointer indices.

💡 Ensure pointers do not cross or skip valid triplets.

💡 Carefully update pointers and check sums at each step.

Why it failed: Fails off-by-one pointer test: likely incorrect pointer increments/decrements causing missed triplets. Fix by carefully managing pointer movement within bounds.

✓ Correctly handles pointer boundaries and finds closest sum.

t3_03corner

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

Expected0

⏱ Performance - must finish in 2000ms

Closest sum to 0 is 0 (-2 + 0 + 2).

💡 Check handling of duplicates and zero sums.

💡 Avoid skipping valid triplets due to duplicate values.

💡 Use sorting and careful pointer movement to handle duplicates.

Why it failed: Fails duplicate handling test: likely skips valid triplets due to duplicate skipping logic. Fix by only skipping duplicates when appropriate and checking all triplets.

✓ Correctly handles duplicates and finds closest sum.

t4_01performance

Input{"nums":[-10000,-9998,-9996,-9994,-9992,-9990,-9988,-9986,-9984,-9982,-9980,-9978,-9976,-9974,-9972,-9970,-9968,-9966,-9964,-9962,-9960,-9958,-9956,-9954,-9952,-9950,-9948,-9946,-9944,-9942,-9940,-9938,-9936,-9934,-9932,-9930,-9928,-9926,-9924,-9922,-9920,-9918,-9916,-9914,-9912,-9910,-9908,-9906,-9904,-9902,-9900,-9898,-9896,-9894,-9892,-9890,-9888,-9886,-9884,-9882,-9880,-9878,-9876,-9874,-9872,-9870,-9868,-9866,-9864,-9862,-9860,-9858,-9856,-9854,-9852,-9850,-9848,-9846,-9844,-9842,-9840,-9838,-9836,-9834,-9832,-9830,-9828,-9826,-9824,-9822,-9820,-9818,-9816,-9814,-9812,-9810,-9808,-9806,-9804,-9802],"target":5000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100, testing O(n^2) time complexity within 2 seconds.

💡 Sorting and two pointers yield O(n^2) time complexity.

💡 Brute force O(n^3) will time out on this input size.

💡 Optimize by early exit when exact sum found.

Why it failed: TLE on large input: brute force O(n^3) approach is too slow. Fix by implementing sorting + two pointers O(n^2) solution.

✓ Efficient O(n^2) solution passes performance test.

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 a sorted array and need to remove duplicates such that each element appears at most twice, modifying the array in-place. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Using a nested loop to count duplicates and shift elements accordingly

B. Using two pointers where the write pointer only advances if the current element differs from the element two positions before

C. Using a hash map to count occurrences and then reconstruct the array

D. Using dynamic programming to track the maximum allowed duplicates

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, and duplicates are allowed at most twice, so we can leverage order.

2. Step 2: Identify the approach that uses two pointers and index offset check

   This approach compares the current element with the element two positions before the write pointer to decide if it should be written, ensuring O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers with index offset check is the known optimal approach [OK]

Hint: Two pointers with offset check is optimal [OK]

Common Mistakes:

• Using nested loops causes O(n²) time
• Hash maps use extra space
• DP is unnecessary here

4. The following code attempts to count pairs with absolute difference at most K using binary search. Identify the line containing the subtle bug that causes incorrect counting for some inputs.

import bisect

def count_pairs_buggy(nums, K):
    count = 0
    n = len(nums)
    for i in range(n - 1):
        target = nums[i] + K
        j = bisect.bisect_right(nums, target, i) - 1
        if j > i:
            count += j - i
    return count

medium

A. Line 5: for i in range(n - 1):

B. Line 7: target = nums[i] + K

C. Line 8: j = bisect.bisect_right(nums, target, i) - 1

D. Line 9: if j > i:

Solution

1. Step 1: Understand bisect_right usage

   bisect_right should start searching from i + 1 to avoid counting pairs where j ≤ i.

2. Step 2: Identify bug in line 8

   Using i as the start index includes nums[i] itself, causing pairs with i == j or double counting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing i to i + 1 fixes the bug [OK]

Hint: bisect must start from i+1 to avoid invalid pairs [OK]

Common Mistakes:

• Starting binary search at i instead of i+1
• Off-by-one errors in bisect indices
• Counting pairs where i >= j

5. Suppose the input array is no longer sorted but you still need to return the squares of each number in sorted order. Which of the following approaches is correct and efficient?

hard

A. Square each element and then sort the resulting array using a standard sorting algorithm.

B. Use a max-heap to insert squares and extract them in sorted order.

C. Use the two-pointer approach from ends, as it works regardless of input order.

D. Modify the input array in place by squaring and then perform an in-place merge sort.

Solution

1. Step 1: Recognize input is unsorted

   Two-pointer approach relies on sorted input; it fails if input is unsorted.

2. Step 2: Choose a correct approach

   Squaring then sorting with a standard sort is correct and efficient (O(n log n)) for unsorted input.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting after squaring handles unsorted input correctly [OK]

Hint: Two-pointer requires sorted input; else sort after squaring [OK]

Common Mistakes:

• Applying two-pointer on unsorted input
• Using complex data structures unnecessarily
• Assuming in-place modifications preserve order