SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The threeSumClosest problem requires finding three integers in an array such that the sum is closest to a given target value. The goal is to return the sum of the three integers that is closest to the target. If multiple sums are equally close, any of them can be returned.

Intuition

The brute-force approach of checking all possible triplets to find the closest sum is inefficient for larger inputs due to its (O(n^3)) time complexity. A more optimal approach leverages sorting and the two-pointer technique, allowing us to reduce the number of comparisons and efficiently find the closest sum.

Approach

1. Sort the Array: Begin by sorting the input array. Sorting helps in applying the two-pointer technique.

2. Iterate through the Array: Iterate through the array, fixing one element at a time.

3. Two-pointer Technique: For each fixed element, use two pointers—one starting just after the fixed element and the other starting at the end of the array. Adjust these pointers based on whether the current sum is less than or greater than the target:

   • If the current sum is less than the target, move the left pointer to the right to increase the sum.
   • If the current sum is greater than the target, move the right pointer to the left to decrease the sum.

4. Update Closest Sum: Track the closest sum found during the iteration. If the current sum is closer to the target than the previously recorded closest sum, update the closest sum.

5. Return the Closest Sum: After processing all elements, return the closest sum found.

Complexity

Time Complexity

(O(n^2)). Sorting the array takes (O(n \log n)), and the two-pointer technique runs in (O(n^2)) time.

Space Complexity**:

(O(1)), as the solution only uses a constant amount of extra space.

Code

C++

class Solution {
public:
    int threeSumClosest(std::vector<int>& nums, int target) {
        int closestSum = std::numeric_limits<int>::max();
        int closestDifference = std::numeric_limits<int>::max();
        
        for (int i = 0; i < nums.size() - 2; i++) {
            for (int j = i + 1; j < nums.size() - 1; j++) {
                for (int k = j + 1; k < nums.size(); k++) {
                    int currentSum = nums[i] + nums[j] + nums[k];
                    int currentDifference = std::abs(currentSum - target);
                    
                    if (currentDifference < closestDifference) {
                        closestDifference = currentDifference;
                        closestSum = currentSum;
                    }
                }
            }
        }
        
        return closestSum;
    }
};

Python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest_sum = float('inf')
        
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                # If the current sum is exactly the target, return it
                if current_sum == target:
                    return current_sum
                
                # Update the closest sum if the current one is closer
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
                
                # Move the pointers
                if current_sum < target:
                    left += 1
                else:
                    right -= 1
        
        return closest_sum

Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closestSum = Integer.MAX_VALUE;
        int closestDifference = Integer.MAX_VALUE;
        
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int currentSum = nums[i] + nums[j] + nums[k];
                    int currentDifference = Math.abs(currentSum - target);
                    
                    if (currentDifference < closestDifference) {
                        closestDifference = currentDifference;
                        closestSum = currentSum;
                    }
                }
            }
        }
        
        return closestSum;
    }
}

JavaScript

var threeSumClosest = function (nums, target) {
    let closestSum = Number.MAX_SAFE_INTEGER;
    let closestDifference = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                let currentSum = nums[i] + nums[j] + nums[k];
                let currentDifference = Math.abs(currentSum - target);

                if (currentDifference < closestDifference) {
                    closestDifference = currentDifference;
                    closestSum = currentSum;
                }
            }
        }
    }

    return closestSum;
};