fun twoSum(ts: IntArray, k: Int): Boolean {
    val ts = ts.sorted() // O(n log n)
    var lower = 0
    var upper = ts.size-1

    while (upper != lower) {
        val res = ts[upper] + ts[lower]
        when (res.compareTo(k)) {
            -1 -> lower++
            0 -> { return true }
            +1 -> upper--
        }
    }

    return false
}

#Challenge

Given an array of ints and an int k. Determine whether some pair of entries in the array sum to give k.

#Solution

Iterate from opposite sides of the sorted array, comparing the sum of each element to k. If the sum is less than k than the lower bound needs to be increased, otherwise the upper bound needs to be decreased.

#Proof

The improvement here is dependent on the nature of sums. Take for example the naive implementation of summing each value across the array twice to form a 2D matrix.

fun twoSum(ts: IntArray, k: Int): Boolean {
    for ((i, a) in ts.withIndex) {
        for ((j, b) in ts.withIndex) {
            if (i != j && a + b == k) {
                return true
            }
        }
    }

    return false
}

With an array of [1, 2, 3, 4] we construct the following summation matrix using our above implementation.

| nil   3   5   5 |
| 3   nil   6   6 |
| 5     6 nil   8 |
| 5     6   8 nil |

Notice how the matrix is symmetrical along the diagonal. There are repeated calculations taking place in the 2D approach and a mild optimisation could be to only check pairs on one half of the matrix with pairs on the other half.

However the bigger thing to note here is that smaller values lie towards the start of the matrix (top left hand side) and larger values lie towards the end. This is a consequence of the input array being sorted. For any array [a, b, c, d] that is sorted, we can guarantee that a <= b <= c <= d.

Following from this if we fix some value a we can guarantee that a+a <= a+b <= a+c <= a+d. Our main implementation above takes advantage of this fact, if the largest value we have summed with the smallest value is larger than k, then the only possible way to reach k would be to have a smaller largest value, thus we decrease the upper bound. Increasing the upper bound would raise the sum and move us in the opposite direction. Similair logic applies when the sum is smaller than k.

This is a binary search specialised for finding the sums of numbers yielding towards a known value.

#Test Cases

twoSum(intArrayOf(1,3,8,2), 10) // true
twoSum(intArrayOf(3,9,13,7), 8) // false
twoSum(intArrayOf(4,2,6,5,2), 4) // true