Two-Sum - Pre-sort Optimization Algorithm Design 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

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

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.

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


️ Pre-Sort

Save a new var lastTargetCapacity
If the current itemCapacity &lt; lastTargetCapacity, there are no possible two-sums and return false.

i.e.
Input: [6,2,1,0]

Total capacity: 9

Iterations

targetCapacity = 9 - 6, lastTargetCapacity = 3
Return false because the itemCapacity of 2 &lt; lastTargetCapacity of 3.
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