Closest Value Array Mapping

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.

Join the 1M+ learners on CodeSignal

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

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:

Scala

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:

Scala

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.

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: Scaladef 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 arraydef 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: Scaladef 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 }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: Scaladef 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 }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 }

Let's analyze the computational complexity of our solution:

Time Complexity: The main steps are sorting the array B and traversing it with two pointers. Sorting an array of n elements takes $O(n \log n)$ time. The two-pointer traversal adds $O(n)$ time. Therefore, the overall time complexity is $O(n \log n)$ , dominated by the sorting step.
Space Complexity: Besides the input arrays, we use B_sorted and res, both of which are arrays of length n. Thus, the space complexity is $O(n)$ .