Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Analysis:
1. How to define the "closest" to the target?
Given a target x, we could have an array of sum[] of each equals to the sum of three integers, so the closet is defined as distance = abs(sum[i] - target) and find the minimum distance. In this scenario, for the target x = 2, we can see that both 1 and 3 are closet to the target.
2. The problem assumes that each input would have exactly one solution, so it is safe to return the value once we found.
Follow-up: What if there exists multiple solutions and required to return all triplets?
We may store the results into an arrayList, which is similar to the 3sum problem.
3. What is the return value? In this problem, what is returned is the sum of the triplet, of which is closest to the target.
Naive Solution:
A native solution is to pick up each 3 elements from the array, and check the distance between its sum to the target. Use a hash table of which the key stores the distance, and value stores the sum of the triplet. At the end, we find the minimum distance in the hash table. Since the key in the hash table is always sorted, so the first pair is closest to the target. In this solution, finding the triplet takes O(n^3) time. Since the operations related to the hash table takes O(1) time, the overall time complexity is O(n^3). Since hash table needs additional O(n^3) space, the space complexity is O(n^3). In this problem, since we assume that there is exactly only one solution existed, one optimization is we return the sum if it equals to 0, i.e, the sum equals to the target. For the case that duplicated triplets exist, a key in the hash table may have two values. For instance, for the distance to 1 equals to 4, the sum could be either 5 or -3. In this case, we need a arrayList to store the value in the hash table. The implementation is omitted. We are aiming to look for a better solution.
A Better Solution:
Remember that in the 3sum problem we use two pointers to achieve the time complexity of O(n^2) and space O(1), can we borrow the idea to this problem?
One thinking is do we really need a hash table to store distances and the corresponding sum? Note that we only need the minimum distance. Therefore, we only need to maintain a pair of minimal distance and its sum that we reduced the space complexity to constant. How about the time complexity? We could borrow the same idea in the 3sum. For a given array element num[i], use two pointers, start = i + 1 and end = length - 1. Then check the sum of num[i] + num[start] + num[end], and compute the distance to the target x, if it is equal to zero, immediately returns 0 and we're done. If the distance is less than zero, move the start and update the minimum pair, if the distance is larger than zero, move the end pointer and update the minimum pair. Following is the Java code:
Code (Java):
public class Solution {
public int threeSumClosest(int[] num, int target) {
int length = num.length;
Pair min = new Pair();
// Sort the array
Arrays.sort(num);
for (int i = 0; i < length - 2; i++) {
int start = i + 1;
int end = length - 1;
while (start < end) {
int sum = num[i] + num[start] + num[end];
int distance = sum - target;
if (distance == 0) return sum;
else if (distance < 0) start++;
else end--;
// update the pair
if (Math.abs(distance) < min.first) {
min.first = Math.abs(distance);
min.second = sum;
}
}
}
return min.second;
}
private class Pair {
private int first, second;
private Pair() {
first = Integer.MAX_VALUE; // store the distance
second = 0; // store the sum
}
}
}
Discussion:
We can see that this implementation has the time complexity of O(n^2), and space complexity of O(1). Note that we created a private class called Pair to store the pair of <distance, value>, and the initial value of the distance is MAX integer. The purpose is to make the condition true for the first time.
Hash Table Solution:
Remember that in the 3sum problem we also proposed a hash table based solution, which has the time complexity of O(n^2) as well, but requires additional O(n) space to store the key-value pairs. Can we borrow the similar idea to this problem? Probably very hard. In the 3sum problem hash table works because the answer always "hits" the key in the hash table. However, in the 3sum closest problem, the answer might be not existed in the hash table, it is only "closet" to a key in the table. As a result, it is very to achieve O(1) time complexity in determining if a key is existed in the table.
Summary:
In this question, we examined three ways in resolving the problem. During the code interview, it does not matter if you proposed a solution but finally found it does not work. But it is important that you analyze why it does not work and the possible work around.
Update on 7/12/18:
class Solution {
public int threeSumClosest(int[] nums, int target) {
int ans = nums[0] + nums[1] + nums[2];
// Sort the array
//
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int newTarget = target - nums[i];
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
// save the current result
//
int diff = Math.abs(nums[i] + nums[start] + nums[end] - target);
if (diff < Math.abs(ans - target)) {
ans = nums[i] + nums[start] + nums[end];
}
if (nums[start] + nums[end] == newTarget) {
return target;
} else if (nums[start] + nums[end] < newTarget) {
start++;
} else {
end--;
}
}
}
return ans;
}
}
No comments:
Post a Comment