DEV Community

Discussion on: Daily Challenge #63- Two Sum

Collapse
 
peledzohar profile image
Zohar Peled • Edited

The input will always be valid that's even worst than premature optimizations.

However, for the purpose of this challenge, I'll take that assumption, because while super important, input validation is boring.

My answer inspired by willsmart's answer.

C#, with comments on every line, so that everyone can understand it even if they don't speak the language:

The simple, O(n2) solution - using a nested loop.


    (int Index1, int Index2) TwoSum(int[] array, int target)
    {
        // iterate the array from 0 to length -2
        for (var i = 0; i < array.Length - 1; i++)
        {
            // iterate the array from i+1 to length -1
            for (var j = i + 1; j < array.Length; j++)
            {
                // if sum found
                if (array[i] + array[j] == target)
                {
                    // return both indexes
                    return (i, j);
                }
            }
        }
        // indicate no match found, required by the c# compier.
        return (-1, -1); 
    }

The sophisticated, O(n) solution - using a single loop and a helper hash map.

    int Index1, int Index2) TwoSumImproved(int[] array, int target)
    {
        // In .Net, A dictionary is basically a hash map. here the keys and values are both ints
        var map = new Dictionary<int, int>();

        // iterate the full length of the array.
        for (var i = 0; i < array.Length; i++)
        {
            // calculate the value needed to add to the current value to get the target sum
            var valueNeeded = target - array[i];

            // check if the map contains the value needed as it's key, If it does, return true and populate the int j
            // The TryGetValue time complexity is approaching O(1)
            if (map.TryGetValue(valueNeeded, out int j))
            {
                // return both indexes
                return (j, i);
            }
            // add to the map, where the key is the array value and the value is the index.
            map.Add(array[i], i);
        }
        return (-1, -1); // indicate no match found
    }

Try it online