# 3 Sum - Leetcode #15 Short & Simple Solution

Updated: 4 days ago

## Problem Statement

This is another article in the series leetcode problem solutions and this article is a solution to leetcode 15 three sum problem.

We solved the two sum problem in our earlier article, and this problem in some ways is a continuation of the two sum problem. So, if you have not yet solved the two sum problem we advice you to do so because it will help you understand the 3 sum problem better.

Given an array of integers, nums, return all the triplets in the given array nums[i], nums[j], nums[k] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

**Notice:** The solution set must not contain duplicate triplets.

## Example

**Example 1:**

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

**Example 2:**

**Input****:** nums = [0]
**Output****:** []

## Solution

Let us try to understand the problem statement. The first part of the problem statement is clear, we are asked to find out all the triplets in the given array whose sum is equal to zero. A triplet is nothing but a set of three numbers in the given array. For example, if nums=[1,2, 3,4] is the given array, [1,2,3] [2,3,4] [1,3,4] etc are its triplets.

What does the condition i != j, i != k, and j != k mean?

It means that we are not allowed to reuse any number from the array within a triplet. Example, for the given array nums = [1,2,3,4], triplets [1,1,1] or [1,1,2] or [1,2,2] etc are not considered valid triplets.

The last condition that we need to consider is that we cannot have duplicate triplets in our final result. Example if [-2,-2,0,2] is the given array, we can only consider one of [-2,0,2] from indexes 0, 2, 3 and [-2,0,2] from indexes 1, 2, 3 in our final result.

### Solution 1: Brute Force

The most simple and straight forward solution to this problem is to find every possible triplet from the given array, see if its sum is equal to zero and return the result (ensuring there are no duplicate triplets in the result).

This algorithm involves the following steps:

Use three loops to generate all possible triplets for the given array, with each loop variable keeping track of 1 triplet element each.

Next we calculate the sum for each triplet generated in step 1.

If the sum is equal to 0 we need to check if it is a unique triplet (not already in our result set). We can ensure the triplets in our result set are unique by sorting the triplets and adding it to a hashmap (hashmap overwrites data if same value is written to the same key multiple times thereby eliminating duplicates).

Once we have added all the triplets whose sum is equal to 0 into the hashmap, we iterate through the hashmap and add it to our result array.

Finally we return the result array.

#### Implementation

Below is the implementation for this solution:

##### Language: Go

##### Language: Java

#### Complexity Analysis

##### Time Complexity: O(n^3)

Time complexity is O(n^3) since the algorithm uses 3 loops to arrive at the result.

##### Space Complexity: O(k)

Space complexity is O(k) since we use hashmap to store unique triplets. k here is the number of unique triplets with sum = 0 for the given array.

**Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:**

### Solution 2: Efficient Solution

We can sort the given array and use the three pointer approach to improve the time complexity of our solution as compared to the previous approach.

The idea is to sort the array first, then run two loops to process the triplets. We fix the outer loop and move the two pointers (indexes) of the inner loop inwards to arrive at the result.

The intuition behind this algorithm is simple, when we sort the array all the duplicate elements are grouped together. And if we use two pointers from left and right to traverse the array while processing the triplets, we can easily avoid duplicate triplets that would occur because of these duplicate elements.

For example is nums = [-2, 1, -3, 5, -3, 5] is the given array, when we sort this array we get: nums = [-3, -3, -2, 1, 5, 5]. As you can see all the duplicate elements [-3, -3] and [5,5] are grouped together. If were to consider all of these duplicate elements, it would result duplicate triplets like [-3, -2, 5] and [-3, -2, 5]. We can easily avoid this if we use two pointers to traverse the array from either sides (one from start and one from end). We process only the 1st element and skip all the duplicate elements that appear after it.

For the given input array **nums** of size n this approach does the following steps:

First step is to sort the given array nums. Sorting the array helps us identify duplicate triplets using our loops by skipping certain numbers that would result in duplicate triplets. This helps us avoid using a hashmap to identify the duplicates (like in solution 1) there by improving the space complexity(Keep reading to know how duplicate triplets can be skipped). Also sorting the array helps efficiently increment/decrement our index variables depending on whether the sum is less than or greater than 0.

Next we need two loops. Outer loop index

**num1Idx**represents the index of the first element in the triplet. Inner loop contains two indexes**num2Idx**and**num3Idx**representing the indexes of the 2nd and 3rd triplet elements respectively.Initially

**num1Idx**points to the first element in the given array and**num2Idx**,**num3Idx**point to the 2nd and last elements in the given array. We fix the outer loop index**num1Idx**and move the two inner loop indexes inwards as long as**num3Idx**>**num2Idx**. Once the condition**num3Idx**>**num2Idx**is false we stop the inner loop and increment the outer loop index**num1Idx**, also update**num2Idx**and**num3Idx**,**num2Idx**=**num1Idx**+1 and**num3Idx**=n-1.Take a variable

**sum**to store the triplet sum.**sum**=**nums**[**num1Idx**] +**nums**[**num2Idx**] +**nums**[**num3Idx**]. Now there are three possibilities:**a.**If**sum**is equal to 0 we add it to our result.**b.**If**sum**is greater than 0 we need to decrease the sum value to make it equal to 0, so we decrement**num3Idx**index.**c.**If**sum**is less than 0 we need to increase sum value to make it equal to 0, so we increment**num2Idx**index.The inner loop should run as long as

**num3Idx >****num2Idx**for each iteration of the outer loop**.**We return the result once all the triplet combinations are processed.The above 4 steps ensure that we find all triplets whose sum is equal to 0. But it will also add duplicates to the result array. To skip duplicate triplets we need to add two conditions to our algorithm, one in the outer loop and one in the inner loop. In the outer loop

*if nums[num1Idx] == nums[num1Idx-1]*i.e. if current**num1Idx**value is same as previous number (**num1Idx**-1) we skip the current number (we don't have to consider the current number for calculating our result). This condition ensures that we skip all duplicates from the left side of the array. Similarly to skip all numbers from the right side of the array, once we find a triplet with sum equal to zero we keep decrementing**num3Idx**until nums[**num3Idx**] != nums[**num3Idx**+1] (in the inner loop).

#### Simulation

To make this more clear let us understand this algorithm with a simulation.

Consider you are given the below input array **nums** of size n = 5:

The first step is to sort the given array. After sorting **nums** will be:

##### Iteration 1

For the 1st iteration of the outer loop **num1Idx **= 0, **num2Idx **= **num1Idx **+ 1 = 1 and **num3Idx **= n-1 = 4. Same is show in figure below:

Now we calculate the sum for array elements at current **num1Idx**, **num2Idx **and **num3Idx**.

**sum** = **nums** [**num1Idx**] + **nums** [**num2Idx**] + **nums** [**num3Idx**]

**sum** = **nums**[0] + **nums**[1] + **nums**[4] = (-1) + (-1) + 2 = 0

As you can see for the current values of **num1Idx**, **num2Idx **and **num3Idx** sum = 0, so we add it to our **result**. So **result **= [[-1, -1, 2]] and also decrement **num3Idx**. There is no need to make the duplicate check in the inner loop as **num3Idx** is the last element in the array.

Now the updated values of index variables are **num1Idx **= 0, **num2Idx **= 1 and **num3Idx **= 3.

Again calculate sum,

**sum** = **nums**[0] + **nums**[1] + **nums**[3] = (-1) + (-1) + 1 = -1.

Sum is less than 0, so we increment **num2Idx**.

Now **sum** = **nums**[0] + **nums**[2] + **nums**[3] = (-1) + 0 + 1 = 0. Sum is equal to 0, so we add the current triplet [-1, 0, 1] to the result and decrement **num3Idx**. Also make the duplicate check in the inner loop, **nums**[**num3Idx** ] != **nums**[**num3Idx**+1], so there is no possibility of a duplicate for the current value of **num3Idx**, therefore no need to decrement **num3Idx **further.

The updated values of index variables are **num1Idx **= 0, **num2Idx **= 2 and **num3Idx **= 2. As you can see **num2Idx** is equal to **num3Idx**, so we stop our inner loop and increment the outer loop index **num1Idx **by 1.