2 Sum [Easy]

https://leetcode.com/problems/two-sum

Find 2 numbers in an array whose sums add up to target . A variant of this question is finding the largest 2 numbers that are <= target There's 2 approaches to it

Find a single pair

Approach 1

We're returning the index of the 2 numbers here

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
  val sorted = nums.zipWithIndex.sorted

  def go(i: Int, j: Int): Array[Int] =
    if (sorted(i)._1 + sorted(j)._1 > target) go(i, j - 1)
    else if (sorted(i)._1 + sorted(j)._1 < target) go(i + 1, j)
    else Array(sorted(i)._2, sorted(j)._2)

  go(0, nums.length - 1)

}

Approach 2

If question asks simply find any 2 numbers that = target you can use a map to find if the target - k is in the map. if k == (target - k) then there must be 2 occurrences of k in the array

def twoSum(nums: Array[Int], target: Int): Option[(Int, Int)] = {

  val m = nums.foldLeft(Map.empty[Int, Int]) { (m, n) =>
    m.get(n).fold(m + (n -> 1))(v => m + (n -> (v + 1)))
  }

  m.find {
    case (k, v) =>
      val other = target - k
      if (other == k) {
        v == 2
      } else m.contains(k)
  }.map{case (k, _) => k -> (target - k)}

}

Find all pairs

Approach 1

def findPairs(is: Vector[Int], target: Int): List[(Int, Int)] = {
  
  val m = is.foldLeft(Map.empty[Int, Int]){(m, i) => 
    m.get(i).fold(m + (i -> 1))(v => m + (i -> (v + 1)))
  }
  
  def go(out: List[(Int, Int)], m: Map[Int, Int]): List[(Int, Int)] = 
    m.headOption.fold(out){ case (i, freq) =>
      val other = target - i
      if (other == i) {
        if (freq > 1) 
          go(
            0.until(freq / 2).foldLeft(out)((out, _) => (i -> i) :: out),
            m.tail
          )
        else go(out, m.tail)
      } else {
        m.get(other).fold(go(out, m.tail))(freqOther => 
          go(
            0.until(Math.min(freq, freqOther)).foldLeft(out)((out, _) => (i -> other) :: out),
            m.tail - other                                  
          )
        )
    }    
  }
  
  go(List.empty, m)
}

Approach 2

def findPairs(is: Vector[Int], target: Int): List[(Int, Int)] = {
    
  @tailrec
  def go(sorted: Vector[Int], out: List[(Int, Int)]): List[(Int, Int)] = {
    if (sorted.length == 1) out
    else if (sorted.head + sorted.last == target) 
      go(
       // or you can maintain `i` and `j` pointers in Approach 1 in 
       // Find a single pair above
        sorted.tail.dropRight(1),
        (sorted.head -> sorted.last) :: out
      )
    else if (sorted.head + sorted.last > target)
      go(
        sorted.dropRight(1),
        out
      )
    else 
      go(
        sorted.tail,
        out
      )
  }
  
  go(is.sorted, List.empty)
}