Two-Sum - Pre-sort Optimization Algorithm Design

Question

🧩 Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order?

🚀 Original Two-Sum

Determine whether there are two items whose individual capacity will perfectly equal the total capacity while ensuring the same item cannot be selected twice.

• Input: An Int representing the total capacity and an Array of Int's representing items' individual capacities.
• Output: A Boolean representing whether it is possible for two of the items to equal the total capacity.
• Time complexity: Linear growth, $O(n)$
• Space complexity: Linear growth, $O(n)$

Samples

Input: [4, 5, 2, 6]

• Total capacity: 10
• Expect: true

Input: [4, 5, 2, 5]

• Total capacity: 10
• Expect: true

Input: [4, 5, 2, 7]

• Total capacity: 10
• Expect: false

Pseudocode

1. Create a Set searchSet to store the item's that have already been examined.

2. Iterate through the input Array of item capacities.

   2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity

   2b. If searchSet contains the targetCapacity, return true.

   2c. Else, add the itemCapacity to the searchSet.

3. Return false if the entire input is iterated through without finding a match.

🏗️ Pre-Sort

1. Save a new var lastTargetCapacity
2. If the current itemCapacity < lastTargetCapacity, there are no possible two-sums and return false.

i.e.

Input: [6,2,1,0]

• Total capacity: 9

Iterations

1. targetCapacity = 9 - 6, lastTargetCapacity = 3
2. Return false because the itemCapacity of 2 < lastTargetCapacity of 3.

Answer 1

The Two Sum solution can be optimized for runtime performance given the input Array is pre-sorted in ascending or descending order.

If Binary Search is used to find the targetCapacity above, it will run in logarithmic, $O(logn)$, average runtime. This is faster than the pseudocode above that runs in linear, $O(n)$, runtime using iteration and hashing.

If sorting was not provided in the input then it would not be possible to sort and search faster than $O(n)$. The best that could be done would be $O(nlogn)$ with a strategy such as Quicksort and Binary Search.

See: Stanford - Two Sum Explanation

Answer 2

Yes, you can solve the two-sum problem in $O(n)$ time, if the numbers are presented in sorted order. See my other answer for how to do it; it involves a linear scan. This is asymptotically optimal, as it already takes $O(n)$ time even to read the input, and solving the problem may require reading the entire input, so there can no further asymptotic improvement.