Jobs

Interviews

Discussions

3Sum Closest

Medium

3Sum Closest

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums`?
Can the input array `nums` contain negative numbers, zeros, or floating-point numbers?
What is the range of values for both the elements in `nums` and the `target`?
Is it guaranteed that `nums` will always have at least three elements?
If multiple triplets have the same minimum difference from the target, is any one of them acceptable?

Brute Force Solution

Approach

The brute force approach to the 3Sum Closest problem is all about trying absolutely every possible combination of three numbers from the given set. We will calculate the sum of each combination and then compare it to our target value. The goal is to find the sum that is closest to the target, even if it's not an exact match.

Here's how the algorithm would work step-by-step:

Imagine you have a group of numbers and you need to pick any three numbers from this group.
Start by picking the first three numbers in the group.
Calculate their sum.
Now, compare this sum with the target number you are trying to get close to. Note how close you are.
Next, try a different set of three numbers. Maybe the first, second, and fourth numbers in the group.
Calculate the sum of this new set of three numbers.
Again, compare this new sum with the target number, and note how close you are.
Keep repeating this process. Try every single possible combination of three numbers from your group.
After trying every combination and calculating their sums, compare how close each sum was to the target number.
Finally, choose the sum that was the closest to the target number. This is your answer.

Code Implementation

def three_sum_closest_brute_force(numbers, target):
    closest_sum = float('inf')
    min_difference = float('inf')

    # Iterate through all possible combinations of three numbers
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):

            for third_index in range(second_index + 1, len(numbers)):

                current_sum = numbers[first_index] + numbers[second_index] + numbers[third_index]

                # Check if the current sum is closer to the target than the closest sum found so far
                current_difference = abs(current_sum - target)

                # Update the closest sum if the current difference is smaller
                if current_difference < min_difference:

                    min_difference = current_difference

                    # The closest sum needs to be updated
                    closest_sum = current_sum

    return closest_sum

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach considers every possible combination of three numbers from an input array of size n. This involves iterating through the array to choose the first number (n possibilities), then iterating through the remaining array to choose the second number (n-1 possibilities), and again to choose the third number (n-2 possibilities). Therefore, we are performing roughly n * (n-1) * (n-2) operations. This approximates to n * n * n, which simplifies to O(n^3).

Space Complexity

O(1) – The brute force approach, as described, calculates sums from every possible combination of three numbers but doesn't involve creating any auxiliary data structures like lists or hash maps to store intermediate results or track visited combinations. It only needs to store a few variables: the current sum, the closest sum found so far, and potentially a counter for iterations. The number of such variables is constant and independent of the input size N (the number of elements in the input array), resulting in constant auxiliary space.

Optimal Solution

Approach

The goal is to find three numbers in a list that add up to a value closest to a target number. Instead of checking every possible combination of three numbers, we'll use a more strategic approach to quickly narrow down the possibilities and find the closest sum.

Here's how the algorithm would work step-by-step:

First, sort the numbers in the list from smallest to largest. This allows us to make informed decisions about which numbers to consider.
Pick a number from the list. We'll call this our first number.
Now, imagine two pointers, one starting at the number immediately after our first number and the other starting at the very end of the list.
Add our first number to the numbers pointed to by these two pointers. Compare this sum to our target number.
If the sum is smaller than the target, move the left pointer (the one after our first number) one position to the right to consider a slightly larger number. This increases the sum.
If the sum is larger than the target, move the right pointer one position to the left to consider a slightly smaller number. This decreases the sum.
Keep track of the sum that is closest to the target as we move the pointers. Whenever we find a sum closer than the closest one we've found so far, update our closest sum.
Repeat steps 2-7 for each number in the list as the first number, making sure not to repeat calculations.
After going through the entire list, the closest sum we've tracked is the answer.

Code Implementation

def threeSumClosest(numbers, target):
    numbers.sort()
    closest_sum = float('inf')

    for i in range(len(numbers) - 2):
        # Avoid duplicate calculations by skipping same values.
        if i > 0 and numbers[i] == numbers[i - 1]:
            continue

        left_pointer = i + 1
        right_pointer = len(numbers) - 1

        while left_pointer < right_pointer:
            current_sum = numbers[i] + numbers[left_pointer] + numbers[right_pointer]

            # Update closest_sum if current_sum is closer to target.
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            if current_sum < target:
                # Need a larger sum, move left pointer to the right.
                left_pointer += 1

            elif current_sum > target:
                # Need a smaller sum, move right pointer to the left.
                right_pointer -= 1

            else:
                # Exact match found, the closest possible.
                return target

    return closest_sum

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first sorts the input array of size n, which takes O(n log n) time. After sorting, the algorithm iterates through each element of the array in a loop (outer loop). For each element, it uses a two-pointer approach to find the pair of elements whose sum, combined with the current element, is closest to the target. The two-pointer approach examines at most n elements in the worst case (inner loop). The sorting step is dominated by the nested loops with the two-pointer approach, leading to O(n * n) time complexity. Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The algorithm sorts the input array in place, which doesn't use any extra space. We also use a few variables to store the closest sum and the two pointers (left and right). The number of these variables remains constant regardless of the size of the input array (N). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return null or throw an IllegalArgumentException as there are no triplets to sum.
Input array with fewer than 3 elements	Return null or throw an IllegalArgumentException as three numbers are required for a sum.
Integer overflow when summing three large integers	Use a larger data type (long) to store the sum to prevent overflow.
Array contains duplicate numbers	The sorting approach inherently handles duplicates correctly as they are adjacent and will be processed in the loops without special consideration.
All numbers in the array are the same	The algorithm should still correctly calculate the sum of any three identical numbers and compare it to the target.
Array contains only negative numbers	The algorithm will correctly find the closest sum to the target, even if all numbers are negative.
Large input array with a wide range of integer values	Sorting ensures the algorithm has O(n log n) complexity, maintaining efficiency even with a large input size.
Target value is significantly larger or smaller than any possible sum of triplets	The algorithm will still find the triplet sum closest to the target, even if the difference is very large.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums`?
Can the input array `nums` contain negative numbers, zeros, or floating-point numbers?
What is the range of values for both the elements in `nums` and the `target`?
Is it guaranteed that `nums` will always have at least three elements?
If multiple triplets have the same minimum difference from the target, is any one of them acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a group of numbers and you need to pick any three numbers from this group.
Start by picking the first three numbers in the group.
Calculate their sum.
Now, compare this sum with the target number you are trying to get close to. Note how close you are.
Next, try a different set of three numbers. Maybe the first, second, and fourth numbers in the group.
Calculate the sum of this new set of three numbers.
Again, compare this new sum with the target number, and note how close you are.
Keep repeating this process. Try every single possible combination of three numbers from your group.
After trying every combination and calculating their sums, compare how close each sum was to the target number.
Finally, choose the sum that was the closest to the target number. This is your answer.

Code Implementation

def three_sum_closest_brute_force(numbers, target):
    closest_sum = float('inf')
    min_difference = float('inf')

    # Iterate through all possible combinations of three numbers
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):

            for third_index in range(second_index + 1, len(numbers)):

                current_sum = numbers[first_index] + numbers[second_index] + numbers[third_index]

                # Check if the current sum is closer to the target than the closest sum found so far
                current_difference = abs(current_sum - target)

                # Update the closest sum if the current difference is smaller
                if current_difference < min_difference:

                    min_difference = current_difference

                    # The closest sum needs to be updated
                    closest_sum = current_sum

    return closest_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort the numbers in the list from smallest to largest. This allows us to make informed decisions about which numbers to consider.
Pick a number from the list. We'll call this our first number.
Now, imagine two pointers, one starting at the number immediately after our first number and the other starting at the very end of the list.
Add our first number to the numbers pointed to by these two pointers. Compare this sum to our target number.
If the sum is smaller than the target, move the left pointer (the one after our first number) one position to the right to consider a slightly larger number. This increases the sum.
If the sum is larger than the target, move the right pointer one position to the left to consider a slightly smaller number. This decreases the sum.
Keep track of the sum that is closest to the target as we move the pointers. Whenever we find a sum closer than the closest one we've found so far, update our closest sum.
Repeat steps 2-7 for each number in the list as the first number, making sure not to repeat calculations.
After going through the entire list, the closest sum we've tracked is the answer.

Code Implementation

def threeSumClosest(numbers, target):
    numbers.sort()
    closest_sum = float('inf')

    for i in range(len(numbers) - 2):
        # Avoid duplicate calculations by skipping same values.
        if i > 0 and numbers[i] == numbers[i - 1]:
            continue

        left_pointer = i + 1
        right_pointer = len(numbers) - 1

        while left_pointer < right_pointer:
            current_sum = numbers[i] + numbers[left_pointer] + numbers[right_pointer]

            # Update closest_sum if current_sum is closer to target.
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            if current_sum < target:
                # Need a larger sum, move left pointer to the right.
                left_pointer += 1

            elif current_sum > target:
                # Need a smaller sum, move right pointer to the left.
                right_pointer -= 1

            else:
                # Exact match found, the closest possible.
                return target

    return closest_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return null or throw an IllegalArgumentException as there are no triplets to sum.
Input array with fewer than 3 elements	Return null or throw an IllegalArgumentException as three numbers are required for a sum.
Integer overflow when summing three large integers	Use a larger data type (long) to store the sum to prevent overflow.
Array contains duplicate numbers	The sorting approach inherently handles duplicates correctly as they are adjacent and will be processed in the loops without special consideration.
All numbers in the array are the same	The algorithm should still correctly calculate the sum of any three identical numbers and compare it to the target.
Array contains only negative numbers	The algorithm will correctly find the closest sum to the target, even if all numbers are negative.
Large input array with a wide range of integer values	Sorting ensures the algorithm has O(n log n) complexity, maintaining efficiency even with a large input size.
Target value is significantly larger or smaller than any possible sum of triplets	The algorithm will still find the triplet sum closest to the target, even if the difference is very large.