16. 3Sum Closest

Problem Description

The LeetCode problem asks us to find three numbers within an array nums such that their sum is closest to a given target value. The array nums has a length n, and it's guaranteed that there is exactly one solution for each input.

To solve this problem, we must search for triplets in the array whose sum has the smallest absolute difference from the target. The final result is not the triplet itself, but rather the sum of its components.

Intuition

The intuition behind the provided solution leverages a sorted array and a two-pointer technique for efficient searching. Here's a step-by-step breakdown of the approach:

Sorting: We first sort the nums array. Sorting is crucial because it allows us to efficiently sweep through the array using two pointers and easily adjust the sum of the current triplet to get closer to the target.
Iterating with Three Pointers: We use a for-loop to iterate over the array with an index i representing the first number of the triplet. The other two pointers, j and k, are initialized to the next element after i and the last element of the array, respectively. The three numbers represented by i, j, and k are our current candidates for the closest sum.
Evaluating Sums and Moving Pointers: In the while-loop, we calculate the sum of the triplet (t) and compare it to the target. If the sum exactly matches the target, we immediately return it.

If the sum doesn't match, we compare the absolute difference of t and target with the current closest sum (ans), and if it's smaller, we update ans.

To search through different sums, we move pointers j and k depending on whether the current sum is greater than or less than target. If it's greater, we decrement k to reduce the sum. If it's less, we increment j to increase the sum. This is possible without missing the potential answers because the array is sorted.

By analyzing the difference between t and target and adjusting j and k accordingly, we can efficiently find the triplet with the sum that has the smallest absolute difference to the target.

Returning the Answer: Once we've finished iterating through all possible triplets, we return the closest sum recorded as ans.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The algorithm implementation utilizes several important concepts and patterns:

Sorting: The array is initially sorted to simplify the searching process. By having the array in ascending order, we can make use of the two-pointer technique effectively.
Two-Pointer Technique: After fixing one number of the potential triplet using the first for-loop, the two other numbers are controlled by two pointers. One starts right after the fixed element (j), while the other starts from the end of the array (k). These pointers move closer to each other as they iterate.
Avoiding Redundancy: Since each number in nums is used as a starting point for a triplet, the solution avoids re-examining numbers that are identical to the previous starting point (i position) by skipping duplicate combinations. (This is implicit and can be added to optimization in the code if necessary by checking for the same numbers when incrementing i).
Closest Sum Calculation: As the pointers j and k move, the solution calculates the sum of the three numbers, compares it with the target, and keeps track of the closest sum encountered by comparing the absolute differences with the current best answer (ans).
Conditional Pointer Movement: Based on whether the current sum is greater than or less than target, k is decremented or j is incremented respectively. This allows the solution to narrow down the closest sum without checking all possible triplet combinations, which would result in higher computational complexity.
Early Termination: If at any point the sum equals the target, the loop breaks and returns the sum immediately since it cannot get any closer than an exact match.
Return Statement: After going through all possible iterations, the algorithm returns the sum stored in ans, which is the closest sum to target that the solution could find during the iteration process.

The code uses a simple inf value to initialize ans so that any other sum found will be closer compared to infinity. Utilizing this approach, the data structure (a single array) is kept simple, and the algorithm achieves a time complexity of O(n^2), since it only involves iterating over the array of length n and adjusting the pointers without nested full iterations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach using the strategy detailed in the content provided.

Suppose we have the following nums array and target:

nums = [-1, 2, 1, -4]
target = 1

Firstly, according to our approach, we need to sort the nums:

sorted_nums = [-4, -1, 1, 2]

Now we iterate through sorted_nums with our three pointers. For simplicity, I'll walk through the first complete iteration:

Set i = 0, which is the value -4. This is our first number of the potential triplet.
Initialize two other pointers, j = i + 1 => j = 1 (value -1) and k = n - 1 => k = 3 (value 2).
We then enter a while loop with j < k and calculate the sum t using sorted_nums[i], sorted_nums[j], and sorted_nums[k]. So, our first sum is t = (-4) + (-1) + (2) = -3.
Since our goal is to get the sum close to target (1), we check the absolute difference between t and target. Abs(-3 - 1) = Abs(-4) = 4.
We initialize our answer ans with infinity. Our first comparison will set ans = -3 as it's the closest sum we've encountered.
t is less than target, we increment j to increase the sum. Now, j = 2 (value 1).
Calculate a new sum: t = (-4) + (1) + (2) = -1.
Compare the new sum's absolute difference with target. Abs(-1 - 1) = 2, which is closer to the target than our previous best of 4. Update ans to -1.
Since -1 is still less than the target, we increment j once again. Now, j = 3 which is equal to k, so we break out of the while-loop.
The loop for the index i continues, but for the sake of brevity, let's assume the remaining iterations do not find a sum closer to the target than the sum when ans was -1.

With these steps completed, we assert that the closest sum to the target we have found using this method is -1. As per our algorithm's implementation, -1 will be the final answer returned.

Note that for a real implementation, the process would involve iterating over all valid i, j, and k combinations until the end of the array is reached, continuously updating ans if closer sums are found, and potentially breaking early if an exact match is found. However, this simple example serves to convey the essentials of the solution approach.

Solution Implementation

1class Solution:
2    def threeSumClosest(self, nums: List[int], target: int) -> int:
3        # Sort the list to apply the two-pointer approach
4        nums.sort()
5        n = len(nums)
6      
7        # Initialize the answer with infinity to ensure any sum will be closer to target
8        closest_sum = float('inf')
9      
10        # Iterate through each number in the sorted list
11        for i in range(n - 2):  # last two elements will be covered by the two pointers
12            left_pointer = i + 1
13            right_pointer = n - 1
14          
15            # Use two pointers to find the closest sum for the current element nums[i]
16            while left_pointer < right_pointer:
17                current_sum = nums[i] + nums[left_pointer] + nums[right_pointer]
18              
19                # If the sum is exactly the target, return the sum immediately
20                if current_sum == target:
21                    return current_sum
22              
23                # Update the closest sum if the current one is closer to target
24                if abs(current_sum - target) < abs(closest_sum - target):
25                    closest_sum = current_sum
26              
27                # Move the pointers accordingly to get closer to target
28                if current_sum > target:
29                    right_pointer -= 1  # Decrease sum by moving right pointer left
30                else:
31                    left_pointer += 1  # Increase sum by moving left pointer right
32      
33        # Return the closest sum after checking all triples
34        return closest_sum
35```
36
37Please note that in the comments as well as the code, `List` and `inf` are assumed to be imported from the appropriate modules, which should be included when running the code in a complete script:
38
39```python
40from typing import List
41from math import inf
42

1// Class name should be descriptive and use PascalCase
2class Solution {
3    // Method names in camelCase, which is already followed here
4    public int threeSumClosest(int[] nums, int target) {
5        // Sort the array to have numbers in ascending order
6        Arrays.sort(nums);
7      
8        // Initialize the answer with a large value for comparison purposes
9        int closestSum = Integer.MAX_VALUE;
10      
11        // The length of the numbers array
12        int length = nums.length;
13      
14        // Iterate through each number in the array
15        for (int i = 0; i < length; ++i) {
16            // Initialize two pointers, one just after the current number and one at the end of the array
17            int left = i + 1;
18            int right = length - 1;
19          
20            // Continue as long as the left pointer is less than the right pointer
21            while (left < right) {
22                // Calculate the current sum of the three numbers
23                int currentSum = nums[i] + nums[left] + nums[right];
24              
25                // If the current sum is equal to the target, return it immediately as the closest sum
26                if (currentSum == target) {
27                    return currentSum;
28                }
29              
30                // If the current sum is closer to the target than the previous sum,
31                // update closestSum with the current sum
32                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
33                    closestSum = currentSum;
34                }
35              
36                // Move pointers based on how currentSum compares to the target
37                if (currentSum > target) {
38                    // If currentSum is greater than the target,
39                    // move the right pointer to the left to reduce the sum
40                    --right;
41                } else {
42                    // If currentSum is less than the target,
43                    // move the left pointer to the right to increase the sum
44                    ++left;
45                }
46            }
47        }
48      
49        // Return the closest sum found
50        return closestSum;
51    }
52}
53

1#include <vector>
2#include <algorithm>  // for sort function
3#include <cstdlib>    // for abs function
4
5class Solution {
6public:
7    int threeSumClosest(std::vector<int>& nums, int target) {
8        // First, sort the input vector in non-decreasing order
9        std::sort(nums.begin(), nums.end());
10      
11        // Initialize the closest sum to a very large value
12        int closestSum = INT_MAX;
13        // Calculate the size of the input vector
14        int numSize = nums.size();
15      
16        // Iterate through each element of the vector
17        for (int i = 0; i < numSize; ++i) {
18            // Set pointers for the current element, next element, and the last element
19            int leftPointer = i + 1, rightPointer = numSize - 1;
20          
21            // Use a while loop to check the sums with the current element
22            while (leftPointer < rightPointer) {
23                // Calculate the sum of the three elements
24                int sum = nums[i] + nums[leftPointer] + nums[rightPointer];
25              
26                // If the exact sum is found, return it
27                if (sum == target) {
28                    return sum;
29                }
30              
31                // Update closestSum if the current sum is closer to the target
32                if (std::abs(sum - target) < std::abs(closestSum - target)) {
33                    closestSum = sum;
34                }
35              
36                // Move the right pointer left if the sum is greater than the target
37                if (sum > target) {
38                    --rightPointer;
39                } else {
40                    ++leftPointer;  // Otherwise, move the left pointer right
41                }
42            }
43        }
44      
45        // Return the closest sum found
46        return closestSum;
47    }
48};
49

1function threeSumClosest(nums: number[], target: number): number {
2    // Sort the array in non-decreasing order
3    nums.sort((a, b) => a - b);
4
5    // Initialize the answer with the maximum safe integer value
6    let closestSum: number = Number.MAX_SAFE_INTEGER;
7
8    // Get the length of the nums array
9    const length = nums.length;
10
11    // Iterate over the array to find the three numbers
12    for (let i = 0; i < length; ++i) {
13        // Set pointers for the current element, next element, and the last element
14        let left = i + 1;
15        let right = length - 1;
16      
17        // While the left pointer is less than the right pointer
18        while (left < right) {
19            // Calculate the current sum of the triplets
20            const currentSum: number = nums[i] + nums[left] + nums[right];
21          
22            // If the current sum exactly equals the target, return the current sum
23            if (currentSum === target) {
24                return currentSum;
25            }
26          
27            // If the current sum is closer to the target than the previous closest, update the closestSum
28            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
29                closestSum = currentSum;
30            }
31          
32            // If the current sum is greater than the target, move the right pointer to find a smaller sum
33            if (currentSum > target) {
34                --right;
35            } else { // If the current sum is less, move the left pointer to find a larger sum
36                ++left;
37            }
38        }
39    }
40  
41    // Return the closest sum found
42    return closestSum;
43}
44

Time and Space Complexity

Time Complexity

The time complexity of the given function depends on a few distinct steps:

Sorting the array: The sort() method in Python uses the Timsort algorithm, which has a time complexity of O(n log n), where n is the length of the list being sorted.
The for-loop: The loop runs for each element in the sorted array, resulting in a complexity of O(n) iterations.
The while-loop inside the for-loop: In the worst case, for each iteration of the for-loop, the while-loop can perform nearly O(n) operations since it might iterate from i+1 to the n-1 index.

Combining these complexities, the first step is dominant if n is large. However, since the nested loop inside the for-loop could potentially run n times for each n iterations of the for-loop, the resulting time complexity is O(n^2), since n(n-1)/2 simplifies to O(n^2). This nested loop is the most influential factor for large n.

So, the overall time complexity of the algorithm is O(n log n) + O(n^2), which simplifies to O(n^2) since the O(n^2) term is dominant for large n.

Space Complexity

The space complexity is O(1) if we ignore the space used for input and output since the sorting is done in-place and only a fixed number of variables are used, which does not scale with the size of the input array.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know