Complexity Analysis and Optimization with JavaScript: Arrays and Two-Pointer Method

Complexity Analysis and Optimization with JavaScript: Arrays and Two-Pointer Method | CodeSignal Learn

Introduction

Hello there! Are you ready to solve another engaging problem today? We have a practical task that will enhance your problem-solving skills. It involves critical aspects of programming — dealing with arrays and using techniques such as sorting and the two-pointer method . So, let's jump in!

Task Statement

1

Create and Sort Array

Let's embark on our solution-building journey by constructing a sorted array for array B. This array will include pairs of values (val) and their corresponding indices (idx) from array B. Here, val represents the element in B, while idx denotes the index at which val is found in array B. This sorted array will be similar to an associative array, storing 'value-index' pairs. It not only organizes the data for efficient retrieval but also makes it easier for us to traverse the array. Here's the introductory part of our JavaScript function, including the complete sorted array: JavaScriptfunction findAndReplace(A, B) { let B_sorted = []; for (let i = 0; i < B.length; i++) { B_sorted.push({ value: B[i], index: i }); } B_sorted.sort((a, b) => a.value - b.value); In the above code, we generate an array of objects comprising the values from B and their respective indices using a simple loop. Then, the sort function arranges these pairs in ascending order of their values.

Join the 1M+ learners on CodeSignal

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

Our task is as follows. Suppose you have two equally long arrays, A and B, with a length varying from 1 to 1000, with each element being a unique positive integer ranging from $1$ up to $10^6$ . Your challenge is to create a JavaScript function that performs the following steps:

For each element B[i] in array B, double its value to get 2 * B[i].
Find the closest number to 2 * B[i] in array B. Let's call this closest number B[j].
For each index i in array B, get the value at index j in array A, i.e., A[j].
Create a new array where each element is A[j] corresponding to the closest number found in B.

To illustrate this, let's consider an example. We have:

JavaScript

const A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110];
const B = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100];

After running your function, the resulting array should look like this:

JavaScript

const result = [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 is 8. The closest number to 8 in array B is 8, which is at index=7. The number at the same index in array A is 80, so we add 80 to our new array.

The second item in B is 12 at index=1. Double this number is 24. The closest number to 24 in B is 25, which is at index=9. The corresponding index in A has the number 100. So, we add 100 to our new array.

The third item in B is 3 at index=2. Double this number is 6. The closest number to 6 in B is 6, which is at index=4. The corresponding index in A has the number 50. So, we add 50 to our new array.

We continue this process for the rest of the elements in B.

Initialize Pointers and the Result Array

Now that our sorted array (or associative array) is ready, we initiate the right pointer, j, and the result array, res. The former assists in ensuring our search remains within the boundaries of B_sorted, while the latter will be our final output containing the replaced elements from array A. We'll update res as we progress through the solution. JavaScriptfunction findAndReplace(A, B) { let B_sorted = []; for (let i = 0; i < B.length; i++) { B_sorted.push({ value: B[i], index: i }); } B_sorted.sort((a, b) => a.value - b.value); let j = 0; // Initialize right pointer let res = new Array(A.length); // Initialize the result arrayfunction findAndReplace(A, B) { let B_sorted = []; for (let i = 0; i < B.length; i++) { B_sorted.push({ value: B[i], index: i }); } B_sorted.sort((a, b) => a.value - b.value); let j = 0; // Initialize right pointer let res = new Array(A.length); // Initialize the result array

Traverse the Array and Compare

2 \cdot B\_sorted[i].value

Assemble the Result Array

In this final step, we employ the indices from B_sorted to alter the appropriate elements in array A . Based on the position of the right pointer j, we replace the corresponding element in res with the element in A located at the same index. JavaScript res[B_sorted[i].index] = A[B_sorted[j].index]; // Collect the corresponding element from A at the same index as the closest number in B_sorted} return res;} const A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]; const B = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100]; const result = findAndReplace(A, B); console.log(result); res[B_sorted[i].index] = A[B_sorted[j].index]; // Collect the corresponding element from A at the same index as the closest number in B_sorted} return res;} const A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]; const B = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100]; const result = findAndReplace(A, B); console.log(result); And there you have it! You've successfully crafted a JavaScript function capable of producing the required output. This function iteratively replaces each element in array A according to the defined logic and returns the modified array.

Full Code

The fully combined code for this solution is found below. It effectively finds and replaces elements in the array A based on the closest doubled values in the array B: JavaScriptfunction findAndReplace(A, B) { let B_sorted = []; for (let i = 0; i < B.length; i++) { B_sorted.push({ value: B[i], index: i }); } B_sorted.sort((a, b) => a.value - b.value); let j = 0; // Initialize right pointer let res = new Array(A.length); // Initialize the result array for (let i = 0; i < B.length; i++) { let target = 2 * B_sorted[i].value; // The target is twice the current number in the sorted B while (j < B.length - 1 && B_sorted[j + 1].value < target) { j++; // Move the right pointer to find a number smaller than or equal to the target } if (j < B.length - 1 && Math.abs(B_sorted[j + 1].value - target) < Math.abs(target - B_sorted[j].value)) { j++; // Move the right pointer one more step if the next number is closer to the target } res[B_sorted[i].index] = A[B_sorted[j].index]; // Collect the corresponding element from A at the same index as the closest number in B_sorted } return res; } const A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]; const B = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100]; const result = findAndReplace(A, B); console.log(result);function findAndReplace(A, B) { let B_sorted = []; for (let i = 0; i < B.length; i++) { B_sorted.push({ value: B[i], index: i }); } B_sorted.sort((a, b) => a.value - b.value); let j = 0; // Initialize right pointer let res = new Array(A.length); // Initialize the result array for (let i = 0; i < B.length; i++) { let target = 2 * B_sorted[i].value; // The target is twice the current number in the sorted B while (j < B.length - 1 && B_sorted[j + 1].value < target) { j++; // Move the right pointer to find a number smaller than or equal to the target } if (j < B.length - 1 && Math.abs(B_sorted[j + 1].value - target) < Math.abs(target - B_sorted[j].value)) { j++; // Move the right pointer one more step if the next number is closer to the target } res[B_sorted[i].index] = A[B_sorted[j].index]; // Collect the corresponding element from A at the same index as the closest number in B_sorted } return res; } const A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]; const B = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100]; const result = findAndReplace(A, B); console.log(result);

The primary logic of the problem lies in this step. We iterate over each item in B_sorted using its index i. For every item, we calculate the target, which is double the value of the element at the current index in B_sorted. We adjust the position of the right pointer, j, until it points to the closest number that is less than the target ( $2 \cdot B\_sorted[i].value$ ). The operation continues as long as j is within the bound for B_sorted and the next number in the array is smaller than the target.

Once we've identified a number greater than or equal to the target, we compare it with the previous number to see which one is closer to the target. If the next number is closer, we advance j by one step.

JavaScript

    for (let i = 0; i < B.length; i++) {
        let target = 2 * B_sorted[i].value; // The target is twice the current number in the sorted B
        while (j < B.length - 1 && B_sorted[j + 1].value < target) {
            j++; // Move the right pointer to find a number smaller than or equal to the target
        }
        if (j < B.length - 1 && 
            Math.abs(B_sorted[j + 1].value - target) < Math.abs(target - B_sorted[j].value)) {
            j++; // Move the right pointer one more step if the next number is closer to the target
        }