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
skippedIndexso 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
Setinstead 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, 3and3, 2, 1the 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]]
Top comments (1)
Nice Explanation !