### 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

## Comments

## Post a Comment