Monotonic Stack — Equal-Price Operator Off-by-One

from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    """
    For each element, find the next strictly greater element to its right.
    Returns -1 if none exists.

    Approach: monotonic decreasing stack of indices.
    When a new element is greater than the stack top, the top has found its answer.

    Time:  O(n) — each element pushed/popped at most once
    Space: O(n) — stack + result array
    """
    n = len(nums)
    result = [-1] * n
    stack = []          # indices, maintained in decreasing order of nums[index]

    for i in range(n):
        # While current element beats the stack top:
        # the top's 'next greater' is nums[i]
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    # Remaining indices in stack → no greater element → stay -1

    return result


print(next_greater_element([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]
# Trace:
# i=0: push 0. stack=[0]  (val=2)
# i=1: 1<2 → push 1. stack=[0,1]
# i=2: 2>1 → pop 1, result[1]=2. 2==2 → push 2. stack=[0,2]
# i=3: 4>2 → pop 2, result[2]=4. 4>2 → pop 0, result[0]=4. push 3. stack=[3]
# i=4: 3<4 → push 4. stack=[3,4]
# End: indices 3,4 remain → result[3]=result[4]=-1


def stock_span(prices: List[int]) -> List[int]:
    """
    Stock Span: for each day, how many consecutive previous days
    (including today) had price <= today's price?

    Monotonic decreasing stack of (index, price) pairs.
    Time: O(n), Space: O(n)
    """
    span = [0] * len(prices)
    stack = []   # (index, price) in decreasing price order

    for i, price in enumerate(prices):
        while stack and price >= stack[-1][1]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1][0]
        stack.append((i, price))

    return span

print(stock_span([100, 80, 60, 70, 60, 75, 85]))
# [1, 1, 1, 2, 1, 4, 6]

from typing import List

def next_smaller_element(nums: List[int]) -> List[int]:
    """
    Monotonic INCREASING stack.
    For each element, find the next strictly smaller element to its right.
    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []   # indices in increasing order of nums[index]

    for i in range(n):
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

print(next_smaller_element([4, 2, 3, 1, 5]))
# [2, 1, 1, -1, -1]


def largest_rectangle_histogram(heights: List[int]) -> int:
    """
    Largest rectangle in histogram.
    Classic monotonic increasing stack problem.
    Time: O(n), Space: O(n)

    Key insight: when we pop a bar because the current bar is shorter,
    we know the FULL width that popped bar can extend to.
    """
    max_area = 0
    stack = []   # (start_index, height) — monotonic increasing by height
    heights = heights + [0]   # sentinel 0 forces all remaining bars to pop

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            width    = i - idx
            max_area = max(max_area, height * width)
            start    = idx   # This bar can extend back to where the popped bar started
        stack.append((start, h))

    return max_area

print(largest_rectangle_histogram([2, 1, 5, 6, 2, 3]))
# 10  (bars of height 5 and 6 form a 2-wide × 5-tall = 10 rectangle)

def trap(heights: List[int]) -> int:
    """
    Trapping rain water using monotonic decreasing stack.
    Time: O(n), Space: O(n)
    """
    water = 0
    stack = []  # indices, decreasing heights
    for i, h in enumerate(heights):
        while stack and h > heights[stack[-1]]:
            bottom_idx = stack.pop()
            if not stack:
                break
            left_idx = stack[-1]
            width = i - left_idx - 1
            height = min(heights[left_idx], h) - heights[bottom_idx]
            water += width * height
        stack.append(i)
    return water

def debug_nge(nums):
    n, res = len(nums), [-1]*len(nums)
    stack = []
    for i in range(n):
        print(f'i={i}, val={nums[i]}, stack_before={stack}')
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]
            print(f'  pop {idx}, set res[{idx}]={nums[i]}, stack={stack}')
        stack.append(i)
        print(f'  push {i}, stack_after={stack}')
    print(f'final res: {res}')
    return res

debug_nge([2,1,2,4,3])