# Three Sum - Leet Code Solution

September 13, 2019

## Problem Statement

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

``````Example:
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]``````

## Solution-1

A simple brute force is the start. But, it is so simple. Lets not discuss it. You just need to make sure that result must have unique entries

## Solution-2

Like, in two-sum problem. We used a HashSet. We can use it here as well. Again, to maintain unique elements, it added complexity.

``````public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet();
int l = nums.length;
for (int i=0; i<l; i++) {
Set<Integer> vals = new HashSet();
for (int j=i+1; j<l; j++) {
if (j == i) continue;

int requiredNum = 0 - (nums[i] + nums[j]);
if (vals.contains(requiredNum)) {
List<Integer> iRes = new ArrayList();

Collections.sort(iRes);
}

if (!vals.contains(nums[j])) {
}
}
}

List<List<Integer>> r = new ArrayList(result);
return r;
}``````

## Solution-3

Lets look at most optimized one.

• Sort the array
• Now, in a loop, start from left and right pointer.
• Keep track of sum. If we found the sum, add it. And, we need to move left and right pointer. One case is where even after moving left and right pointer, the value can be duplicate. Since, we need to avoid duplicates. We need to add a condition here to keep moving untill found a unique element.
• There is a corner case, where handling of duplicate elements has to be handled in outer loop as well. (See line ahead of for loop)
``````public List<List<Integer>> threeSum_2(int[] nums) {
Arrays.sort(nums);
int len = nums.length;

List<List<Integer>> res = new ArrayList<>();
for (int i=0; i<len; i++) {
//to avoid processing duplicate values
if (i > 0 && nums[i-1] == nums[i]) continue;

int l = i+1;
int r = len-1;

while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
List<Integer> ir = new ArrayList<>();

l++;
r--;

//to move over duplicate values
while (l < r && nums[l-1] == nums[l]) l++;
while (l < r && nums[r+1] == nums[r]) r--;
}

else if (s < 0) {
l++;
}
else {
r--;
}
}
}
return res;
}``````

## Similar Posts

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

### Swap Nodes Pairs in Link List - Leet Code Solution

Problem Statement Given a linked list, swap every two adjacent nodes and return…

### Graph Topological Sorting - Build System Order Example

Graph Topological Sorting This is a well known problem in graph world…

### Insertion Sort Algorithm

Its a kind of incremental insertion technique, where the algorithm build up…

System design interview is pretty common these days, specially if you are having…

### Check whether an integer number given is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

## Latest Posts

### Authenticating Strapi backend with Next.js and next-auth using credentials and jwt

Introduction Strapi is a backend system provides basic crud operations with…

### How to create Repository using Github Rest API, Configure Visibility and Assign a Team as Readonly

Introduction I had to create many repositories in an Github organization. I…