Solving Range and Boundary Problems with Monotonic Stacks in JavaScript

In algorithmic design and performance-critical frontend engineering, problems involving boundary lookups—such as locating the next higher stock price, calculating histogram spans, or predicting warmer weather days—frequently tempt developers into nested loops. A naive double-loop approach scans forward from each position, resulting in an $O(N^2)$ quadratic time complexity that degrades rapidly when processing sizable datasets, animation timelines, or high-frequency analytics feeds.

The Monotonic Stack pattern collapses these boundary searches down to an optimal $O(N)$ linear time complexity. By maintaining an internal stack where elements or indices remain in strict ascending or descending order, incoming values systematically resolve pending items. Whenever a newly inspected value violates the stack's ordering invariant, previously unresolved elements are popped and assigned their boundary match. Because each array index is pushed and popped at most once over the entire iteration, the pattern delivers predictable, deterministic performance even with duplicates and boundary edge cases.

Example #

// Monotonically decreasing stack for Next Greater Element
const nums = [2, 1, 2, 4, 3];
const result = new Array(nums.length).fill(-1);
const stack = []; // Stores indices whose next greater element is pending

for (let i = 0; i < nums.length; i++) {
  while (stack.length > 0 && nums[i] > nums[stack.at(-1)]) {
    const prevIndex = stack.pop();
    result[prevIndex] = nums[i]; // nums[i] is the first greater element
  }
  stack.push(i);
}

console.log(result); // [4, 2, 4, -1, -1]

Implementation #

/**
 * Resolves the Next Greater Element for each item in an array.
 * Returns an array where each position contains the next greater value, or -1 if none exists.
 * Time Complexity: O(N) | Space Complexity: O(N)
 */
function findNextGreaterElements(nums) {
  if (!Array.isArray(nums) || nums.length === 0) {
    return [];
  }

  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // Stores index positions to preserve original ordering

  for (let currentIndex = 0; currentIndex < n; currentIndex++) {
    const currentValue = nums[currentIndex];

    // Maintain monotonically decreasing stack invariant
    while (stack.length > 0 && currentValue > nums[stack.at(-1)]) {
      const targetIndex = stack.pop();
      result[targetIndex] = currentValue;
    }

    stack.push(currentIndex);
  }

  // Any remaining indices in the stack have no greater element to their right
  return result;
}

/**
 * Solves the Daily Temperatures problem:
 * Given daily temperatures, returns the number of days to wait until a warmer day.
 */
function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const daysToWait = new Array(n).fill(0);
  const stack = []; // Monotonic decreasing stack of day indices

  for (let currentDay = 0; currentDay < n; currentDay++) {
    const currentTemp = temperatures[currentDay];

    while (stack.length > 0 && currentTemp > temperatures[stack.at(-1)]) {
      const prevDay = stack.pop();
      daysToWait[prevDay] = currentDay - prevDay; // Calculate distance in days
    }

    stack.push(currentDay);
  }

  return daysToWait;
}

// Verification with duplicates and edge cases
const readings = [73, 74, 75, 71, 69, 72, 76, 73];
console.log('Next higher readings:', findNextGreaterElements(readings));
// [74, 75, 76, 72, 72, 76, -1, -1]

console.log('Days until warmer:', dailyTemperatures(readings));
// [1, 1, 4, 2, 1, 1, 0, 0]

Main Point: The monotonic stack invariant replaces quadratic lookahead scans with an optimal linear-time pattern by caching pending indices and resolving boundaries in a single pass.

Credits #

Photo by Frames For Your Heart on Unsplash

← Home