Patterns

Maintain stack in monotonic order; pop while invariant violated

When to useNext greater/smaller element, daily temperatures, largest rectangle, span problems

iterative

Monotonic Stack/Deque Intro

mono_stack_intro

Daily Temperatures

daily_temperatures

Largest Rectangle In Histogram | Monotonic Stack

largest_rectangle_in_histogram

Next Greater Element

next_greater_element_ii

Shopkeeper Sale

shopkeeper_sale

Final Discounted Price

twitter_oa_final_discounted_price

Asteroid Collisionmedium

asteroid_collision · no slots

Can See Persons Counthard

can_see_persons_count · no slots

INITIALIZE

empty stack; result array

const result = new Array(arr.length).fill(-1);
const stack = [];

const res = Array(t.length).fill(0);
const stack = [];

const stack = [];
let maxArea = 0;

const result = new Array(n).fill(-1);
const stack = [];

const result = [...prices];
const stack = [];

const result = [...prices]; const stack = [];

—

TRAVERSE

for each index in input

for (let i = 0; i < arr.length; i++) {

for (let i = 0; i < t.length; i++) {

for (let i = 0; i < heights.length; i++) {

for (let i = 0; i < n; i++) {  // pass 1: left-to-right

for (let i = 0; i < prices.length; i++) {

for (let i = 0; i < prices.length; i++) {

—

evict

while stack top violates monotonic order, pop

  while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {

  while (stack.length > 0 && t[stack[stack.length - 1]] < t[i]) {

  while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {

  while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {

  while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {

  while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {

—

[RECORD]

record result for popped index

    const j = stack.pop(); result[j] = arr[i];

    const j = stack.pop(); res[j] = i - j;

    const j = stack.pop();
    const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
    maxArea = Math.max(maxArea, heights[j] * width);

    const j = stack.pop(); result[j] = nums[i];

    const j = stack.pop(); result[j] = prices[j] - prices[i];

    const idx = stack.pop(); result[idx] = prices[idx] - prices[i];

—

push

push current index

  stack.push(i);

  stack.push(i);

  stack.push(i);

  stack.push(i);

  stack.push(i);

  stack.push(i);

—

RETURN

result derived from pop events

return result;

return res;

return maxArea;

return result;

return result;

return result.reduce((sum, p) => sum + p, 0);

—