Leetcode 15. 3 Sum

Question

Problem statement

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4], a solution set is:

[
 [-1, 0, 1],
 [-1, -1, 2]
]

I did review Leetcode 3 sum algorithm a few hours, and put together the following C# code. The time complexity is optimal, \$O(n*n)\$ where \$n\$ is the length of the array, pass Leetcode online judge. Also, I did a few improvements, make it more flat (using two continue statements, instead of if/else statements), test cases are added, two sum algorithm uses two pointer technique to go through the array once.

Please share your ideas to improve C# code.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode_15_3Sum
{
/*
* 
* Work on this 3 sum algorithm
* 
* Leetcode 15: 3 sum
* https://leetcode.com/problems/3sum/
* 
* Given an array S of n integers, are there elements a, b, c in S 
* such that a + b + c = 0? Find all unique triplets in the array 
* which gives the sum of zero.
* 
 Note:
 Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
 The solution set must not contain duplicate triplets. 
* 
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
* 
*/
class Program
{
 static void Main(string[] args)
 {
 // test 3 sum 
 // 2 lists, one is -1, 0, 1, second one is -1, -1, 2
 int[] array = new int[6] { -1, 0, 1, 2, -1, -4 };
 IList<IList<int>> triplets = ThreeSum(array);
 Debug.Assert(triplets.Count == 2); 
 Debug.Assert(String.Join(",", triplets[0].ToArray()).CompareTo("-1,-1,2") == 0);
 Debug.Assert(String.Join(",", triplets[1].ToArray()).CompareTo("-1,0,1") == 0);
 }
 /*
 * @nums - the array containing the numbers
 * 
 * 3 sum can be solved using 2 sum algorithm, 
 * 2 sum algorithm - optimal solution is using two pointers, time complexity is O(nlogn), 
 * sorting takes O(nlogn), and two pointer algorithm is O(n), so overall is O(nlogn).
 * Time complexity for 3 sum algorithm: 
 * O(n*n)
 */
 public static IList<IList<int>> ThreeSum(int[] nums)
 { 
 IList<IList<int>> results = new List<IList<int>>();
 HashSet<string> keys = new HashSet<string>(); 
 if (nums == null || nums.Length == 0)
 return results;
 Array.Sort(nums);
 int length = nums.Length;
 int target = 0;
 for (int i = 0; i < length - 2; i++) 
 {
 int firstNo = nums[i];
 // using two pointers to go through once the array, find two sum value 
 int newTarget = target - firstNo;
 int start = i + 1;
 int end = length - 1;
 while (start < end)
 { 
 int twoSum = nums[start] + nums[end];
 if (twoSum < newTarget)
 {
 start++;
 continue;
 }
 if (twoSum > newTarget)
 {
 end--;
 continue; 
 } 
 int[] threeNumbers = new int[] { firstNo, nums[start], nums[end] };
 string key = PrepareKey(threeNumbers, 3);
 if (!keys.Contains(key))
 {
 keys.Add(key); 
 results.Add(threeNumbers.ToList());
 }
 // continue to search 
 start++;
 end--; 
 }
 }
 return results;
 }
 /* 
 * -1, 0, 1 -> key string" "-1,0,1,"
 */
 private static string PrepareKey(int[] arr, int length)
 {
 string key = string.Empty;
 for (int j = 0; j < length; j++)
 {
 key += arr[j].ToString();
 key += ",";
 }
 return key;
 }
 }
}

• Denis: Are [-1, 0, 1], and [1, 0, -1], considered duplicates ?
• Jianmin Chen: @denis, \$[-1, 0, 1]\$ and \$[1, 0, -1]\$ are considered duplicates.
• Muhammad Zohaib Ehsan: I am new here. Can i suggest a solution. The solution is separate out the negative number. Than loop through negative numbers array and with the rest of the numbers by making set of 3. When sum is zero add it to a collection of triplets. do reverse for the remaining numbers ( 2 negative numbers can cause a triplet). what i think the complexity is n + n/2*n/2+n/2*n/2. which is equal to (correct me) n+n/2+n/2.

Answer 1

if (nums == null || nums.Length == 0)
 return results;

should be

if (nums == null || nums.Length < 3)
 return results;

another

List<int> threeNumbers = new List<int> { firstNo, nums[start], nums[end] };
string key = PrepareKey(string.Join(",", threeNumbers);
if (!keys.Contains(key))
{
 keys.Add(key); 
 results.Add(threeNumbers);
}

I don't like continue over if / else

This should faster as it skips values already evaluated
Since it skips values evaluated then do not need to check for duplicate

public static IList<IList<int>> ThreeSumB(int[] nums)
{
 IList<IList<int>> results = new List<IList<int>>(); 
 if (nums == null)
 return results;
 int length = nums.Length;
 if (length < 3)
 return results;
 Array.Sort(nums);
 Debug.WriteLine(string.Join(", ", nums)); 
 int target = 0;
 int firstNo;
 int newTarget;
 int start;
 int end;
 for (int i = 0; i < length - 2; i++)
 {
 firstNo = nums[i];
 if (i > 0 && firstNo == nums[i-1])
 continue;
 // using two pointers to go through once the array, find two sum value 
 newTarget = target - firstNo;
 start = i + 1;
 end = length - 1;
 while (start < end)
 {
 int twoSum = nums[start] + nums[end];
 if (twoSum < newTarget)
 {
 //Debug.WriteLine(nums[start] + " " + nums[start + 1]);
 start++;
 while (start < end && nums[start - 1] == nums[start])
 start++;
 //Debug.WriteLine(nums[start]);
 }
 else if (twoSum > newTarget)
 {
 //Debug.WriteLine(nums[end] + " " + nums[end - 1]);
 end--;
 while (start < end && nums[end + 1] == nums[end])
 end--;
 //Debug.WriteLine(nums[end]);
 }
 else
 {
 results.Add(new List<int> { firstNo, nums[start], nums[end] });
 //Debug.WriteLine(nums[start] + " " + nums[start + 1]);
 start++;
 while (start < end && nums[start - 1] == nums[start])
 start++;
 //Debug.WriteLine(nums[start]);
 //Debug.WriteLine(nums[end] + " " + nums[end - 1]);
 end--;
 while (start < end && nums[end + 1] == nums[end])
 end--;
 // Debug.WriteLine(nums[end]);
 }
 }
 }
 return results;
}

I am getting like 8x faster than OP solution using

int[] array = new int[] { -1, 0, 1, 2, -1, -4, -1, -4, 1, 2, 2 };

Even faster. Bring the last until you are at target or less.
No purpose to starting at the end with the last as if one of the first two is increased then last has to decrease

• t3chb0t: or even shorter with C# 6 if(nums?.Length < 3) {..}
• t3chb0t: Could you write a few words about why this solution is faster and what optimizations have you made rather then just claiming it with a large portion of code?
• paparazzo: I did write a few words about what makes this faster. "This should be faster as it skips values already evaluated. Since it skips values evaluated then do not need to check for duplicate."
• t3chb0t: Very good ;-] I've already voted.
• Jianmin Chen: @Paparazzi, I learned the idea to do checking of duplicates through your code; I like to vote one you wrote as an answer. But should we extract small functions for the checking, based on DRP - Do not repeat yourself principle? see line 106 - 114, gist.github.com/jianminchen/dfebe273c5beca0fbbb52981f3934ded

Answer 2

Just a few tips about your PrepareKey method.

private static string PrepareKey(int[] arr, int length)
{
 string key = string.Empty;
 for (int j = 0; j < length; j++)
 {
 key += arr[j].ToString();
 key += ",";
 }
 return key;
}

The entire function can be replaced with:

string.Join(",", arr);

but in cases where you need to build a string with a loop you should use the StringBuilder next time because it's much faster then concatenating strings with the + operator.

---

for (int j = 0; j < length; j++)

You could also the the foreach loop for this as arrays are enumerable.

---

PrepareKey(int[] arr, int length)

This method does not need the length parameter because an array has a Length property.

Answer 3

I offer a different approach which got accepted on Leetcode with the following results

enter image description here

Here are the original results with your code :

enter image description here

As you can see my soltion wins by ~100 ms.

I prefer having a class with overloaded equality checks so that it can be used in the Hashset to determine if an item is duplicate or not. I also replaced this line :

if (!keys.Contains(key))

To this

int previousCount = keys.Count;
keys.Add(triplet);
if (previousCount != keys.Count)

Hashset<T>.Add(..) wont add any duplicates items anyway it's checking that internally but we still need to know if the item is actually duplicate to see if we need to add it to the results I prefer not checking if the key is contained but rather use the returned boolean value from HashSet<T>.Add().

Here is my solution :

internal class Triplet
{
 public int A { get; }
 public int B { get; }
 public int C { get; }
 public Triplet(int a, int b, int c)
 {
 A = a;
 B = b;
 C = c;
 }
 public static bool operator ==(Triplet first, Triplet second)
 {
 return first.A == second.A && first.B == second.B && first.C == second.B;
 }
 public static bool operator !=(Triplet first, Triplet second)
 {
 return !(first == second);
 }
 protected bool Equals(Triplet other)
 {
 return A == other.A && B == other.B && C == other.C;
 }
 public override bool Equals(object obj)
 {
 if (ReferenceEquals(null, obj)) return false;
 if (ReferenceEquals(this, obj)) return true;
 if (obj.GetType() != this.GetType()) return false;
 return Equals((Triplet)obj);
 }
 public override int GetHashCode()
 {
 unchecked
 {
 var hashCode = A;
 hashCode = (hashCode * 397) ^ B;
 hashCode = (hashCode * 397) ^ C;
 return hashCode;
 }
 }
}

And this is the actual algorithm :

public static IList<IList<int>> ThreeSum(int[] nums)
{
 IList<IList<int>> results = new List<IList<int>>();
 HashSet<Triplet> keys = new HashSet<Triplet>();
 if (nums == null || nums.Length == 0)
 return results;
 Array.Sort(nums);
 int length = nums.Length;
 int target = 0;
 for (int i = 0; i < length - 2; i++)
 {
 int firstNo = nums[i];
 // using two pointers to go through once the array, find two sum value 
 int newTarget = target - firstNo;
 int start = i + 1;
 int end = length - 1;
 while (start < end)
 {
 int twoSum = nums[start] + nums[end];
 if (twoSum >= newTarget)
 {
 if (twoSum <= newTarget)
 {
 Triplet triplet = new Triplet(firstNo, nums[start], nums[end]);
 if (keys.Add(triplet))
 {
 results.Add(new List<int> {triplet.A, triplet.B, triplet.C});
 }
 start++;
 end--;
 }
 else
 {
 end--;
 }
 }
 else
 {
 start++;
 }
 }
 }
 return results;
}

• t3chb0t: You don't need to check the Count twice, actually don't need to check it at all.. The Add method returns bool and true if it could add the new item so it's ok to just do if(keys.Add(triplet)) {..}
• Denis: Great tip will update the answer.
• t3chb0t: One more tip... you don't need two collections. At the end the keys collection will have the same items as the results collection. I'd keep the keys and rename it to results and your code will become even simpler. Besides the results still uses list items although you now have the Triplet type.
• Denis: Yeah I noticed that and it kinda annoys me but the return type of ThreeSums must always be IList<IList<int>> or at least that's what the LeetCode site has, thus we can't just return List<Triplet>.
• Denis: We need to return an IList<IList<T>> hashset doesn't implement that interface so we still need to do .ToList() at the end which pretty much the same as saving the items in a different collection of type IList.

Answer 4

Seems your algorithm works fine. I tried to find some issues but i couldn't :)
The only thing i would like to say is about input parameter for ThreeSum function. You change it ! And it's considered as bad practice. Imagine you will want to write some summary. Like this

if(triplets.Count > 0)
{
 Console.WriteLine("Solution has been found !");
 //try to write original array
 for(int i=0;i <array.Length;i++)
 {
 Console.Write(array[i].ToString() + " ");
 }
 //write three numbers
 //...
}

And you cannot write original array as it is sorted now. Even worse. if you implementation change and you will add\remove items from array then it will be completely wrong.

• Jianmin Chen: the idea to make a copy of array from function input argument nums is reasonable, since sorting takes O(nlogn) time usually, and it is not in-place, therefore, function ThreeSum(int[] nums) uses extra O(n) space should be a good practice. It will not cause memory issue.