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:

After running your function, the resulting array should be:

Let's walk through the first few steps:

• The first item in is 4 at index 0. Double this number to get 8. The closest number to 8 in is 8 at index 7. The corresponding value in at index 7 is 80, so we add 80 to our result.

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:

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.

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:

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:

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:

Let's analyze the computational complexity of our solution:

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

Well done! In this lesson, you learned how to manipulate arrays in Scala and apply techniques such as sorting and the two-pointer method to solve a practical problem efficiently. By working through this challenge, you have strengthened your Scala coding skills and your ability to implement optimized solutions.

Keep practicing similar problems to further develop your problem-solving abilities in Scala. The more you practice, the more confident and skilled you will become. Happy coding!