3 SUM

Companies:
  • Adobe Interview Questions
  • Amazon Interview Questions
  • Apple Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions
  • Oracle Interview Questions
  • Uber Interview Questions

Problems statement

Given an array nums of n integers, are there elements abc in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Sample Test Cases

Given array nums = [-1, 0, 1, 2, 2, -4],

A solution set is:
[
  [-4, 2, 2],
  [-1, 0, 1]
]

Problem Solution

We Solve this question by fixing the first element and then finding the other two using two pointer algorithm.

So first we sort the array in ascending order and Traverse it from start to end.

For every Index i, we create two variables l=i+1 and h= arr_size-1 . Then we run the loop until l is less than h , if sum of nums[l] and nums[h] is equal to zero then store the triplet.

If the sum is less than zero then we increment value of l, since array is sorted increasing value of l leads to increase in sum as nums[l+1]>nums[l].

If sum is greater than zero then we decrement the value of h, by decreasing value of h the overall sum value decreases as nums[h-1]<nums[h].

Complexity Analysis

  • Time Complexity: O(n^2).only two nested loops are required, so the time complexity is O(n2).
  • Space Complexity: O(1), no extra space is required, so the time complexity is constant.

Code Implementation

// C++ program to find a triplet
#include <bits/stdc++.h>
using namespace std;

void threeSum(vector<int>nums,int sum)
{   int arr_size= nums.size();
    int l, r;
    vector< vector<int> > result;
    /* Sort the elements */
    sort(nums.begin(), nums.end());

    /* Now fix the first element one by one and find the
       other two elements */
         vector<int> temp;
    for (int i = 0; i < arr_size - 2; i++) {

        // To find the other two elements, start two index
        // variables from two corners of the array
        l = i + 1;
      temp.clear();
        r = arr_size - 1; // index of the last element
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] == sum) {

                 temp.push_back(nums[i]);
                 temp.push_back(nums[l]);
                 temp.push_back(nums[r]);
                 l++;
                 r--;
                 result.push_back(temp);
                 temp.clear();

            }
            else if (nums[i] + nums[l] + nums[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }

    }

  for(int i=0;i<result.size();i++)
  {
      for(int j=0;j<3;j++)
      {
          cout<<result[i][j]<<" ";

      }
      cout<<endl;
  }

}

/* Driver program to test above function */
int main()
{
    vector<int> nums ;
    nums.push_back(-1);
    nums.push_back(0);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    nums.push_back(-4);
    int sum = 0;


    threeSum(nums,sum);

    return 0;
}

 

Scroll to Top