Last active
November 1, 2020 13:07
-
-
Save Ch-sriram/b25b9e2ca718b306d45e322666154c27 to your computer and use it in GitHub Desktop.
3Sum Closest [TC: O(N^2); SC: O(1)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Problem Link: https://leetcode.com/problems/3sum-closest/ | |
// Test Link: https://ide.geeksforgeeks.org/EBNEOuStvx | |
// Solution Status: Accepted in Leetcode Online Judge | |
class Solution { | |
public: | |
// Approach: Two-Pointer Technique. Time Complexity: Quadratic O(N^2) -- because we fix one element, and for | |
// the remaining elements, we apply two-ptr technique. | |
int threeSumClosest(vector<int>& nums, int target) { | |
sort(nums.begin(), nums.end()); // sort the array to apply two-ptr technique | |
int closestSum = 1e8; // A very large number. Taking INT_MAX can cause overflow. | |
const int nums_size = nums.size(); | |
for(int i = 0; i < nums_size; ++i) { | |
// Fix one element: nums[i] and apply two ptr technique on the remaining elements | |
int p1 = i+1, p2 = nums_size - 1; | |
while(p1 < p2) { | |
int sum = nums[i] + nums[p1] + nums[p2]; | |
if(abs(target - closestSum) > abs(target - sum)) | |
closestSum = sum; | |
if(sum == target) return sum; | |
else if(sum < target) ++p1; | |
else --p2; | |
} | |
} | |
return closestSum; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem Link
Test Link