CODEWITHSUNDEEP
scalafunctional-programming
Xiaohe Dong
Xiaohe Dong

Reputation: 5023

The improved solution for 2 sum algorithm

I try to work out the functional implementation for the algorithm in leetcode (https://leetcode.com/problems/two-sum/#/description)

I guess what I need are 3 functions as followed:

The code looks like this:

  def findTwoSumElements(xs: List[Int], sum: Int): List[(Int, Int)] = {
    val zipWithIndex = xs.zipWithIndex
    var tailElements = zipWithIndex

    val result = zipWithIndex.map(t => {
      val element = zipAndFilter(tailElements, t, sum)
      tailElements = tailElements.tail
      element
     }
    )

    result.flatten.map(t => (t._1._2, t._2._2))
  }

  private def zipAndFilter(xs: List[(Int, Int)], x: (Int, Int), sum: Int): List[((Int, Int), (Int, Int))] = {
    xs.map(t => (t, x)).filter(t => (t._1._1 + t._2._1) == sum)
  }

 println(findTwoSumElements(List(1,2,3,4), 10)) //List()
 println(findTwoSumElements(List(1,2,3,4), 7)) //List((3,2))
 println(findTwoSumElements(List(1,2,3,4), 5)) //List((3,0), (2,1))
 println(findTwoSumElements(List(), 5)) //List()

I would like to improve this part of the code by not using var

  var tailElements = zipWithIndex

  val result = zipWithIndex.map(t => {
     val element = zipAndFilter(tailElements, t, sum)
     tailElements = tailElements.tail
     element
   }
  )

The reason is I want to remove duplicate Tuple[Int, Int], for example, it will return (x, y) and (y, x) together if I dont mutate the tail

Can I have some suggestion or demo code about how to improve it and also for the whole implementation

Upvotes: 1

Views: 2824

Answers (5)

Aamir
Aamir

Reputation: 2422

 def sol(inputArray: Array[Int], target: Int): Array[Int] = {

    def recPass(list: List[(Int, Int)], map: Map[Int, Int]): Array[Int] = list match {
      case (elem, index) :: tail =>
        val complement = target - elem
        if (map.contains(complement)) Array(map(complement), index)
        else recPass(tail, map + (elem -> index))
      case _ => throw new IllegalArgumentException("No two sum solution")
    }
    recPass(inputArray.zipWithIndex.toList, Map.empty)
  }

or

  def sol(nums: Array[Int], target: Int): Array[Int] = {
      def tailRec(map: Map[Int, Int], index: Int): Array[Int] = {

  if (index >= nums.length) throw new IllegalArgumentException("No two sum solution") else {
    if (map.contains(nums(index))) {
      Array(map(nums(index)), index)
    } else {
      tailRec(map + (target - nums(index) -> index), index + 1)
    }
  }
}
  tailRec(Map(), 0)
  }

Upvotes: 0

zijianz
zijianz

Reputation: 21

combinations(2) will always give you O(n^2) complexity. Leetcode will timeout your solution for large inputs.

The last .map(nums.indexOf) won't work since you will get a wrong answer for "[3, 3] seeking for 6".

One solution I would propose is

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    import scala.collection.immutable.HashMap 
    def run(index: Int, map: HashMap[Int, Int]): Array[Int] = {
        val value = nums(index)
        map get (target - value) match {
            case Some(foundInd) => Array(foundInd, index)
            case None => run(index + 1, map + (value -> index))
        }
    }
    run(0, HashMap())
}

It is not really fancy but it runs in linear time, works for all test cases, and without mutation.

Upvotes: 2

Federico Pellegatta
Federico Pellegatta

Reputation: 4017

For the simplified problem in which for each input would have exactly one solution, then you can write the solution as a one-liner:

def twoSum(nums: List[Int], target: Int): List[Int] =
  nums.combinations(2).find(_.sum == target).get.map(nums.indexOf)

Expanded solution, with explicit types:

def twoSum(nums: List[Int], target: Int): List[Int] = {
  val comb: Iterator[List[Int]] = nums.combinations(2) // Get 2-sized combinations iterator
  val find: Option[List[Int]] = comb.find(_.sum == target) // Find the first (and only) combination having sum equals to our target
  val res: List[Int] = find.get // Exactly one solution
  val idx: List[Int] = res.map(nums.indexOf) // Get the indexes in the original list
}

A alternative and generic solution, that allows multiple or no result at all (returns List[List[Int]]):

 def twoSum(nums: List[Int], target: Int): List[List[Int]] =
   nums.combinations(2).collect {
     case couple if couple.sum == target =>
       couple.map(nums.indexOf)
   }.toList

It can be generalized even more accepting combinations size (2 in our example) as a parameter

Upvotes: 7

Karl Bielefeldt
Karl Bielefeldt

Reputation: 49148

Scala has a built-in combinations method that does a lot of the work for you. This makes finding the target sum as easy as:

val result = nums.combinations(2).filter{case List(x, y) => x + y == target}.next

Then you can map the answer back to the indices by:

val indices = result map (nums.zipWithIndex.toMap)

Upvotes: 1

silvaren
silvaren

Reputation: 730

Ok I'll take a shot :)

How about the solution below:

  def twoSum(nums: Seq[Int], target: Int): Seq[Int] =
    nums.zipWithIndex.
      filter(x =>
        (nums.take(nums.indexOf(x._1)) ++ nums.drop(nums.indexOf(x._1)+1))
        .contains(target - x._1)).map(_._2)

Here's what being done (using array [2, 7, 11, 15] and target=9 as example):

  1. We zip with index to get each number paired with its position, e.g. (2,0),(7,1)...
  2. We filter each pair by the presence of its number difference with the target (i.e. target - number) in the original collection with itself removed (see the nums.take ++ nums.drop)
  3. We map each resulting pair to its position part (e.g. (2,0) => 0, (7,1) => 1)
  4. The resulting sequence contains only the positions of the numbers that have corresponding sum-pairs that add to the target: (0,1).

Upvotes: 2

Related Questions