Mastering Arrays and Two-Pointer Technique with TypeScript

Introduction

Welcome to our exciting TypeScript lesson! Today, you'll tackle a fascinating programming challenge that will enhance your problem-solving skills using TypeScript . This exercise involves working with arrays while employing advanced techniques like sorting and the two-pointer method . Let's dive right in!

Task Statement

Your challenge is to create a TypeScript function to work on two equally long arrays, A and B . The arrays have a length between 1 and 1000, and each element is a unique positive integer ranging from 1 to 1,000,000. Your task involves the following steps: For each element B[i] in the array B, double its value to get 2 * B[i] . Identify the closest number to 2 * B[i] in array B, naming it B[j] . For each index i, retrieve the value at index j in array A and assign it to the new array. Return a new array where each element corresponds to A[j] based on the closest value found in B . To illustrate this, let's consider an example: TypeScript const A: number[] = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]; const B: number[] = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100]; After executing your function, the resulting array should appear as follows: TypeScript const result: number[] = [80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110];

Create and Sort Array

Let's begin solving this problem by constructing a sorted structure for array B. We'll use TypeScript type annotations to define an array of objects, where each object contains the elements (value) from B and their respective indices (index). Here’s how to start our TypeScript function with type annotations included: TypeScripttype BElement = { value: number; index: number }; function findAndReplace(A: number[], B: number[]): number[] { let B_sorted: BElement[] = []; 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 this section, we define BElement to clearly structure B_sorted as an array of objects with defined types, which aids in improving the readability and type safety of our code.

Initialize Pointers and the Result Array

Join the 1M+ learners on CodeSignal

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

Full Code

Here is the complete TypeScript solution for this task, which successfully implements the outlined logic:

TypeScript

type BElement = { value: number; index: number };

function findAndReplace(A: number[], B: number[]): number[] {
    let B_sorted: BElement[] = [];
    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: number = 0; // Pointer as a number type
    let res: number[] = new Array(A.length); // Result array with number type

    for (let i = 0; i < B.length; i++) {
        let target: number = 2 * B_sorted[i].value; // Calculate target number
        while (j < B.length - 1 && B_sorted[j + 1].value < target) {
            j++; // Adjust pointer to find closest number
        }
        if (j < B.length - 1 && 
            Math.abs(B_sorted[j + 1].value - target) < Math.abs(target - B_sorted[j].value)) {
            j++; // Increment pointer for closer match
        }
        res[B_sorted[i].index] = A[B_sorted[j].index];  
    }

    return res;
}

const A: number[] = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110];
const B: number[] = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100];
const result: number[] = findAndReplace(A, B);
console.log(result); // Output: [80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110].

type BElement = { value: number; index: number };

function findAndReplace(A: number[], B: number[]): number[] {
    let B_sorted: BElement[] = [];
    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: number = 0; // Pointer as a number type
    let res: number[] = new Array(A.length); // Result array with number type

    for (let i = 0; i < B.length; i++) {
        let target: number = 2 * B_sorted[i].value; // Calculate target number
        while (j < B.length - 1 && B_sorted[j + 1].value < target) {
            j++; // Adjust pointer to find closest number
        }
        if (j < B.length - 1 && 
            Math.abs(B_sorted[j + 1].value - target) < Math.abs(target - B_sorted[j].value)) {
            j++; // Increment pointer for closer match
        }
        res[B_sorted[i].index] = A[B_sorted[j].index];  
    }

    return res;
}

const A: number[] = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110];
const B: number[] = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100];
const result: number[] = findAndReplace(A, B);
console.log(result); // Output: [80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110].

Introduction

Task Statement

Create and Sort Array

Initialize Pointers and the Result Array

Join the 1M+ learners on CodeSignal

Traverse the Array and Compare

Assemble the Result Array

Full Code

Lesson Summary