We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

3Sum Closest

Number: 16

Difficulty: Medium

Paid? No

Companies: Google, Meta, Bloomberg, Microsoft, Flipkart, Amazon, Zoho, Adobe, Apple, Uber, Yahoo, Nvidia

Problem Description

Given an integer array and a target value, the task is to find three integers in the array such that their sum is closest to the target. You are guaranteed that each input will have exactly one solution, and you should return the sum of the three chosen integers.

Key Insights

  • Sort the array to make it easier to use the two pointers technique.
  • Fix one element and then use two pointers (left and right) to find the best pair that, along with the fixed element, produces a sum closest to the target.
  • Update the best sum whenever a closer sum is found.
  • The sorted order helps eliminate unnecessary iterations and allows efficient movement of pointers.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(log n) to O(n) depending on the sorting algorithm used (typically in-place sort, so extra space might be minimal)

Solution

The solution starts by sorting the array. For each index in the array (considered as the first element of the triple), we use two pointers: one starting just after the fixed element and the other at the end of the array. We calculate the sum of the fixed element and the two pointers. If this sum is closer to the target than the current best, we update our best sum. Depending on whether the current sum is less than or greater than the target, we adjust the left or right pointer to try and get closer to the target. This two-pointer method leverages the sorted order of the array for efficient summing.

Code Solutions

# Python solution for 3Sum Closest
def threeSumClosest(nums, target):
    # Sort the array to allow two pointer technique
    nums.sort()
    # Initialize best_sum with the sum of the first three elements
    best_sum = sum(nums[:3])
    
    # Iterate through each number as the fixed element
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        # Use two pointers to check pairs
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            # Update best_sum if current_sum is closer to target
            if abs(target - current_sum) < abs(target - best_sum):
                best_sum = current_sum
            # Move left pointer if current_sum is less than target to increase sum
            if current_sum < target:
                left += 1
            # Move right pointer if current_sum is greater than target to decrease sum
            elif current_sum > target:
                right -= 1
            else:
                # If the current_sum exactly equals target, return the target sum
                return current_sum
    # Return the closest sum found
    return best_sum

# Example usage:
# print(threeSumClosest([-1,2,1,-4], 1))
← Back to All Questions