3Sum Closest medium

Problem Statement

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.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

Steps

1. Sort the array: Sorting the array allows us to use a two-pointer approach efficiently.

2. Iterate and use two pointers: Iterate through the array using a single pointer i. For each element at index i, use two pointers left and right to find a pair that, when added to nums[i], gets closest to the target. left starts at i + 1 and right starts at the end of the array.

3. Adjust pointers: Based on the current sum, adjust left or right to get closer to the target. If the sum is less than the target, move left to the right; if the sum is greater than the target, move right to the left.

4. Track the closest sum: Maintain a variable closest_sum to keep track of the sum that is closest to the target so far. Update closest_sum whenever a closer sum is found.

Explanation

The algorithm leverages the fact that a sorted array allows for efficient searching for a target sum. By iterating through the array with one pointer and using two pointers to explore possible pairs, we systematically check all possible combinations of three numbers without redundant calculations. The sorting step improves the time complexity. The two-pointer approach within the loop helps optimize the search for the closest sum in each iteration.

Code

def threeSumClosest(nums, target):
    """
    Finds the sum of three integers in nums closest to target.

    Args:
        nums: A list of integers.
        target: The target integer.

    Returns:
        The sum of three integers closest to target.
    """

    n = len(nums)
    nums.sort()  # Sort the array
    closest_sum = float('inf')  # Initialize closest_sum to a large value

    for i in range(n - 2):
        left = i + 1
        right = n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1  # Move left pointer to increase sum
            elif current_sum > target:
                right -= 1  # Move right pointer to decrease sum
            else:
                return target # Exact match found

    return closest_sum

Complexity

• Time Complexity: O(n^2), dominated by the nested loops. The sorting step is O(n log n), but it's less significant than the nested loops.
• Space Complexity: O(1). We are using a constant amount of extra space (excluding the input array). The sorting done in-place doesn't count towards space complexity.