= Solution
Search only the suffix strictly after each candidate first index. This enforces distinct indices even when the target is twice an existing value. Compute the complement in `Long` to prevent <integer overflow>: subtracting two `Int` values can require 33 signed bits.
``
def twoSum(a: Array[Int], target: Int): (Int, Int) = {
def lowerBound(from: Int, wanted: Long): Int = {
var lo = from
var hi = a.length
while (lo < hi) {
val mid = lo + (hi - lo) / 2
if (a(mid).toLong < wanted) lo = mid + 1
else hi = mid
}
lo
}
var i = 0
while (i < a.length - 1) {
val wanted = target.toLong - a(i).toLong
val j = lowerBound(i + 1, wanted)
if (j < a.length && a(j).toLong == wanted) return (i, j)
i += 1
}
(0, 0)
}
``
The outer <loop invariant> says that no solution has a smaller first index than `i`, when a pair is written in increasing index order. A failed suffix <binary search> proves there is no partner for the current `i`, extending the excluded prefix by one. A successful return has $j>i$ and $a(j)=t-a(i)$ in exact <integer arithmetic>. At exhaustion, every possible ordered pair has been excluded, so \b[the sentinel `(0,0)` means no solution]. The inner <loop invariant> is the standard lower-bound partition, restricted to the suffix starting at `i + 1`.
There are at most $N-1$ suffix searches, each taking $O(\log(N+1))$ <running time>, so the total is $O(N\log(N+1))$, customarily written $O(N\log N)$ for $N\geq2$. <Auxiliary space> is $O(1)$. Empty and singleton <arrays> immediately return the sentinel. This is <distinct-index two-sum by suffix lower bounds>; a faster <two-pointer technique> is also possible on a <sorted array>, but the code here directly meets the requested search-based bound.
Back to article page
