Leetcode Problem: Three sum
Tags: java, leetcode, programming
Published: 2020-05-28 01:42:38

---
title: Leetcode Problem: Three sum
published: true
description: Solution to the three sum problem
tags: java, leetcode, programming
series: programming-exercises
---

## Background
Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. You can find some of the other solutions in my profile page.

## Problem
[3 Sum Problem](https://leetcode.com/problems/3sum/solution/)
Given a list of numbers and a sum k, return all unique triplets <x, y, z> such that 
```java
x + y + z = k
```

### Note
This is a subset of the n-sum problem and a level higher in difficulty compared to often asked 2 sum problem. I have personally asked 2 sum problem multiple times in interview but have never gotten to solving the three sum problem. 

## Solution
### 2 Sum
From previous experience, I know that the fastest way to solve the 2 sum problem is by maintaining a hashmap.

The rough algorithm for a list of size `n` with a sum `k` is as follows:
* Iterate through the list.
* In each iteration check if the hashmap contains the key `k - currentElement`
    * if it does you have found a tuple
    * else place the currentElement in the hashmap. 

This solution yields a `O(n)` solution where n is the number fo elements in the list.

### 3 Sum as an extension to 2 sum
My first thought to solve this problem, was to think of extending the hashmap solution from 2sum. 

My first idea was to see if I could maybe use a nested hashmap. So, somehow in each step, I would check every other element. But then I realized I would have to check every other element twice, once for the top level set of keys and once for the second nested level. While I am not sure if this would work (I didn't try implementing this) it would at least involve a n^3 solution. 

An optimization which might be useful is to use the 2 sum problem. So the modified algorithm could be: 
* For every element in the list
* Get the value of `k - currentElement` 
* Call twoSum with the value from above step and the rest of the list. 

Given twoSum is `O(n)` and it is called `n` times, this solutions would be `O(n^2)` 
This is clearly better than my first approach so I decided to implement it. 

## Implementation
* I wrote a quick twoSum method and then added a third parameter to it `skippedIndex` so that I can skip the current element. There is probably a better way to pass around the rest of the list.
* My first run was successful, but then I hit a snag. I was getting duplicate triplets. 
* To get around this, I used a `Set` instead of an array (more on Java's Set [here](https://docs.oracle.com/javase/tutorial/collections/interfaces/set.html))
* There was still an issue. If my two sum code returned two set of triplets `1, 2, 3` and `3, 2, 1` the Set interface in java treated this as two different elements. To get around this problem, I simply sorted the triplet before inserting it into the set. This ensures uniqueness of the triplets. See sidebar below on how this works.
* You can find my full solution [here](https://github.com/deepakvenkat/LeetCodeExamples/blob/master/src/com/company/ThreeSum.java)

### Sidebar
Here is a quick example of Sets and how you can add sorted lists to a set to maintain uniqueness.

```java
jshell> Set<List<Integer>> s = new HashSet <List<Integer>>();
s ==> []

jshell> List<Integer> a = new ArrayList<Integer>(List.of(1, 2, 3))
a ==> [1, 2, 3]

jshell> List<Integer> b = new ArrayList<Integer>(List.of(3, 2, 1))
b ==> [3, 2, 1]

jshell> s.add(a)
$6 ==> true

jshell> s
s ==> [[1, 2, 3]]

jshell> s.add(b)
$8 ==> true

jshell> s
s ==> [[1, 2, 3], [3, 2, 1]]

jshell> Set<List<Integer>> s = new HashSet <List<Integer>>();
s ==> []

jshell> s.add(a)
$11 ==> true

jshell> Collections.sort(b)
jshell> s.add(b)
$13 ==> false

jshell> s
s ==> [[1, 2, 3]]
```