Posts 3 sum
Post
Cancel

3 sum

This question is part of NeetCode150 series.

Problem Description

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.

Solution set must not contain duplicate triplets.
leetcode

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
For the main function:

    Sort the input array nums.
    Iterate through the array:
        If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
        If the current value is the same as the one before, skip it.
        Otherwise, call twoSumII for the current position i.

For twoSumII function:

    Set the low pointer lo to i + 1, and high pointer hi to the last index.
    While low pointer is smaller than high:
        If sum of nums[i] + nums[lo] + nums[hi] is less than zero, increment lo.
        If sum is greater than zero, decrement hi.
        Otherwise, we found a triplet:
            Add it to the result res.
            Decrement hi and increment lo.
            Increment lo while the next value is the same as before to avoid duplicates in the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
        
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        
        //Sort the array in ascending order
        Arrays.sort(nums);
        
        //Loop through the elements one by one
        for(int i=0; i<nums.length; i++){

            //Fix the first element
            int current = nums[i];

            //If the current element is more than 0, triplet will 0 sum is NOT possible (since our array is sorted)
            if(current > 0) break;
            
            //If the current element is same as the previous one, skip it since we don't want duplicates
            if(i!=0){
                if(nums[i] == nums[i-1]) continue;
            }
            
            //Let's look for the other two elements such that the total sum of three elements in 0
            //We will do this using two pointer approach
            int l=i+1, r=nums.length-1;
            
            while(l<r){

                //If their sum is less than 0, we need a higher value, so we increment L
                if(nums[i] + nums[l] + nums[r] < 0){
                    l++;
                //If their sum is more than 0, we need a lower value, so we decrement R
                }else if(nums[i] + nums[l] + nums[r] > 0){
                    r--;
                //We have found our triplet
                }else{
                    List<Integer> tempList = new ArrayList<Integer>();
                    
                    tempList.add(nums[i]);
                    tempList.add(nums[l]);
                    tempList.add(nums[r]);
                    
                    //Save the current triplet
                    ans.add(tempList);
                    
                    //Move to the next elements
                    l++; r--;
                    
                    //This part is important to avoid duplicates. If we land into the same element, move forward
                    while(nums[l] == nums[l-1] && l<r) l++;
                    
                }
            }
            
            
        }
        
        return ans;
        
    }
    
}
This post is licensed under CC BY 4.0 by the author.