3Sum


  • 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 target value.
    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. 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, 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>> fourSum(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, 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 do not use any extra space.

    Approach #2 Two Pointers [Accepted]

    Algorithm

    Lets simplify the problem into 2Sum problem. Now we need two 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.

    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.
    
        * Time complexity : $$O(n^2)$$.
    
        Because each outer loop runs `n` times and two pointers runs `n` times as well, 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 do 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.