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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala