Algorithm goal

Find indices of tuples that sum to a target. Assume no duplicates on input.

Test cases in Scala

assert(twoSum(Array.empty, 0).isEmpty, "Empty array has no result")
assert(
  indexArray(Array(-1, 2)) == Map(-1 -> 0, 2 -> 1),
  "We can map numbers to their indices"
)
assert(twoSum(Array(-1, 0, 1, 3, -3, -4), 0) == Set(Set(0, 2), Set(3, 4)))

Algorithm in Scala

10 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

Explanation

The normal approach to this problem is to check for all pairings of values, however that is O(n^2).

In the faster version, we can put the values into a map, and then look up 'target - num' to find if there is a match for the other number for the target number (because 'num1 + num2 = target', then 'num2 = target - num1'. (this is © from www.scala-algorithms.com)

This takes to O(n) which is a good fast solution. We also use Sets to represent the indices since they may be out of order.

Scala concepts & Hints

1. For-comprehension

   The for-comprehension is highly important syntatic enhancement in functional programming languages.

   val Multiplier = 10
   
   val result: List[Int] = for {
     num <- List(1, 2, 3)
     anotherNum <-
       List(num * Multiplier - 1, num * Multiplier, num * Multiplier + 1)
   } yield anotherNum + 1
   
   assert(result == List(10, 11, 12, 20, 21, 22, 30, 31, 32))
   

   ▶ Run code in the IDE

2. View

   The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.