Closest Value Array Mapping

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!

Here is your challenge. Suppose you have two arrays, A and B, of equal length (from 1 to 1000), where each element is a unique positive integer between 1 and $10^6$. Your goal is to write a Scala function that, for each index i, finds the closest number in array B to 2 * B(i). Once this closest number is found (let's say it's at index j), you should construct a new array using the elements A(j) in the order of increasing i.

Let's look at an example:

val A = Array(10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110)
val B = Array(4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100)

After running your function, the resulting array should be:

Array(80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110)

Let's walk through the first few steps:

• The first item in B is 4 at index 0. Double this number to get 8. The closest number to 8 in B is 8 at index 7. The corresponding value in A at index 7 is 80, so we add 80 to our result.
• The second item in B is 12 at index 1. Double this to get 24. The closest number to 24 in B is 25 at index 9. The corresponding value in A at index 9 is 100.
• The third item in B is 3 at index 2. Double this to get 6. The closest number to 6 in B is 6 at index 4. The corresponding value in A at index 4 is 50.

Continue this process for the rest of the elements in B.

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:

def 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.