C# LeetCode 1: Two Sum - (Easy)

LeetCode 1: Two Sum

Problem:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Solution:

public int[] TwoSum(int[] numbers, int targetSum)
{
    var numberToIndex = new Dictionary<int, int>();

    for (int currentIndex = 0; currentIndex < numbers.Length; currentIndex++)
    {
        int currentNumber = numbers[currentIndex];
        int requiredNumber = targetSum - currentNumber;

        if (numberToIndex.ContainsKey(requiredNumber))
        {
            return new int[] { numberToIndex[requiredNumber], currentIndex };
        }

        if (!numberToIndex.ContainsKey(currentNumber))
        {
            numberToIndex[currentNumber] = currentIndex;
        }
    }

    throw new InvalidOperationException("No solution exists for the given input.");
}

Approach:

Instead of checking every pair with a nested loop, we can use a dictionary to remember the numbers we’ve seen as we scan the array, storing the value and its index.

We loop through each number, and subtract it from the target. If the result exists in the Dictionary, we know we've found our two numbers and can return the indexes of these numbers.

But wait how does result = target - currentNumber give us the two numbers?

Well, because if we can't find a match we still add the currentNumber to the Dictionary, so we keep a record we've seen that number somewhere in the array.

Example:

Target is 20;
Current Number is 7;

result = 20 - 7 = 13
We check if 13 has been seen before in the array, if it has we pull the index of this number, and therefore can return index of 13 and index of currentNumber and Bingo we have our two numbers.

Why do we throw an exception?

Well, simply because all paths in a code base need to return a result. However, instead of returning [0,0] which is wrong, we throw an exception to show we've handled all paths, but wasn't a valid outcome.