Leetcode Problem: Three sum

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

Comments

[Pushpak Chhajed]

Nice Explanation !