Technique Two Pointers and memoization.

#100daysofcode #javascript #algorithms #interview

Coding Problem: Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

Example:

For example, given [4, 1, 3, 5, 6] and index 0, you should return 3.

Conditions:

1) If two distances to larger numbers are the equal, then return any one of them.
2) If the array at i doesn't have a nearest larger integer, then return null.

Extra:

Follow-up: If you can preprocess the array, can you do this in constant time?

Problem solution:

1) Technique: Two Pointers(in this case not order array)

const findNearestLarger = (idx, arr) => {

    const value = arr[idx], len = arr.length;

    //Two pointers start with the same value
    let [down, up] = [idx, idx]

    while (up < len || down >= 0) {
              ++up;
            --down;
        //  condition 1
        if (down >= 0 && arr[down] > value) { return down }
        if (up < len && arr[up] > value) { return up }
    }
    // condition 2
    return null;
 }

Extra O(1) with preprocessing and memoization:


function dynamic() {

    let cache = new Map();
    let ant_arr = [];

    const preprocessing= findNearestLarger; 


    return function nearestLarger(idx, arr) {

        // Compare previous arr with new arr received
        if (JSON.stringify(ant_arr) === JSON.stringify(arr)) {
            //Follow-up: If you can preprocess the array,
            // can you do this in constant time?
            return cache.get(idx);

        } else {

            // Update the new matrix for the first time
            ant_arr = arr;
            //Preprocessing
            for (let i = 0; i < ant_arr.length; i++) {
                cache.set(i, preprocessing(i, ant_arr));
            }
            // result
            return cache.get(idx);
        }

    }
}

Simple test:


let arr = [4, 1, 3, 5, 6];
let idx = 0; // you should return 3.

let fastNearestLarger = dynamic();

console.log(fastNearestLarger(0, [4, 1, 3, 5, 6]))