3Sum Problem Solution - The Coding Shala

Home >> Interview Prep >> 3Sum Problem

 In this post, we will learn how to solve the 3Sum Problem and will implement its solution in Java.

3Sum Problem

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.

The solution set must not contain duplicates.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []

Output: []

3Sum Java Solution

Approach 1

We can solve this problem using brute force but time complexity will go O(n^3) in that case. The brute force solution can be improved using Two pointer technique and the time complexity will be O(n^2). The steps are below for that:

Step 1. First, sort the array so we can use two pointer technique to figure out which side we need to move our pointer.

Step 2. Now we can solve this like 2 Sum problem.

To remove the duplicate pairs we need to check if two continuous elements are the same or not.

Java Program: 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                // array is sorted
                // now there is no way that sum will be zero
                break;
            }
            
            int sum = 0 - nums[i];
            int start = i + 1;
            int end = nums.length - 1;
            
            // ignore if first number is duplicate
            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
                // now its 2 sum problem from here
                while (start < end) {
                    if (nums[start] + nums[end] == sum) {
                        // add this pair in result
                        result.add(Arrays.asList(nums[i], nums[start], nums[end]));
                        
                        // skip the same 2nd and 3rd numbers
                        while (start < end  && nums[start] == nums[start+1]) start++;
                        while (start < end && nums[end] == nums[end-1]) end--;
                        
                        start++;
                        end--;
                    }
                    else if (nums[start] + nums[end] < sum) start++;
                    else end--;
                }
            }
        }
        
        return result;
    }
}

Other Posts You May Like

• Triplets with Sum between Given Range
• Two Sum Sorted Array
• Two Sum Problem
• Repeat and Missing Number Array
• Max Sum Contiguous SubArray

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.