Interview type problems

twoSum.scala

import scala.annotation.tailrec

object ShittySolution {
  // Given an array of integers, return indices of the two numbers such that they add up to a specific target.
  //
  // You may assume that each input would have exactly one solution, and you may not use the same element twice.
  // https://leetcode.com/problems/two-sum/
  // NB: More efficient solution would iterate once over the array and keep a Map of values and indicies
  
  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    for (idx <- 0 until nums.length - 1) {
      for (idy <- idx + 1 until nums.length) {
        if (nums(idx) + nums(idy) == target) {
          return Array(idx, idy)
        }
      }
    }
    throw new IllegalArgumentException("No solution exists")
  }

  def functionalTwoSum(nums: Array[Int], target: Int): Array[Int] = {
    val numsList = nums.toList
    recursiveTwoSum(numsList.zipWithIndex, target) match {
      case Some((idx, idy)) => Array(idx, idy)
      case None => throw new IllegalArgumentException("No solution exists")
    }
  }

  @tailrec
  def recursiveTwoSum(nums: Seq[(Int, Int)], target: Int): Option[(Int, Int)] = {
    nums match {
      case Nil => None
      case head::tail => tail.find{
        case (elem, _) => elem + head._1 == target
      } match {
        case Some((_: Int, idy: Int)) => Some(head._2, idy)
        case None => recursiveTwoSum(tail, target)
      }
    }
  }
}