Find a pair of numbers whose sum is equal to the given sum

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

Before starting to think about an approach, let's look at the examples. We see arrays are not sorted, and there are negative numbers. Another important note is "Each integer can be used only once, and the input has exactly one solution". Different approaches could solve the problem. Let's try to use the simplest one - Brute-force.

Brute-force approach

The first idea could be to take the first number and add to it all the other numbers one by one. If we get the target sum, we are done. If not, take the following number and do the same.

Let's see the algorithm in action. For example, we have this array 2, 1, 4, 9, 0, and the target sum is 5.

We take 2 as the first number and try to find the second number.

2 + 1 = 3 3 is not equal 5 (1 is not the second number)

2 + 4 = 6 (4 is not the second number)

2 + 9 = 11 (9 is not the second number)

2 + 0 = 11 (0 is not the second number)

2 can not be the first number because there's no number in the array which could give a sum equal to 5

We take the next number 1 as a second number and do the same. We skip all numbers before 1 because we already checked them. a + b = b + a

1 + 4 = 5. We got the target sum, 1 and 4 are the pair.

The implementation is self-explanatory. It does precisely the same as what we just did manually with only one addition, we're checking the corner cases.

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

The algorithm works fine with only one downside. It's a very slow algorithm. The time complexity is O(n^2). Let's see what we can do better.

Binary search approach

The main issue of the brute-force approach is we're checking all pairs one by one. We can do the same more efficiently. We can sort the array before trying to find a pair number and use binary search.

Here's the idea.

• We sort the array.
• We take the first number as a first
• Use the binary search algorithm to find a number equal to sum - first number.
  • If we found it, we are done.
  • If not, take the next number as a first number and do the same.

        public int[] TwoSum(int[] array, int sum)
        {
            if (array == null || array.Length < 2)
            {
                return Array.Empty<int>();
            }

            Array.Sort(array);

            for (int i = 0; i < array.Length - 1; i++)
            {
                int startIndex = i + 1;
                int rangeLength = array.Length - startIndex;
                int searchNumber = sum - array[i];

                int index = Array.BinarySearch(array, startIndex, rangeLength, searchNumber);

                if(index > 0)
                {
                    return new int[] {array[i], array[index]};
                }
            }

            return Array.Empty<int>();
        }

The time complexity for the approach is O(n Log(n)) because of sorting. It's a bit better than O(n^2).

Each time on a coding interview, you could ask yourself, - Is there a better approach? even if you will not find a better approach. In most cases, it's more important. It still shows you in better lights. You're displaying a thinking process.

Ok, and what about this problem. Is it possible to find a better solution? Yes, it's possible to find the numbers for the linear time.