Optimizing Array Segmentations Using TypeScript Maps

Introduction

Hello there! Welcome to this exciting TypeScript coding lesson, where we'll explore the performance efficiencies gained by utilizing Map types. Our focus will be on solving a problem involving arrays, where we aim to make an optimal choice to minimize the size of segments. Ready to dive in? Let's get started!

Task Statement

In this unit's task, we're tasked with creating a TypeScript function named minimalMaxBlock() . This function should accept an array of integers and compute an interesting property related to contiguous segments within the array. Specifically, you'll need to select a particular integer, k, from the array. By choosing k, the function will remove all occurrences of k from the array, splitting it into several contiguous segments. The unique aspect of k is that it should be chosen such that the maximum length among these segments is minimized. For example, with the list [1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5], removing all instances of 2 results in blocks [1], [3, 1, 4, 4, 4, 1], [5], with the longest containing six elements. However, if we remove all instances of 1, the remaining blocks are [2, 2, 3], [4, 4, 4], [2, 5], with the longest containing three elements. Therefore, the function should return 1, minimizing the maximal block length.

Brute Force Approach

An initial approach to this problem is a brute force method. We can test each possible value in the array by removing it and checking the resulting sub-array sizes. This method involves iterating through the array for each possible k. TypeScriptfunction minimalMaxBlockBruteforce(array: number[]): number { let minMaxBlockSize: number = Number.MAX_VALUE; let minNum: number = -1; const uniqueElements: Set<number> = new Set(array); uniqueElements.forEach((num: number) => { const indices: number[] = []; for (let i: number = 0; i < array.length; ++i) { if (array[i] === num) { indices.push(i); } } indices.unshift(-1); indices.push(array.length); let maxBlockSize: number = 0; for (let i: number = 1; i < indices.length; ++i) { maxBlockSize = Math.max(maxBlockSize, indices[i] - indices[i - 1] - 1); } if (maxBlockSize < minMaxBlockSize) { minMaxBlockSize = maxBlockSize; minNum = num; } }); return minNum; } This method has a time complexity of O(n^2) due to two nested loops: an outer loop iterating through each potential k value, and an inner one through the array for each k.

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 with Example Usage

Here's the complete TypeScript code for our optimized minimalMaxBlock function, leveraging Map for efficient traversal.

TypeScript

function minimalMaxBlock(array: number[]): number {
    const lastOccurrence: Map<number, number> = new Map();
    const maxBlockSizes: Map<number, number> = new Map();

    for (let i: number = 0; i < array.length; ++i) {
        const num: number = array[i];
        if (!lastOccurrence.has(num)) {
            maxBlockSizes.set(num, i);
        } else {
            const blockSize: number = i - lastOccurrence.get(num)! - 1;
            maxBlockSizes.set(num, Math.max(maxBlockSizes.get(num)!, blockSize));
        }
        lastOccurrence.set(num, i);
    }

    lastOccurrence.forEach((pos: number, num: number) => {
        const blockSize: number = array.length - pos - 1;
        maxBlockSizes.set(num, Math.max(maxBlockSizes.get(num)!, blockSize));
    });

    let minNum: number = -1;
    let minBlockSize: number = Number.MAX_VALUE;
    maxBlockSizes.forEach((blockSize: number, num: number) => {
        if (blockSize < minBlockSize) {
            minBlockSize = blockSize;
            minNum = num;
        }
    });

    return minNum;
}

// Example usage
const exampleArray: number[] = [1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5];
const result: number = minimalMaxBlock(exampleArray);
console.log(`The integer to remove for optimal segments is: ${result}`);
// Expected output: The integer to remove for optimal segments is: 1

function minimalMaxBlock(array: number[]): number {
    const lastOccurrence: Map<number, number> = new Map();
    const maxBlockSizes: Map<number, number> = new Map();

    for (let i: number = 0; i < array.length; ++i) {
        const num: number = array[i];
        if (!lastOccurrence.has(num)) {
            maxBlockSizes.set(num, i);
        } else {
            const blockSize: number = i - lastOccurrence.get(num)! - 1;
            maxBlockSizes.set(num, Math.max(maxBlockSizes.get(num)!, blockSize));
        }
        lastOccurrence.set(num, i);
    }

    lastOccurrence.forEach((pos: number, num: number) => {
        const blockSize: number = array.length - pos - 1;
        maxBlockSizes.set(num, Math.max(maxBlockSizes.get(num)!, blockSize));
    });

    let minNum: number = -1;
    let minBlockSize: number = Number.MAX_VALUE;
    maxBlockSizes.forEach((blockSize: number, num: number) => {
        if (blockSize < minBlockSize) {
            minBlockSize = blockSize;
            minNum = num;
        }
    });

    return minNum;
}

// Example usage
const exampleArray: number[] = [1, 2, 2, 3, 1, 4, 4, 4, 1, 2, 5];
const result: number = minimalMaxBlock(exampleArray);
console.log(`The integer to remove for optimal segments is: ${result}`);
// Expected output: The integer to remove for optimal segments is: 1

Introduction

Task Statement

Brute Force Approach

Join the 1M+ learners on CodeSignal

Setup the Solution Approach

Steps to Implement

Initialize the Maps

Traverse the Array

Handle Tail Blocks

Return the Optimal Result

Full Code with Example Usage

Lesson Summary