Solution by two pointer


  • 0
    U

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    Find all unique triplets of the given array which gives the sum of zero.
    Here unique means there are no two triplets $a_{1}, b_{1}, c_{1}$ and $a_{2}, b_{2}, c_{2}$ where:-
    $a_{1} == a_{2} && b_{1} == b_{2} && c_{1} == c_{2}$ satisfied.

    Algorithm

    First ignore the unique condition. To find all thriplets, what we need to do?

    • Use three nested loop for $a, b & c$, and generate all possible combination.

    C++

    class Solution {
    public:
      vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> t(3);
        vector< vector<int> > triplets;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
          for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
              if (nums[i] + nums[j] + nums[k] == c) {
                t[0] = nums[i];
                t[1] = nums[j];
                t[2] = nums[k];
                triplets.push_back(t);
              }
            }
          }
        }
        return ans;
      }
    };
    

    But here out solution is not unique. For same $a$ and $b$ only one real number is possible for $c$, that is $c = - (a + b)$.
    If more than one $c$ exists in the array, we take one to be unique of our solution.
    Now, our goal is to compute $a$ and $b$ uniquely. For all possible unique $a$, if we select all unique $b$, here $(b >= a)$ than all $a, b$ pair must be unique.

    C++

    class Solution {
    public:
      vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> t(3);
        vector< vector<int> > triplets;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        cout << n << endl;
        for (int i = 0; i < n; i++) {
          // a should be unique, so ignore
          // if we use same value before
          if (i > 0 && nums[i] == nums[i-1]) {
            continue;
          }
          for (int j = i + 1; j < n; j++) {
            // b also unique for every a, so ignore
            // if we use same value before for this ai
            if (j > i + 1 > 0 && nums[j] == nums[j-1]) {
              continue;
            }
            for (int k = j + 1; k < n; k++) {
              if (nums[i] + nums[j] + nums[k] == 0) {
                t[0] = nums[i];
                t[1] = nums[j];
                t[2] = nums[k];
                triplets.push_back(t);
                break;      // To be soluton unique break after find one c
              }
            }
          }
        }
        return triplets;
      }
    };
    

    Complexity Analysis

    • Time complexity : $O(n^3)$.

    Fist we sort the given array. Complexity for this $n log(n)$.
    After that use three nested loop to select $a, b$ and $c$.
    In worst case these three loop run $n, n - 1$ and $n - 2$ times.
    So total time complexity is:
    $$O(nlog(n)) + n * (n - 1) * (n - 2)$$
    $$ = O(nlog(n)) + n^3 - 3n^2 + 2n$$
    $$ = O(nlog(n)) + O(n^3)$$
    $$ = O(n^3)$$


    Approach #2 Use Binary Search [Accepted]

    Algorithm

    Here $a + b + c = 0$, hence $c = -(a + b)$.
    So in third loop we need to know if $-(a + b)$ is exist or not.
    We already sort the array, so we can use binary search.

    C++

    class Solution {
    public:
      vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> t(3);
        vector< vector<int> > triplets;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        cout << n << endl;
        for (int i = 0; i < n; i++) {
          if (i > 0 && nums[i] == nums[i-1]) {
            continue;
          }
          for (int j = i + 1; j < n; j++) {
            if (j > i + 1 > 0 && nums[j] == nums[j-1]) {
              continue;
            }
            int c = -(nums[i] + nums[j]);
            if (binary_search(nums.begin() + j + 1, nums.end(), c)) {
              t[0] = nums[i];
              t[1] = nums[j];
              t[2] = c;
              triplets.push_back(t);
            }
          }
        }
        return triplets;
      }
    };
    

    Complexity Analysis

    • Time complexity : We use binary search instead of third loop. So time complexity is: $O(n^2log(n))$

    Approach #3 Us two pointer [Accepted]

    Algorithm

    Here $a + b + c = 0$, hence $b + c = -a$.
    So for all $a$ we need to find number of unique pair which sum gives $-a$.
    We can do it linear time using two pointer.

    C++

    class Solution {
    public:
      vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> t(3);
        vector< vector<int> > triplets;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n; i++) {
          if (i > 0 && nums[i] == nums[i-1]) {
            continue;
          }
          int b = i + 1, c = n - 1, a = -nums[i];
          while (b < c) {
            while (b < c && nums[b] + nums[c] > a) {
                c--;
            }
            while (b < c && nums[b] + nums[c] < a) {
                b++;
            }
            if (b < c && nums[b] + nums[c] == a) {
              t[0] = nums[i];
              t[1] = nums[b];
              t[2] = nums[c];
              triplets.push_back(t);
              b++;
            }
            while (b < c && nums[b] == nums[b - 1]) {
                  b++;
            }
          }
        }
        return triplets;
      }
    };
    

    Complexity Analysis

    • Time complexity : We use We iterate full array for first number. For rest two number we iterate rest of the array. So time complexity is: $O(n^2)$

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.