Stacks, Monotonic Structures, And Sliding Windows

Invariant: the stack stores the exact closing brackets required by the processed prefix. Test empty string, one opener, one closer, mixed nesting, and leftover openers.

def is_valid_parentheses(s):
    closing = {"(": ")", "[": "]", "{": "}"}
    stack = []
    for ch in s:
        if ch in closing:
            stack.append(closing[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Invariant: stack indices are unresolved days, and their temperatures are decreasing. When the current temperature is warmer than the stack top, the current index resolves that older day.

def daily_temperatures(temperatures):
    answer = [0] * len(temperatures)
    stack = []
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

Invariant: the stack stores increasing bar indices. A shorter bar ends rectangles for taller bars on the stack. Common mistakes are forgetting the sentinel zero and using the wrong width after pop.

def largest_rectangle_area(heights):
    stack = []
    best = 0
    for i, height in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > height:
            h = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, h * width)
        stack.append(i)
    return best

Invariant: if window length minus the most frequent character count exceeds k, the window cannot be repaired and must shrink. The stored max frequency may be stale; it still preserves a correct best length because it only delays shrinking, never creates an impossible recorded answer.

from collections import defaultdict


def character_replacement(s, k):
    counts = defaultdict(int)
    left = 0
    best = 0
    max_count = 0

    for right, ch in enumerate(s):
        counts[ch] += 1
        max_count = max(max_count, counts[ch])
        while right - left + 1 - max_count > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)

    return best

Invariant: formed == required means every required character count is satisfied. Test repeated required characters, absent targets, target longer than source, and a best window at the beginning or end.

from collections import Counter, defaultdict


def min_window(s, t):
    need = Counter(t)
    window = defaultdict(int)
    required = len(need)
    formed = 0
    best = (float("inf"), 0, 0)
    left = 0

    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            formed += 1

        while formed == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            drop = s[left]
            window[drop] -= 1
            if drop in need and window[drop] < need[drop]:
                formed -= 1
            left += 1

    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

Invariant: every stack frame stores the prefix before a bracket and the repeat count for that bracket. On close, the completed fragment is appended back to the previous prefix. Common mistakes are failing multi-digit counts and losing nested prefixes.

def decode_string(s):
    stack = []
    current = []
    number = 0

    for ch in s:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == "[":
            stack.append(("".join(current), number))
            current = []
            number = 0
        elif ch == "]":
            prefix, repeat = stack.pop()
            current = [prefix + "".join(current) * repeat]
        else:
            current.append(ch)

    return "".join(current)

Clarify whether ignored minutes are removed from the denominator or tolerated as exceptions. If the rule is exception-based, use a sliding window over minutes whose age is above threshold and shrink when exceptions exceed k. Connect the result to ASR or TTS backlog alerts and rollout freeze decisions.

Use a stack for brackets and braces, track string and escape state, and avoid executing tools from partial text. A strong answer adds a timeout, maximum nesting, schema validation, confirmation for sensitive actions, and logging that never stores raw private audio.

The algorithm records a maximum length only after expanding. A stale max can make the window appear valid longer than it truly is, but it cannot cause a too-large answer because the stale value came from a real earlier window with that frequency. It is a proof about preserving best length, not a claim that every intermediate window is valid.

Use a stack when nested structure or last-unresolved state matters, such as parsing partial tool calls or bracketed markup. Use a sliding window when the metric is over a contiguous time range, such as churn rate over the last five seconds or rollback alerts over the latest canary minutes.