Return the indices of the two numbers such that they add up to a specific target

Question

(...as I learn Kotlin) I want to get the indices of the two numbers such that they add up to a specific target from a given array of integers.

Solution:

fun sum(values: Array<Int>, result: Int): Array<Int> {
  for ((i, e1) in values.withIndex()) {
    for ((j, e2) in values.drop(i + 1).withIndex()) { // ...or: values.drop(i + 1).forEachIndexed { j, e2 ->
      //println("$i : $e1 >> $j : $e2")
      if (e1 + e2 == result) {
        return arrayOf(i, i + j + 1)
      }
    }
  }
  return emptyArray()
}

Test cases:

class SumTest {
  @Test
  fun testSum() {
    Assert.assertArrayEquals(sum(arrayOf(4, 7, 9, 10, 6, 34), 10), arrayOf(0, 4))
    Assert.assertArrayEquals(sum(arrayOf(5, 7, 9, 10, 21, 34), 43), arrayOf(2, 5))
    Assert.assertArrayEquals(sum(arrayOf(2, 7, 11, 15), 9), arrayOf(0, 1))
    Assert.assertArrayEquals(sum(arrayOf(2, 7, 8, 6, 20), 11), emptyArray())
  }
}

I know this is a pretty simple algorithm, but I would like to avoid the return arrayOf(i, i + j + 1) and modifying the values array in the second loop (values.drop(i + 1).withIndex()) if possible. A functional-towards approach would be great!

Answer 1

1. Kotlin's Array<Int> is equivalent to Java's Integer[] (boxed array). You probably want Kotlin's equivalent of Java's int[] though (primitive array): IntArray.
2. drop and withIndex can be very handy but for simple loops like this they slow things down because they consume more memory than simple index loops. I did some quick benchmarks and in this scenario simple index loops (see below) were 10 times faster.
3. This function looks like a specialized indexOf function. You could write this as an extension function. e.g. indexPairForSumOf.
4. e1 and e2 are okay as names but augend and addend would be much more descriptive.
5. Dair also points this out but instead of returning an array it seems more appropriate to return a Pair<Int, Int>?.

Here is my take on the code if I were to create such a specialized function:

fun IntArray.indexPairForSumOf(sum: Int): Pair<Int, Int>? {
    for (augendIndex in indices) {
        val augend = this[augendIndex]
        for (addendIndex in augendIndex + 1..lastIndex) {
            val addend = this[addendIndex]
            if (augend + addend == sum) {
                return Pair(augendIndex, addendIndex)
            }
        }
    }
    return null
}

However, I recommend creating a more generic indexPairOf function (then you can find a pair of indices for the sum, difference, product, quotient, etc.):

inline fun IntArray.indexPairOf(predicate: (Int, Int) -> Boolean): Pair<Int, Int>? {
    for (firstIndex in indices) {
        val first = this[firstIndex]
        for (secondIndex in firstIndex + 1..lastIndex) {
            val second = this[secondIndex]
            if (predicate(first, second)) {
                return Pair(firstIndex, secondIndex)
            }
        }
    }
    return null
}

fun IntArray.indexPairForSumOf(sum: Int) = indexPairOf { augend, addend ->
    augend + addend == sum
}

Usage:

intArrayOf(4, 7, 9, 10, 6, 34).indexPairForSumOf(10)

Answer 2

sum

The word sum sounds like your taking an iterable of some sort and summing all the values in it. sumsTo would be a better name. Even then, I would expect to return all possible pairings, which the code doesn't currently do.

result

I wouldn't call it result. I'm not that familiar with Kotlin, but sometimes APIs will write to the value you pass in and so the function doesn't return anything but it modifies the result variable. Maybe target is a better choice?

Pair datatype

I would change your datatype from Array to Pair. You are returning a pair of integers satisfying the equation so why choose an array when there is a Pair data type object? I also suggest that if no solution is found that you, yes, return null.

null is often a bad design choice, but I strongly believe this is the exception. If there are no solutions we say that the solution set is null (or the empty set). So if there are no pairs the solution set is null. Reads just like math.

Generalizing to Iterable

You could just iterate over an array of values, but more generally you probably want to iterate over an Iterable collection of integers.

The one cost of this is you have to say arrayOf(...).asIterable().

The code

fun sumsTo(values: Iterable<Int>, target: Int): Pair<Int, Int>? {
  for ((i, e1) in values.withIndex()) {
    for ((j, e2) in values.drop(i + 1).withIndex()) {
      if (e1 + e2 == target) {
        return Pair(i, i + j + 1)
      }
    }
  }
  return null
}