How to use Stack In Javascript

Using Iteration

In this example we calculate the maximum of minimum values for all window sizes in the given array using stack-based approach. By using stack based approach we find the next smaller and previous smaller of each element and update the maximum of window with size as the difference in their indices.

Example: This JavaScript code is the implementation of the above approach to find maximum of minimum for every window size in a given array

JavaScript

const maxMinWinSize = arr => {
    const res = [];
    const stack = [];
    const left = [];
    const right = [];

    // Find the next smaller element on the left
    for (let i = 0; i < arr.length; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        if (stack.length === 0) {
            left.push(-1);
        } else {
            left.push(stack[stack.length - 1]);
        }
        stack.push(i);
    }

    stack.length = 0;

    // Find the next smaller element on the right
    for (let i = arr.length - 1; i >= 0; i--) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        if (stack.length === 0) {
            right[i] = arr.length;
        } else {
            right[i] = stack[stack.length - 1];
        }
        stack.push(i);
    }

    // Initialize result array with -Infinity
    for (let i = 0; i <= arr.length; i++) {
        res.push(-Infinity);
    }

    // Calculate max of min for each window size
    for (let i = 0; i < arr.length; i++) {
        let len = right[i] - left[i] - 1;
        res[len] = Math.max(res[len], arr[i]);
    }

    // Fill in any missing elements in the result array
    for (let i = arr.length - 1; i >= 1; i--) {
        res[i] = Math.max(res[i], res[i + 1]);
    }

    return res.slice(1); // Remove the first element (which is -Infinity)
};

const array = [1, 2, 3, 5, 1, 7, 3];
console.log(maxMinWinSize(array));

Output

[
  7, 3, 2, 1,
  1, 1, 1
]

Time Complexity: O(N), where N is the size of the given array.

Auxiliary Space: O(N), for using stack and additional arrays.

JavaScript Program to Find Maximum of Minimum for Every Window Size in a Given Array

Given an array of integers, find the maximum of minimums for every window size in the array. The window size varies from 1 to the size of the array.

Example:

Input:  Array: [1, 2, 3, 5, 1, 7, 3]
Output: [7, 3, 2, 1, 1, 1, 1]
Explanation: The first element in the output indicates the maximum of minimums of all windows of size 1. 
Minimums of windows of size 1 are {1}, {2}, {3}, {5}, {1}, {7} and {3}. 
Maximum of these minimums is 7
The second element in the output indicates the maximum of minimums of all windows of size 2. 
Minimums of windows of size 2 are {1}, {2}, {3}, {1}, {1}, and {3}. 
Maximum of these minimums is 3
The third element in the output indicates the maximum of minimums of all windows of size 3. 
Minimums of windows of size 3 are {1}, {2}, {1}, {1} and {1}. 
Maximum of these minimums is 2
Similarly, other elements of output are computed.

Below are the approaches to find maximum of minimum for every window size in a given array:

Table of Content

Using Iteration
Using Stack

Tags:

#JavaScript-Program #JavaScript #Web Technologies

Using Iteration

How to use Stack In Javascript

JavaScript Program to Find Maximum of Minimum for Every Window Size in a Given Array

Similar Reads

Contact Us