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

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