grid47 Exploring patterns and algorithms
Nov 5, 2024
5 min read
Solution to LeetCode 16: 3Sum Closest Problem
You are given an integer array nums and an integer target. Find three integers in nums such that the sum is closest to the target. Return the sum of those three integers.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array nums and an integer target.
Example: nums = [1, 2, 3, -4], target = 3
Constraints:
• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4
Output: Return the sum of the three integers whose sum is closest to the target.
Example: 3
Constraints:
• The sum should be the closest to the target.
Goal: Find three integers in the array whose sum is closest to the given target.
Steps:
• Sort the input array.
• Iterate through the array, fixing one element and using a two-pointer technique to find the other two elements.
• Track the sum of the triplet and check how close it is to the target.
• Return the closest sum.
Goal: The array has at least 3 elements and the target is within the range [-10^4, 10^4].
Steps:
• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4
Assumptions:
• There is exactly one solution, so there is no need to check for multiple solutions.
• Input: nums = [1, 2, 3, -4], target = 3
• Explanation: The closest sum to the target is 3. (1 + 2 + 3 = 3).
• Input: nums = [0, 0, 0], target = 5
• Explanation: The closest sum to the target 5 is 0. (0 + 0 + 0 = 0).
Approach: The approach to solving this problem involves sorting the array first and then using the two-pointer technique to find the closest sum.
Observations:
• Sorting helps in finding the closest sum using the two-pointer technique efficiently.
• The problem requires comparing the sum of different triplets and finding the one closest to the target.
• We need to iterate through the array, fixing one element and using two pointers to explore potential sums.
Steps:
• Sort the array in ascending order.
• Fix one element and use two pointers to find the closest sum by adjusting the pointers based on whether the sum is greater or less than the target.
• Keep track of the closest sum found during the iteration and return it.
Empty Inputs:
• The input array will always have at least 3 elements.
Large Inputs:
• The solution should be efficient for arrays up to 500 elements.
Special Values:
• The array may contain both negative and positive numbers, which should be handled correctly.
Constraints:
• The solution should handle negative, zero, and positive numbers efficiently.
intthreeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int front;
int sum = nums[0] + nums[1] + nums[2], sum1 =0;
for(int i =0; i < nums.size(); i++) {
front = i +1;
int back = nums.size() -1;
while( front < back ) {
sum1 = nums[front] + nums[back] + nums[i];
if (abs(sum1-target) <= abs(sum-target)) sum = sum1;
if(sum1 > target) back--;
elseif(sum1 < target) front++;
elsereturn sum1;
}
}
return sum;
}
1 : Function Declaration
intthreeSumClosest(vector<int>& nums, int target) {
Declare the `threeSumClosest` function, which takes a vector of integers `nums` and a target integer `target` as input and returns the closest sum to the target.
2 : Sorting Operations
sort(nums.begin(),nums.end());
Sort the `nums` vector in ascending order.
3 : Variable Initialization
int front;
Declare a variable `front` to be used as a pointer in the two-pointer approach.
4 : Variable Initialization
int sum = nums[0] + nums[1] + nums[2], sum1 =0;
Initialize `sum` with the sum of the first three elements as an initial closest sum. Initialize `sum1` to store the current sum of three elements.
5 : Loop Iteration
for(int i =0; i < nums.size(); i++) {
Start a loop to iterate through each element `nums[i]` in the sorted array.
6 : Variable Initialization
front = i +1;
Initialize `front` to point to the element after `nums[i]`. This will be the left pointer in the two-pointer approach.
7 : Variable Initialization
int back = nums.size() -1;
Initialize `back` to point to the last element of the array. This will be the right pointer in the two-pointer approach.
8 : Loop Iteration
while( front < back ) {
Start a two-pointer loop to find the closest sum to the target.
9 : Calculations
sum1 = nums[front] + nums[back] + nums[i];
Calculate the sum of the current three elements `nums[i]`, `nums[front]`, and `nums[back]`.
10 : Conditional Update
if (abs(sum1-target) <= abs(sum-target)) sum = sum1;
Check if the absolute difference between the current sum `sum1` and the target is less than or equal to the current minimum difference. If so, update `sum` to the current `sum1`.
11 : Conditional Update
if(sum1 > target) back--;
If the current sum `sum1` is greater than the target, move the `back` pointer to the left to decrease the sum.
12 : Conditional Update
elseif(sum1 < target) front++;
If the current sum `sum1` is less than the target, move the `front` pointer to the right to increase the sum.
13 : Return Value
elsereturn sum1;
If the current sum `sum1` is exactly equal to the target, return it as the closest sum.
14 : Return Value
return sum;
Return the closest sum `sum` found after iterating through all possible triplets.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) because we iterate over the array and use two pointers to find the closest sum.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because no additional space is used except for a few variables.
