First Pair Summing to Given Number

Problem:
Given an array of integers, find the first pair whose sum equals the given number.

Example:
Given array [14, 8, 5, 7, 4, 1, 20] and number 12, return (5, 7).

Clarification:
The term "first pair" means the both 2 numbers appear before the latter of any other pair. In above example, the first pair is (5, 7) instead of (8, 4).

Thinking:
I discussed the brute force way to solve this problem (post here). The code is simple and it runs in \(O(n^2)\) time. Why can't we use sorting first? Because it will destroy the appearance order? Do we have a way to keep track of the appearance order?

The answer is YES! We can use an auxiliary array to keep track of the appearance during sorting. After sorting, this array can be used to find the first pair we need. Sorting is always a good approach. At the same time, we should notice that this algorithm is \(O(n\log n)\) in time but \(O(n)\) in space, while the brute-force approach only costs \(O(1)\) space. This is a common trade-off.

In the code below, I assume that we don't know the range of the numbers, so we can only rely on the comparison-based sorting algorithms, which means it's unable to achieve \(O(n)\) complexity in time.


Related Posts:

Brute Force Approach to Solve this Problem