Leetcode 15. 3Sum

Link to the Problem

3Sum

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

Leetcode 15. 3Sum (Three Sum)
Leetcode 1. Two Sum - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms

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)
};
view raw Leetcode_15.cpp hosted with ❤ by GitHub

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!



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s