Leetcode 15. 3Sum

Показать описание

Leetcode 15. 3Sum

My contact details

You can practice for coding interview from here

I am Mohammad Fraz , a final year Engineer at DTU and I create content for Coding and technical interviews for FAANG. I explain the intuition to solve Data Structure and Algorithm Questions from leetcode and other platforms. I also cover interview experiences for FAANG and other tech giants. You will also find lectures on the frequently asked interview questions.

Рекомендации по теме

Комментарии

i liked u intentionally created errors and then resolved .

parwana

Fraz your explanation is very simple.finally i understood the problem after watching 5 videos of different youtubers.please make more videos of leetcode problems.

ankitgaur

Optimal solution
With the previous analysis, we can use the same technique on the 3sum question. As 2sum solution, let’s sort the array first. Now if we fix one number X in the array, the problem becomes finding 2 numbers that sum up to -X, which is exactly the 2sum question and can be solved in O(N) time.

Therefore, we can iterate over each number and inside the loop, solve the sub-problem as 2sum. To calculate the time complexity, sorting is O(NlogN), the outside loop is O(N) and the inside 2sum is O(N). Therefore, the overall time complexity is O(N^2) and space complexity is O(1)

DPCODE

Bhaiya it would be more efficient if you explain us the intuition of your dry run behind the code. as after getting such errors personally i won't able to figure out what next can be done now. as all the logic that one can think of is already applied .

SaradRana

class Solution{
public:
vector<vector<int>> threeSum(vector<int>&nums){
int n=nums.size();
if(n<3){
return {};
}
sort(nums.begin(), nums.end());
vector<vector<int>> ans;

for(int i=0;i<n-2;i++){
int j=i+1;int k=n-1;
if( i==0 || nums[i]!=nums[i-1]){
while(j<k){
int sum=nums[i]+nums[j]+nums[k];
if(sum==0){
ans.push_back({nums[i], nums[j], nums[k]});
while(j<k && nums[j]==nums[j+1]){
j++;
}

k--;
}
j++;
k--;
}
else if(sum>0){
k--;
}
else j++;
}

}
}
return ans;

}
};

dice