Algorithm goal

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

Test cases in Scala

assert(threeSum(Array.empty, 0).isEmpty)
assert(
  threeSum(Array(-1, 0, 1, 2, -1, -4), 0) ==
    Set(List(-1, 0, 1), List(-1, -1, 2))
)

Algorithm in Scala

39 lines of Scala (compatible versions 2.13 & 3.0).

Explanation

The normal approach to this problem is to check for all pairings of values, however that is O(n^3) because we would be checking for every triplet possible.

However, what we can do is to build on TwoSum, which is O(n), to get O(n^2), in the same vein as in Twosum. (this is © from www.scala-algorithms.com)

Scala concepts & Hints

1. Collect

   'collect' allows you to use Pattern Matching, to filter and map items.

   assert("Hello World".collect {
     case character if Character.isUpperCase(character) => character.toLower
   } == "hw")
   

   ▶ Run code in the IDE

2. Ordering

   In Scala, the 'Ordering' type is a 'type class' that contains methods to determine an ordering of specific types.

   assert(List(3, 2, 1).sorted == List(1, 2, 3))
   
   assert(List(3, 2, 1).sorted(Ordering[Int].reverse) == List(3, 2, 1))
   
   assert(Ordering[Int].lt(1, 2))
   
   assert(!Ordering[Int].lt(2, 1))
   

   ▶ Run code in the IDE

3. Pattern Matching

   Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

   assert("Hello World".collect {
     case character if Character.isUpperCase(character) => character.toLower
   } == "hw")
   

   ▶ Run code in the IDE

4. View

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