3Sum Cont…

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

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

You may view the full question here.

Approach 2: After ̶a̶ ̶f̶e̶w̶ many many futile attempts, I finally decided to do it — I mean this!

And bumped into this brilliant post. The two pointer approach was a game changer, indeed. Clearly, it requires us to look at the problem in greater detail and acutely analyze the most basic aspects. These probably seem very basic but can have a significant impact on the performance.

Simple things such as —

• Sorting the array
• Making sure that the first and second value are always unique (automatically ensures that the third, and hence the whole combination will be unique too)

Now let’s quickly look at the code (It’s an exact replication of the code in the post in java) —

//Approach 2
//Runtime: 33ms!!!
//Memory usage: 48.6MB
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> output = new ArrayList();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; ++i) {
    // Never let i refer to the same value twice to avoid duplicates.
    if (i != 0 && nums[i] == nums[i - 1]) continue;
    int j = i + 1;
    int k = nums.length - 1;
    while (j < k) {
      if (nums[i] + nums[j] + nums[k] == 0) {
          List<Integer> list = new ArrayList();
          list.add(nums[i]);
          list.add(nums[j]);
          list.add(nums[k]);
          output.add(list);
        ++j;
        // Never let j refer to the same value twice (in an output) to avoid duplicates
        while (j < k && nums[j] == nums[j-1]) ++j;
      } else if (nums[i] + nums[j] + nums[k] < 0) {
        ++j;
      } else {
        --k;
      }
    }
  }
  return output;
    }
}

Approach 3: A small little tweak — If the sum needs to be 0, unless all the values are 0, there should be at least one negative number. Since the outermost loop is to determine the first element, we restrict the for loop for negative numbers and numbers equal to 0. This can eliminate a bunch of redundant iterations.

//Approach 3
//Runtime: 28ms
//Memory usage: 47.8MB
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> output = new ArrayList();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && nums[i]<=0; ++i) {
    // Never let i refer to the same value twice to avoid duplicates.
    if (i != 0 && nums[i] == nums[i - 1]) continue;
    int j = i + 1;
    int k = nums.length - 1;
    while (j < k) {
      if (nums[i] + nums[j] + nums[k] == 0) {
          List<Integer> list = new ArrayList();
          list.add(nums[i]);
          list.add(nums[j]);
          list.add(nums[k]);
          output.add(list);
        ++j;
        // Never let j refer to the same value twice (in an output) to avoid duplicates
        while (j < k && nums[j] == nums[j-1]) ++j;
      } else if (nums[i] + nums[j] + nums[k] < 0) {
        ++j;
      } else {
        --k;
      }
    }
  }
  return output;
    }
}

Find more posts here.

Cheers & Chao!