Two Sum

Problem Statement

 

Given an array of integers, find two numbers such that they add up to a specific target number.

 

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

 

Please note that your returned answers (both index1 and index2) are not zero-based.

 

You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

 

Source: https://leetcode.com/problems/two-sum/
Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: O(N)

Solution 
 

public Tuple<int, int> TwoSum(int[] numbers, int target)
{
    // Maintain map for the integers to have O(1) lookup
    Dictionary<int, int> dictionary = new Dictionary<int, int>();
            
    for (int index = 0; index < numbers.Length; index++)
    {
        // If exists in the map
        if (dictionary.ContainsKey(target - numbers[index]))
        {
            // Output is expected ordered by index
            if (index < dictionary[target - numbers[index]])
                return new Tuple<int, int>(index + 1, dictionary[target - numbers[index]] + 1);
            else
                return new Tuple<int, int>(dictionary[target - numbers[index]] + 1, index + 1);
        }
        else
        {
            if (!dictionary.ContainsKey(numbers[index]))
                dictionary.Add(numbers[index], index);
        }
    }

    // Return null if solution not found
    return null;
}