3Sum — Leetcode

Topic: Array
Difficulty: Medium
Question Number: 15

To understand this question better, first solve 2sum problem of leetcode

2sum- leetcode

Problem statement:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Explanation:

Approach

• Sort the input array.
• Iterate over the input array to fix the value in tempsum.
• Take two pointers, one(start) at i + 1 and the other(end) at n — 1.
• If the sum is smaller than tempsum, shift the start pointer to the right.
• Else, If the sum is bigger, shift the end pointer to the left.
• Else, if the sum of elements at i, start, end are equal to zero then store it in res.
• To eliminate the redundancy shift the start and end pointer unless you get a value not equal to the previous value.
• Return the res as the answer.

Code:

class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res= new ArrayList<>();
    if(nums == null || nums.length == 0) return res;

    Arrays.sort(nums);

    if(nums[0] >0) return res;
    
    int N = nums.length;

    for(int i=0; i< N; i++) {
      int start=i+1;
      int end=N-1;
      
      if(i>0 && nums[i]==nums[i-1]) continue;

      while(start<end) {
        //handle duplicate
        int tempSum =  nums[i] + nums[start] + nums[end];
        if(tempSum == 0) {
          res.add(Arrays.asList(new Integer[]{nums[i], nums[start], nums[end]}));
          start++;
          end--;
          while(start< end && nums[start] == nums[start-1]) start++;
          while(start< end && nums[end] == nums[end+1]) end--;
        } else if (tempSum > 0) end--;
        else start++;
      }
    }
      //handle duplicate
    return res;
  }
}

Thank You

Oshi Raghav