programming-exercises (5 Part Series)

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

Given a list of numbers and a sum k, return all unique triplets such that

```
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) - 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

### Sidebar

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

```
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]]
```

Posted on May 28 by:

## Discussion

Nice Explanation !