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;
    }
  }
}

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

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

Here are the original results with your code :

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;
}

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.