Time: 125 ms (66.18%), Space: 21 MB (48.23%) - LeetHub

JanaSabuj · JanaSabuj · commit 29b611d4f70d · 2022-08-13T22:59:38.000+05:30
diff --git a/15-3sum/15-3sum.cpp b/15-3sum/15-3sum.cpp
@@ -1,50 +1,72 @@
 class Solution {
 public:
-    vector<pair<int,int>> p2(int l, int r, vector<int>& nums, int sum) {
-        vector<pair<int,int>> vec;
-        while(l < r) {
-            if(nums[l] + nums[r] == sum) {
-                 vec.push_back({l, r});
-                 int ll = nums[l];
-                 int rr = nums[r];
-                 while(ll == nums[l] and l < r) l++;
-                 while(rr == nums[r] and l < r) r--;
+    vector<pair<int, int>> p2(int l, int r, vector<int>& nums, int sum) {
+        vector<pair<int, int>> vec;
+        while (l < r) {
+            if (nums[l] + nums[r] == sum) {
+                vec.push_back({l, r});
+
+
+                int ll = nums[l];
+                while (ll == nums[l] and l < r) l++;
+
+                int rr = nums[r];
+                while (rr == nums[r] and l < r) r--;
             }
-            else if(nums[l] + nums[r] < sum)
+            else if (nums[l] + nums[r] < sum)
                 l++;
             else
                 r--;
         }
 
         return vec;
     }
-    
+
     vector<vector<int>> threeSum(vector<int>& nums) {
         int n = nums.size();
         // [- - - - - - - -]
         // a + b + c = 0
-        sort(nums.begin(), nums.end());
-        vector<vector<int>> triplets;
+
+        sort(nums.begin(), nums.end());// sorted array
         
-        for(int i = 0; i < n - 2; ) {
-            int a = nums[i];
-            vector<pair<int,int>> p = p2(i+1,n-1,nums,-a);
+        // misc case
+        if(nums[n-1] < 0)
+            return {};
+        vector<vector<int>> triplets;
+
+        for (int i = 0; i < n - 2; i++) {
             
-            int sz = p.size();
+            // misc: 1st element is > 0, then not possible for triplet sum = 0
+            if(nums[i] > 0)
+                break;
             
-            if(sz) {
-                for(auto pp: p) {
-                    triplets.push_back({a, nums[pp.first], nums[pp.second]});
+            if (i == 0 or nums[i - 1] < nums[i]) {
+                // distinct i
+
+                int a = nums[i];
+                vector<pair<int, int>> p = p2(i + 1, n - 1, nums, -a);
+
+                int sz = p.size();
+
+                if (sz) {
+                    for (auto pp : p) {
+                        triplets.push_back({a, nums[pp.first], nums[pp.second]});
+                    }
                 }
             }
-            
-            while(a == nums[i] and i < n - 2) i++;
+
+            // while(a == nums[i] and i < n - 2) i++;
         }
 
         return triplets;
     }
 };
 
+// NOT while(l <= r) bcoz l != r
+// NOT p2(i+1,n) bcoz right limit should be n-1
+
+
+
 
 
 
