Solution by ananai


  • 0

    Approach #1 Brute Force With Extra Space [Time Limit Exceeded]

    Algorithm

    Each time get three numbers from an array and check if their sum is equal to 0.

    The problem requires to find all unique triplets; therefore, all duplicates
    should be eliminated.

    Naive approach to eliminate all duplicates can be storing all triplets in a set.
    We also need to consider cases when numbers in triplets are in different positions; consequently,
    these numbers will not be considered as duplicates.

    Input:
    [-5,5,4,-3,0,0,4,-2]
    4
    
    Output:
    [[-5,5,0,4],[-5,5,4,0],[5,-3,4,-2],[5,4,-3,-2]]
    
    Expected:
    [[-5,0,4,5],[-3,-2,4,5]]
    

    Therefore, first we need to sort the array.

    sort(nums.begin(), nums.end())

    As a result,

    Input:
    [-5,5,4,-3,0,0,4,-2]
    4
    
    Output:
    [[-5,0,4,5],[-3,-2,4,5]]
    
    Expected:
    [[-5,0,4,5],[-3,-2,4,5]]
    

    C++

    vector<vector<int>> threeSum(vector<int>& nums) {
    
            set<vector<int>> tripletSet;
    
            sort(nums.begin(), nums.end());
    
            for(int i = 0; i<nums.size(); i++) {
                for(int j = i+1; j<nums.size(); j++) {
                    for(int k = j+1; k<nums.size(); k++) {
                        if(nums[i] + nums[j] + nums[k] == 0) {
                            tripletSet.insert({nums[i], nums[j], nums[k]});
                        }
                    }
                }
            }
    
            vector<vector<int>> triplets(tripletSet.begin(), tripletSet.end());
    
            return triplets;
    }
    

    Complexity Analysis

    • Time complexity : $$O(n^3)$$. Because each of these nested loops executes n times and nlogn to sort the array, the total time complexity is $$O(n^3)$$, where n is a size of an array.

    • Space complexity : $$O(n^2)$$. If we assume that resultant array is not considered as additional space we need $$O(n^2)$$ space for storing triplets in a set.


    Approach #2 Brute Force With Constant Space [Time Limit Exceeded]

    Algorithm

    Instead of storing triplets in a set eliminate all duplicates in place.
    Each time before choosing a number check it with previous neighbor.

    C++

    vector<vector<int>> threeSum(vector<int>& nums, int target) {
    
          vector<vector<int>> triplets;
    
          sort(nums.begin(), nums.end());
    
          for(int i = 0; i<nums.size(); i++) {
              if(i == 0 || nums[i] != nums[i-1]) {
                  for(int j = i+1; j<nums.size(); j++) {
                      if(j == i+1 || nums[j] != nums[j-1]) {
                          for(int k = j+1; k<nums.size(); k++) {
                              if(k == j+1 || nums[k] != nums[k-1]) {
                                  if(nums[i] + nums[j] + nums[k] == 0) {
                                      triplets.push_back({nums[i], nums[j], nums[k]});
                                  }
                              }
                          }
                      }
                  }
              }
          }
    
          return triplets;
    }
    

    Complexity Analysis

    • Time complexity : $$O(n^3)$$. Because each of these nested loops executes n times and nlogn to sort the array, the total time complexity is $$O(n^3)$$, where n is a size of an array.

    • Space complexity : $$O(1)$$. If we assume that resultant array is not considered as additional space we did not use any extra space.


    Approach #3 Two Pointers [Accepted]

    Algorithm

    Lets simplify the problem into 2Sum problem. Now we need to find two numbers from an array such that their sum is equal to given target value. Assuming that the array is sorted the approach to solve the problem in this case would be to run two pointers from the start and the end of the array.

    Each time check the sum of two numbers at pointers with target value. If the sum is equal to target value it means that numbers are found otherwise increment start or decrement end.

    while(start<end) {
        if(nums[start] + nums[end] = target) {
            //Numbers are found
        } else if(nums[start] + nums[end] < target) {
            start++;
        } else {
            end--;
        }
    }
    

    In this approach we are traversing the array once therefore time complexity is $$O(n)$$ where n is a size of the array.

    Lets apply this logic to the initial problem by replacing two inner loops with two pointers.

    C++

    vector<vector<int>> threeSum(vector<int>& nums) {
    
            vector<vector<int>> triplets;
    
            sort(nums.begin(), nums.end());
    
            for(int i = 0; i<nums.size(); i++) {
                if(i == 0 || nums[i] != nums[i-1]) {
                    int l = i+1, r = (int)nums.size()-1;
                        while(l<r) {
                            if(nums[i] + nums[l] + nums[r] == 0) {
    
                                triplets.push_back({nums[i], nums[l], nums[r]});
    
                                while(l<r && nums[l] == nums[l+1]) {
                                    l++;
                                }
    
                                while(l<r && nums[r] == nums[r-1]) {
                                    r--;
                                }
    
                                l++;
                                r--;
    
                            } else if(nums[i] + nums[l] + nums[r] < 0) {
                                l++;
                            } else {
                                r--;
                            }
                        }
                }
            }
    
            return triplets;
    }
    

    Run first loop for our initial number in a triplet and for remaining two numbers run inner loop with two pointers which reduce our time complexity by n.

    In order to eliminate duplicates in resulting array of triplets check current number with previous number if they are the same keep moving pointers.

    Complexity Analysis

    • Time complexity : $$O(n^2)$$. Because each outer loop runs n times and two pointers runs n times as well and nlogn to sort the array, the total time complexity is $$O(n^2)$$, where n is a size of an array.

    • Space complexity : $$O(1)$$. If we assume that resultant array is not considered as additional space we did not use any extra space.


Log in to reply
 

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