Closest Value Array Mapping | CodeSignal Learn

Closest Value Array Mapping | CodeSignal Learn

Introduction

Welcome! Today, we will tackle an engaging problem that will strengthen your Scala programming and problem-solving skills. This task focuses on working with arrays and applying techniques such as sorting and the two-pointer method . By the end of this lesson, you'll have a deeper understanding of how to manipulate arrays efficiently in Scala. Let's get started!

Task Statement

10^6

Solution Building: Step 1

Let's begin by constructing a sorted list of pairs from array B. Each pair will contain the value from B and its corresponding index. In Scala, we can achieve this using zipWithIndex to pair each value with its index and then sortBy to sort the pairs by value. Here's how you can do this in Scala: Scaladef findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = { val B_sorted = B.zipWithIndex.sortBy(_._1) // B_sorted is now an array of (value, index) pairs, sorted by value You sort by value, so the original order of B is lost in B_sorted. But the original indices are preserved in the second element of the tuple (_._2). This allows you to map back to A correctly. This sorted array of pairs will help us efficiently search for the closest value to our target in the next steps.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 2

Now that we have our sorted array of value-index pairs, let's initialize a pointer j and a result array res. The pointer j will help us traverse B_sorted, and res will store our final output. Here's how to set this up in Scala: def findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = { val B_sorted = B.zipWithIndex.sortBy(_._1) var j = 0 // Initialize the right pointer val res = Array.fill(A.length)(0) // Initialize the result array

Solution Building: Step 3

The main logic of the solution is implemented in this step. We iterate through each element in B_sorted using its index i. For each element, we calculate the target value as twice the current value. We then move the pointer j to find the closest value in B_sorted to this target. Here's the Scala code for this logic: def findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = { val B_sorted = B.zipWithIndex.sortBy(_._1) var j = 0 val res = Array.fill(A.length)(0) for (i <- B_sorted.indices) { val target = 2 * B_sorted(i)._1 while (j < B_sorted.length - 1 && B_sorted(j + 1)._1 < target) { j += 1 } if (j < B_sorted.length - 1 && math.abs(B_sorted(j + 1)._1 - target) < math.abs(target - B_sorted(j)._1)) { j += 1 }

Solution Building: Step 4

Finally, we use the indices from B_sorted to update the result array. For each position, we set res(B_sorted(i)._2) to the value from A at the index corresponding to the closest value found in B_sorted. Here's the complete Scala function: def findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = { val B_sorted = B.zipWithIndex.sortBy(_._1) var j = 0 val res = Array.fill(A.length)(0) for (i <- B_sorted.indices) { val target = 2 * B_sorted(i)._1 while (j < B_sorted.length - 1 && B_sorted(j + 1)._1 < target) { j += 1 } if (j < B_sorted.length - 1 && math.abs(B_sorted(j + 1)._1 - target) < math.abs(target - B_sorted(j)._1)) { j += 1 } res(B_sorted(i)._2) = A(B_sorted(j)._2) } res }

Scala

def findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = {
  val B_sorted = B.zipWithIndex.sortBy(_._1)
  var j = 0 // Initialize the right pointer
  val res = Array.fill(A.length)(0) // Initialize the result array

Scala

def findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = {
  val B_sorted = B.zipWithIndex.sortBy(_._1)
  var j = 0
  val res = Array.fill(A.length)(0)

  for (i <- B_sorted.indices) {
    val target = 2 * B_sorted(i)._1
    while (j < B_sorted.length - 1 && B_sorted(j + 1)._1 < target) {
      j += 1
    }
    if (j < B_sorted.length - 1 &&
        math.abs(B_sorted(j + 1)._1 - target) < math.abs(target - B_sorted(j)._1)) {
      j += 1
    }

Scala

def findAndReplace(A: Array[Int], B: Array[Int]): Array[Int] = {
  val B_sorted = B.zipWithIndex.sortBy(_._1)
  var j = 0
  val res = Array.fill(A.length)(0)

  for (i <- B_sorted.indices) {
    val target = 2 * B_sorted(i)._1
    while (j < B_sorted.length - 1 && B_sorted(j + 1)._1 < target) {
      j += 1
    }
    if (j < B_sorted.length - 1 &&
        math.abs(B_sorted(j + 1)._1 - target) < math.abs(target - B_sorted(j)._1)) {
      j += 1
    }
    res(B_sorted(i)._2) = A(B_sorted(j)._2)
  }

  res
}