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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

3Sum Closest

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding a triplet in the array that minimizes the absolute difference between their sum and the target.
  • Sorting the array allows for an efficient two-pointer approach to find the closest sum.
  • By iterating through the array and using two pointers, we can explore possible combinations efficiently.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (ignoring the input array)

Solution

The solution involves the following steps:

  1. Sort the input array to facilitate the use of the two-pointer technique.
  2. Iterate through the array, treating each element as a potential first element of the triplet.
  3. For each first element, use two pointers (one at the start and one at the end of the remaining array) to find the best pair that, together with the first element, gives a sum closest to the target.
  4. Update the closest sum whenever a closer one is found.

The algorithm takes advantage of sorting to reduce the number of necessary comparisons.

Code Solutions

def threeSumClosest(nums, target):
    nums.sort()  # Sort the array
    closest_sum = float('inf')  # Initialize the closest sum as infinity

    for i in range(len(nums) - 2):  # Iterate through each number
        left, right = i + 1, len(nums) - 1  # Set two pointers
        
        while left < right:  # While pointers do not overlap
            current_sum = nums[i] + nums[left] + nums[right]  # Calculate the current sum
            # Update closest_sum if the current sum is closer to the target
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            
            if current_sum < target:  # Move left pointer to increase the sum
                left += 1
            elif current_sum > target:  # Move right pointer to decrease the sum
                right -= 1
            else:  # If current_sum is exactly the target, return it
                return current_sum

    return closest_sum  # Return the closest sum found
← Back to All Questions