Link to the Problem
Thought Process
As we have already solved “Two Sum” problem already, let’s reuse our existing knowledge to solve this problem. We know the target and we want to search 3 numbers. We know how to search 2 numbers, so if we fix one number at a time and look for the other two numbers using our previous solution that would solve this problem as well. Say the target is N and we want to find numbers a, b, c. We will fix each number as a one by one and all we have to search for is two numbers b and c with the target sum N-a. This is precisely our “Two Sum” problem.
Video Explanation
Code
| /* Watch video explanation here: https://youtu.be/MmhfOzYMYPk */ | |
| class Solution { | |
| vector<vector<int>> ans; // Stores the final answer. | |
| /* Skip the duplicates. */ | |
| int increment(vector<int>& nums, int cur) { | |
| int n = nums.size(); | |
| int j=cur+1; | |
| while (j < n && nums[j] == nums[cur]) { | |
| j++; | |
| } | |
| return j; | |
| } | |
| /* Skip the duplicates. */ | |
| int decrement(vector<int>& nums, int cur) { | |
| int j=cur-1; | |
| while (j >= 0 && nums[j] == nums[cur]) { | |
| j--; | |
| } | |
| return j; | |
| } | |
| /* Pairs of numbers in array `nums` from index `start` to | |
| * index `end` with sum `target`. | |
| */ | |
| void twoSum(vector<int>& nums, int start, | |
| int end, int target, int a) { | |
| while (start < end) { | |
| if (nums[start]+nums[end] == target) { | |
| // Add the triple in the answer. | |
| ans.push_back({nums[start], nums[end], a}); | |
| start = increment(nums, start); | |
| end = decrement(nums, end); | |
| } else if (nums[start]+nums[end] < target) { | |
| start = increment(nums, start); | |
| } else { | |
| end = decrement(nums, end); | |
| } | |
| } | |
| } | |
| public: | |
| vector<vector<int>> threeSum(vector<int>& nums) { // Time: O(n^2) | |
| sort(nums.begin(), nums.end()); // O(nlogn) | |
| int n = nums.size(); | |
| for (int i=0; i<n; i=increment(nums, i)) { // n * | |
| int a = nums[i]; | |
| twoSum(nums, i+1, n-1, -a, a); // O(n) | |
| } | |
| return ans; | |
| } // Space: O(1) | |
| }; |
Is there anything that is still unclear? Let me know in the comments and I can elaborate further.
Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added. I have created a Youtube Channel for quicker explanation, so subscribe to the channel too.
Happy Coding!
