algoadvance

Given an array nums of n integers 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.

Clarifying Questions

  1. What is the range of values for nums and target?
    • The array nums can contain both positive and negative integers. The value of n (number of elements in nums) can vary but is generally within the range of 3 to 1000. The target can also be any integer.
  2. Can nums contain duplicate numbers?
    • Yes, the array nums can contain duplicate numbers.
  3. Should we consider edge cases for very small or large arrays?
    • Yes, but since the problem states that there will be exactly one solution, we can focus on the typical scenarios and ensure our solution works efficiently for larger arrays.

Strategy

To solve the problem effectively, we can follow these steps:

  1. Sort the Array: Start by sorting the array. This helps in efficiently using the two-pointer technique.
  2. Initialize Result: Initialize the variable to store the closest sum found so far.
  3. Iterate with Two Pointers:
    • Iterate through the array, fixing one element at a time.
    • Use two pointers (one starting just after the fixed element and the other starting at the end of the array) to find the best pair that gives the closest sum to the target when added to the fixed element.
  4. Update Closest Sum: For each combination, calculate the sum. If this sum is closer to the target than any previously found sums, update the closest sum.
  5. Adjust Pointers: Adjust the pointers based on whether the current sum is greater or less than the target.

Code

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = float('inf')  # Initialize with infinity

    for i in range(n - 2):
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            # 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:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                # If the sum is exactly equal to the target, return it
                return target
    
    return closest_sum

# Example usage
nums = [-1, 2, 1, -4]
target = 1
print(threeSumClosest(nums, target))  # Output: 2

Time Complexity

  1. Sorting the Array: This takes (O(n \log n)).
  2. Main Loop: The main iteration runs in (O(n)).
  3. Two-Pointer Search: For each fixed element, the two-pointer search takes (O(n)).

Therefore, the overall time complexity is (O(n^2)) due to the nested loop and two-pointer combination, which is efficient for the given constraints.

Try our interview co-pilot at AlgoAdvance.com