Leetcode – 15 – 3Sum

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.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a  b  c)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

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

Description:

In this problem we have to find all the number combinations in the array which will add upto 0. We have to consider that the output should be sorted.

Solution (three pointers)

The approach that we are talking about is to sort the array first and then have one pointer running along the length of the array. We will have another two pointer to point to the start and end of the array elements

We will check for the sum and if the sum is 0 then we we will add it to the list and move forward with increment  the second and decrement third pointer

We will ignore any duplicates along the way.

1

Code:

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for(int i = 0; i < nums.length-2; i++) {
        if(i > 0 && (nums[i] == nums[i-1])) continue; // avoid duplicates
        for(int j = i+1, k = nums.length-1; j<k;) {
            if(nums[i] + nums[j] + nums[k] == 0) {
                list.add(Arrays.asList(nums[i],nums[j],nums[k]));
                j++;k--;
                while((j < k) && (nums[j] == nums[j-1]))j++;// avoid duplicates
                while((j < k) && (nums[k] == nums[k+1]))k--;// avoid duplicates
            }else if(nums[i] + nums[j] + nums[k] > 0) k--;
            else j++;
        }
    }
    return list;
}
}

Time Complexity: O(n2)

  • Go through the length of array elements and check for elements adjacent to the current element – O(n2)

Space Complexity: O(1)

  • We will adding 3 elements to the list and can have n number of combinations  – O(n)

Available Test Cases: 311

  • Check for empty array
  • Check for duplicates

Github:

Leetcode_15_3_sum

1 comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: