Find a pair of numbers in an array with a given sum: Linear Time Complexity

Given an array of integers and sum, return a pair of numbers whose sum is equal to the given sum.

Note: Each integer can be used only once, and the input has exactly one solution

 

Example 1

Input: array = [2, 1, 4, 9, 0], sum = 5

Output: [1, 4]

Explanation: 1 + 4 = 5

Example 2

Input: array = [-2, 1, 4, 2, 10], sum = 0

Output: [-2, 2]

Explanation: -2 + 2 = 0

We already saw,how to solve this problem in O(n Log(n)) and O(n^2) time. We were using the binary search and brute-force approach. Let's think about something different.

Hash table approach

Here's the idea:

• Traverse the array
  • Store in the cache a value sum - item1 as a key and item1 as a value
  • Check the cache on the existence item2
    • If the cache contains item2, it means we already saw item1, and we can return the pair

    public int[] TwoSum(int[] array, int sum)
    {
        if (array == null || array.Length < 2)
        {
            return Array.Empty<int>();
        }
    
        Dictionary<int, int> cache = new Dictionary<int, int>();
    
        for (int i = 0; i < array.Length; i++)
        {
            if (cache.ContainsKey(array[i]))
            {
                return new int[] { cache[array[i]], array[i] };
            }
    
            cache[sum - array[i]] = array[i];
        }
    
        return Array.Empty<int>();
    }

The time complexity for the approach is O(n). The current solution is faster than already reviewed approaches but requires O(n) space.