0

3Sum

Problem:

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

eg.  Given array  S ={-1,0,1,2,-2,-1,-4}

Then solution set is: (-1,0,1), (-2,0,2),(-1,-1,2)

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (i.e, abc)
  • The solution set must not contain duplicate triplets.

Logic:

To satisfy both constraints i.e. elements in triplet must be in non-descending order and no duplicate triplets, we will sort elements in array first.

We will keep first pointer at start of array, second pointer next to first pointer and third pointer at the end of array.  For each first pointer we will find a pair with it ,which in turn form a triplet whose sum is 0.

If sum is greater than 0 then we will decrease last pointer position and if sum is less than 0 then we will increment second pointer.

We need to make sure pairs are not repeated that means if numbers are repeated in array, we should skip them by increment and decrement of pointer appropriately.

Implementation:

Complexity:  O(n2)