I need help to optimize my code speed for Sum 3 problem

Question

Puzzle description

*Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets.

Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Example 2: Input: nums = [] Output: []

Example 3: Input: nums = [0] Output: []

Constraints: 0 <= nums.length <= 3000 -105 <= nums[i] <= 105*

End Of Desctiption

I am having some trouble solving this puzzle from leetcode I am running over the time limit so my code needs to be optimized.

The two locations I know can be fixed are the double loop entry and the loop to check if any of the lists match.

An extra issue that is not stopping me from passing but is something that could cause this to fail in some conditions is the check in the list to see if it contains the distance and is not equal to the first or second iteration since IndexOf will return the first index found.

As for the loop check I found a faster solution in python but I am unsure of the c# equivilent

Python code find whether a list

exists in list of list.

# Input List Initialization 
Input = [[1, 1, 1, 2], [2, 3, 4], [1, 2, 3], [4, 5, 6]] 
  
# List to be searched 
list_search = [1, 1, 1, 2] 
  
# Using in to find whether  
# list exists or not 
if list_search in Input: 
    print("True") 
else: 
    print("False") 

Here is my current code solution (TLDR: it works but is too slow)

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        
        /*total must always = 0
        ideas to use a sort on each list to check if there are
        multiple arrays that are the same combination of values
        
        the last sum can be assumed and pulled via Arraylist since there can only be one answer assumed
        values can be quickly ignored if there is no corrisponding 3rd value that sums to 0 
        ex -1,-1, do we have a value of 2 if not than we can ignore this combination
        also if we do than we will want to temporarly store it than sort the list and compare to our already existing
        list
        
        Something to think about if the numbs array is sorted ahead of time can we ignore using the sort operation
        in some conditions to save cpu time
        
        If the size of the nums array is less than 3 than return a blank array
        also if the size of the array = 3 we can assume the solution and return nums (maybe)
        
        A possible way to make this faster would be to find a way to assume all possible values have been found or use a Addoku/Arrow-Sudoku method of solving and see if for example a value in the array is 9 and there are no negative values in a set of 2 that can = -9 than 9 can be instantly ignored and removed since the combination is not possible.
        
        I dont think the index check is perfect since indexof checks for the first value but it has been passing all of my test cases so I will leave it for now but I will need to find a better way to remove I and Y elements from the index check to avoid duplicates.
        */
        
        IList<IList<int>> mainLs = new List<IList<int>>();
        if(nums.Length < 3){
            return mainLs;
        }
        
        
        for(int i = 0; i< nums.Length; i++){
            int currentVal = nums[i];
           for(int y = 0; y< nums.Length; y++){
               //is there an easier way to skip the matching index
               if(i == y){
                   continue;
               }else{
                   /*
                   We will sum the two elements together and check the distance
                   between the sum and 0. Than if we have the distance in our index and the value to sum to 0
                   is not the index we are on since we need to avoid duplicates than add that value to the array
                   */
                   ArrayList tempNumls = new ArrayList(nums);
                 
                  
                   int sum = currentVal + nums[y];
                   int distance = Math.Abs(sum - 0);
                   //Math abs always produces a postive value which will work for us if the sum is negative but if the sum is positive it will return a positive value so we multiply by -1 to produce the proper result.
                   if(sum > 0){
                       distance = distance * -1;
                   }
                   //output the results found
                   // Console.WriteLine("distance: "+distance + " X & Y = "+ currentVal + " & " + nums[y]);
                   
                   if(tempNumls.Contains(distance) && tempNumls.IndexOf(distance) != y && tempNumls.IndexOf(distance) != i){
                   
                       ArrayList tempIls = new ArrayList() {currentVal, nums[y], distance};
                       //sorting and comparing will be the easiest way to make sure we do not have matching lists
                       tempIls.Sort();
                       var list = tempIls.Cast<int>().ToList();
                       bool match = false;
                       //best to find a better way to traverse and compare the list of list without 
                       //needing to loop over them all
                       foreach (List<int> listname in mainLs)
                    {
                          if (listname.SequenceEqual(list))
                             {
                                 match = true; 
                                break;
                             }
                    }
                       if(!match){
                       mainLs.Add(list);
                       }
                       
                   }
               }
           }
        }
        
        return mainLs;
    }
}

Answer 1

"Thank you I added everyone's suggestions and the code sped up tremendously and passed 315/318 test cases. After watching a few videos on the problem I noticed that the main issue was that I was doing far too many checks and approaching this problem the wrong way so it had no chance to pass unless I restructured it. I will attach a sample solution that I walked through. "

    public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {

        
        HashSet<IList<int>> mainLs = new HashSet<IList<int>>();
        IList<IList<int>> returnedList = new List<IList<int>>();
        if(nums.Length < 3){
            return returnedList;
        }
        
        Array.Sort(nums);
       
        for(int i = 0; i< nums.Length -2; i++){
            if(i == 0 || (i> 0 && nums[i] != nums[i-1])){
                int low = i + 1;
                int size = nums.Length;
                int high = size - 1;
                int sum = 0 - nums[i];
                while (low < high){
                    if (nums[low] + nums[high] == sum){
                        mainLs.Add(new List<int>(){nums[i],nums[low], nums[high]});
                         while (low < high && nums[low] == nums[low+1]) {low++;}
                        while (low < high && nums[high] == nums[high-1]) {high--;}
                      
                        
                        low++;
                        high --;
                    }else if(nums[low] + nums[high] > sum){
                        high--;
                    }else{
                        low++;
                    }
                }
            }
        }
        returnedList = new List<IList<int>>(mainLs.ToList());
        return returnedList;
    }
}

Answer 2

You can use Counter from collections as an indexing mechanism as well as a means to cover special cases (i.e. zeroes, repeated numbers).

The benefit of indexing numbers is to allow quick verification that a number exists to complete a given sum. You can use it to find negative version of positive numbers that you combine with zero. You can also use it to find -2n when you have a number that is present twice in the list.

For the remaining (distinct) triplets, combine each positive number with every other number and check is the opposite value is present.

from collections import Counter
def sum3(A):
    cA = Counter(A)
    if cA[0]>3: yield [0,0,0]  # triple zeros, then [-x,0,x]
    if cA[0]>0: yield from ( [-p,0,p] for p in cA if p>0 and -p in cA )
    del cA[0] # all triplets with zero covered
    for N,c in cA.items():
        if N == 0: continue
        if c>1 and -2*N in cA: yield [-2*N,N,N] # cover repeated numbers
        if N<1: continue                        # then distinct numbers ...
        yield from ([a,-a-N,N] for a in cA if -a-N in cA and len({a,-a-N,N})==3)

output:

result = list(sum3([-1,0,1,2,-1,-4]))
# [[-1, 0, 1], [2, -1, -1]]        

Answer 3

Just like to propose two optimizations to the algorithm posted above by Tanner:

1. In the outer loop, there's no need to go all the way till "nums.Length-2". We know that a "sum zero triplet" can not contain 3 positive numbers. There got to be at least 1 negative number. So once nums[i]>0 we can break from the outer loop.
2. In the inner loop, there's no need to always go all the way till "nums.Length-1". Suppose nums[i]=-10, and nums[i+1]=-9 . In order to balance them out, the third number can not be larger than +19. During the inner loop, we can trust on "low" to increment and require even lower values than +19 for balancing. Therefore, the initial "high" value can be much lower than nums.Length-1. We can use binary search to find the value closest to nums[i]+nums[i+1].