min & max in specified period

Hello, today it is time to realize the monotonic stack and when it can be used 😀

First, let's start with the requirements for the task:

Write the function that returns the array of numbers with minimums (or maximums) in each period k.

• function gets the array of numbers
• k is the length of period

Example:

input: [1, 5, 4, 7, 0]
k: 3

Expected Result:

[1, 4, 0]

Description:

The array: [1, 5, 4, 7, 0] must be split into periods of 3 numbers.
So we get: [1, 5, 4], [5, 4, 7], [4, 7, 0].
And the result must have minimums numbers from each period:
[1, 5, 4] -> 1
[5, 4, 7] -> 4
[4, 7, 0] -> 0

Requirements:

• time complexity O(n)
• space complexity O(k)

Of course Rules for the code:

1. Choose the right names for variables
2. Choose the right loop statements: for, while, forEach, reduce etc.
3. Avoid excess conditions and comparisons for edge cases
4. Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

Write some first assertions to test your function

const compareNumbers = (arr1: number[], arr2: number[]) => {
  return (
    arr1.length === arr2.length &&
    arr1.every((num, index) => {
      return num === arr2[index];
    })
  );
};

console.assert(compareNumbers(getMinimumsFromPeriods([1, 5, 4, 7, 0], 3), [1, 4, 0]));

Your first thought might be about the monotonic stack, or more specifically the min stack. But this is only half true because we should track the period size.

So how can we do that?

1. Our stack size must not be larger than the period size, because we should store every min value within the period k (i - k), on every step.
2. We have the right to drop previous values that are greater than the current value. This is because the current value has a larger index and it may be used within the next k steps.

How to use min stack with the period?

1. We can store not values but indices.
2. We know the current position of the iteration and the min value index, we can check it every iteration as soon as we get an iteration greater than the period and drop if the min value index is bigger than iterationPosition - period.
3. We will use the pop method to optimize the change in the array, because of it our min value index will be the first item in the stack.
4. To drop the stale index we will have to use the shift method.

P.S.
The shift method, which is somehow optimized by the js engine and its complexity can be neglected. Or we can optimize it ourselves (by converting it to an object, for example), but that is beyond the scope of this article.

Possible implementation

const popMinNumFromStack = (arr: number[], stack: number[]) => {
  return arr[stack.shift()!];
};

export const getMinimumsFromPeriods = (arr: number[], period: number) => {
  const minStackIndices: number[] = [];
  const result: number[] = [];

  arr.forEach((num, index) => {
    // drop the values from the stack that are greater than the current value
    while (minStackIndices.length && num <= arr[minStackIndices[minStackIndices.length - 1]]) {
      minStackIndices.pop();
    }
    // save index
    minStackIndices.push(index);
    const position = index + 1;

    // once the position greater period, we must save the min value and drop stale indices at every step if necessary 
    if (position >= period) {
      const min =
        // drop the stale index (greater than the period)
        position - minStackIndices[0] >= period
          ? popMinNumFromStack(arr, minStackIndices)
          : arr[minStackIndices[0]];
      result.push(min);
    }
  });

  // condition for arrays shorter than the period
  return !result.length && minStackIndices.length
    ? [popMinNumFromStack(arr, minStackIndices)]
    : result;
};

Additional assertions

console.assert(compareNumbers(getMinimumsFromPeriods([1, 5, 4, 7, 0], 2), [1, 4, 4, 0]));
console.assert(compareNumbers(getMinimumsFromPeriods([1, 6, 4, 5, 7, 7], 3), [1, 4, 4, 5]));
console.assert(compareNumbers(getMinimumsFromPeriods([0, 8, 6, 4, 3, 1], 3), [0, 4, 3, 1]));
console.assert(compareNumbers(getMinimumsFromPeriods([], 2), []));
console.assert(compareNumbers(getMinimumsFromPeriods([1, 2], 2), [1]));

Let me know your thoughts in the comment section below! 😉