CODEWITHSUNDEEP
scala
coder25
coder25

Reputation: 2393

Improve Two sum problem using Map in scala

I am trying to solve Two sum problem using scala

  val list = List(1,2,3,4,5)
  val map = collection.mutable.Map.empty[Int, Int]
  val sum = 9

  for {
    i <- 0 until list.size
  } yield {
    map.get(sum - list(i)) match {
      case None                => map += (list(i) -> i)
      case Some(previousIndex) => println(s" Indexes $previousIndex $i")
    }
  }

Can anyone suggest an O(n) solution without using mutable map using scala

Upvotes: 0

Views: 217

Answers (2)

Zvi Mints
Zvi Mints

Reputation: 1142

You can try something as follows for the first result:

object Solution extends App {
  def twoSums(xs: List[Int], target: Int): Option[(Int,Int)] = {
    @annotation.tailrec def go(zipped: List[(Int,Int)], map: Map[Int,Int] = Map.empty): Option[(Int,Int)] = {
      zipped match {
        case Nil => None
        case (ele, idx) :: tail =>
          map.get(target - ele) match {
            case Some(prevIdx) => Some((prevIdx, idx))
            case None => go(tail, map + (ele -> idx))
          }
      }
    }
    go(xs.zipWithIndex)
  }

  val res = twoSums(List(1,2,3,4,5), 9)
  println(res)
}

Or via foldLeft for all results:

object Solution extends App {
 def twoSums(xs: List[Int], target: Int): List[(Int, Int)] = {
   xs.zipWithIndex.foldLeft((Map.empty[Int,Int], List.empty[(Int,Int)])) {
     case ((map, results), (ele, idx)) =>
       map.get(target - ele) match {
         case Some(prevIdx) =>(map, (prevIdx, idx) :: results)
         case None =>  (map + (ele -> idx), results)
       }
   }
 }._2

  val res = twoSums(List(1,2,3,4,5), 9)
  println(res)
}

Upvotes: 0

Ivan Kurchenko
Ivan Kurchenko

Reputation: 4063

If you are trying to solve "Two sum problem" - meaning you need from given list find two numbers which gives sum equal to given, can go with:

val list = List(1,2,3,4,5)
val sum = 9

val set = list.toSet
val solution = list.flatMap { item => 
  val rest = sum - item
  val min = Math.min(item, rest)
  val max = Math.max(item, rest)
  if (set(rest)) Some(min, max) else None 
}.toSet
println(solution)

Print result:

Set((4,5))

ScalaFiddle: https://scalafiddle.io/sf/LA6P3eh/0

UPDATE The result required to return indices not values:

val list = List(1,2,3,4,5)
val sum = 9

val inputMap = list.zipWithIndex.toMap
val solution = list.zipWithIndex.flatMap { case (item, itemIndex) =>
  inputMap.get(sum - item).map { restIndex => 
    val minIndex = Math.min(itemIndex, restIndex)
    val maxIndex = Math.max(itemIndex, restIndex)
    minIndex -> maxIndex
  }
}.toSet
println(solution)

Printout: Set((3,4))

ScalaFiddle: https://scalafiddle.io/sf/LA6P3eh/1

Upvotes: 1

Related Questions