Stack

def cal_points(operations: list[str]) -> int:
    """LC 682. Baseball Game.

    Simulate the scorecard with a stack of scores: a number pushes, 'C'
    pops, 'D' doubles the top, and '+' pushes the sum of the top two
    without removing them. The answer is the sum of whatever remains.
    O(n) time, O(n) space.
    """
    record: list[int] = []
    for op in operations:
        if op == "C":
            record.pop()
        elif op == "D":
            record.append(record[-1] * 2)
        elif op == "+":
            record.append(record[-1] + record[-2])
        else:
            record.append(int(op))
    return sum(record)

// LC 682. Simulate the scoreboard with a stack; '+' peeks the top two scores
// without removing them, and the answer is the sum of whatever remains.
int calPoints(vector<string> operations) {
    vector<int> record;
    for (const string& op : operations) {
        if (op == "+") record.push_back(record[record.size() - 1] + record[record.size() - 2]);
        else if (op == "D") record.push_back(2 * record.back());
        else if (op == "C") record.pop_back();
        else record.push_back(stoi(op));
    }
    int total = 0;
    for (int score : record) total += score;
    return total;
}

/// LC 682. Simulate the scorecard with a stack: numbers push, 'C' pops,
/// 'D' doubles the top, and '+' sums the top two WITHOUT removing them.
/// The answer is the sum of whatever remains.
pub fn cal_points(operations: Vec<String>) -> i32 {
    let mut record: Vec<i32> = Vec::new();
    for op in &operations {
        match op.as_str() {
            "+" => record.push(record[record.len() - 1] + record[record.len() - 2]),
            "D" => record.push(record.last().unwrap() * 2),
            "C" => {
                record.pop();
            }
            num => record.push(num.parse().unwrap()),
        }
    }
    record.iter().sum()
}

/** LC 682. Stack of scores: 'C' pops, 'D' doubles the top, '+' reads the top two. */
export function calPoints(operations: string[]): number {
  const record: number[] = [];
  for (const op of operations) {
    if (op === "C") record.pop();
    else if (op === "D") record.push(2 * record[record.length - 1]);
    else if (op === "+") record.push(record[record.length - 1] + record[record.length - 2]);
    else record.push(Number(op));
  }
  return record.reduce((total, score) => total + score, 0);
}

// LC 682. Simulate the scoreboard with a stack; '+' peeks the top two scores
// without removing them, and the answer is the sum of whatever remains.
func calPoints(operations []string) int {
	record := []int{}
	for _, op := range operations {
		switch op {
		case "+":
			record = append(record, record[len(record)-1]+record[len(record)-2])
		case "D":
			record = append(record, 2*record[len(record)-1])
		case "C":
			record = record[:len(record)-1]
		default:
			score, _ := strconv.Atoi(op)
			record = append(record, score)
		}
	}
	total := 0
	for _, score := range record {
		total += score
	}
	return total
}

// LC 682. Simulate the scoreboard with a stack; '+' peeks the top two scores
// without removing them, and the answer is the sum of whatever remains.
func calPoints(_ operations: [String]) -> Int {
    var record: [Int] = []
    for op in operations {
        if op == "+" {
            record.append(record[record.count - 1] + record[record.count - 2])
        } else if op == "D" {
            record.append(2 * record.last!)
        } else if op == "C" {
            record.removeLast()
        } else {
            record.append(Int(op)!)
        }
    }
    return record.reduce(0, +)
}

def is_valid_parentheses(s: str) -> bool:
    """LC 20. Valid Parentheses.

    Push every opener; each closer must find its matching opener on top
    of the stack, then pop it. A closer arriving on an empty stack and
    leftover openers at the end are the two classic pitfalls -- both
    invalidate. O(n) time, O(n) space.
    """
    matching_opener = {")": "(", "]": "[", "}": "{"}
    openers: list[str] = []
    for ch in s:
        if ch in matching_opener:
            # a closer needs a nonempty stack AND the right opener on top
            if not openers or openers[-1] != matching_opener[ch]:
                return False
            openers.pop()
        else:
            openers.append(ch)
    return not openers  # leftover openers mean unclosed brackets

// LC 20. Push openers; each closer must match the top of the stack, and the
// stack must finish empty (leftover openers are also invalid).
bool isValidParentheses(string s) {
    vector<char> openers;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            openers.push_back(ch);
        } else {
            char wanted = ch == ')' ? '(' : ch == ']' ? '[' : '{';
            if (openers.empty() || openers.back() != wanted) return false;
            openers.pop_back();
        }
    }
    return openers.empty();
}

/// LC 20. Push openers; each closer must match the popped top. A closer on
/// an empty stack pops None and fails the match, and leftover openers fail
/// the final emptiness check -- the two classic pitfalls.
pub fn is_valid_parentheses(s: String) -> bool {
    let mut openers = Vec::new();
    for ch in s.chars() {
        match ch {
            '(' | '[' | '{' => openers.push(ch),
            ')' if openers.pop() != Some('(') => return false,
            ']' if openers.pop() != Some('[') => return false,
            '}' if openers.pop() != Some('{') => return false,
            _ => {}
        }
    }
    openers.is_empty()
}

/** LC 20. Push openers; each closer must match the top, and the stack must end empty. */
export function isValidParentheses(s: string): boolean {
  const openerFor: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const openers: string[] = [];
  for (const ch of s) {
    const opener = openerFor[ch];
    if (opener === undefined) openers.push(ch);
    else if (openers.pop() !== opener) return false; // an empty stack pops undefined, failing too
  }
  return openers.length === 0; // leftover openers were never closed
}

// LC 20. Push openers; each closer must match the top of the stack, and the
// stack must finish empty (leftover openers are also invalid).
func isValidParentheses(s string) bool {
	openers := []byte{}
	for i := 0; i < len(s); i++ {
		ch := s[i]
		if ch == '(' || ch == '[' || ch == '{' {
			openers = append(openers, ch)
			continue
		}
		wanted := byte('{')
		if ch == ')' {
			wanted = '('
		} else if ch == ']' {
			wanted = '['
		}
		if len(openers) == 0 || openers[len(openers)-1] != wanted {
			return false
		}
		openers = openers[:len(openers)-1]
	}
	return len(openers) == 0
}

// LC 20. Push openers; each closer must match the top of the stack, and the
// stack must finish empty (leftover openers are also invalid).
func isValidParentheses(_ s: String) -> Bool {
    let matchingOpener: [Character: Character] = [")": "(", "]": "[", "}": "{"]
    var openers: [Character] = []
    for ch in s {
        if let wanted = matchingOpener[ch] {
            if openers.isEmpty || openers.last! != wanted { return false }
            openers.removeLast()
        } else {
            openers.append(ch)
        }
    }
    return openers.isEmpty
}

class MyStack:
    """LC 225. Implement Stack using Queues.

    One queue: after enqueueing a new element, rotate the older elements
    around behind it so the newest sits at the front. That makes push
    O(n) while pop, top, and empty are plain O(1) queue operations.
    """

    def __init__(self) -> None:
        self._queue: deque[int] = deque()

    def push(self, x: int) -> None:
        self._queue.append(x)
        for _ in range(len(self._queue) - 1):  # rotate the n - 1 older elements behind x
            self._queue.append(self._queue.popleft())

    def pop(self) -> int:
        return self._queue.popleft()

    def top(self) -> int:
        return self._queue[0]

    def empty(self) -> bool:
        return not self._queue

// LC 225. One queue: after enqueueing, rotate every older element behind the
// newcomer so the queue front is always the stack top. push O(n), rest O(1).
class MyStack {
    queue<int> rotated;

   public:
    void push(int x) {
        rotated.push(x);
        for (size_t i = 1; i < rotated.size(); ++i) {  // move all older elements behind x
            rotated.push(rotated.front());
            rotated.pop();
        }
    }
    int pop() {
        int topValue = rotated.front();
        rotated.pop();
        return topValue;
    }
    int top() { return rotated.front(); }
    bool empty() { return rotated.empty(); }
};

/// LC 225. One VecDeque as the queue: after each push, rotate the older
/// elements behind the newcomer so the newest sits at the front. Push is
/// O(n); pop, top, and empty become plain O(1) queue operations.
pub struct MyStack {
    queue: VecDeque<i32>,
}

impl MyStack {
    pub fn new() -> Self {
        MyStack { queue: VecDeque::new() }
    }

    pub fn push(&mut self, x: i32) {
        self.queue.push_back(x);
        // Rotate every older element behind x; now the queue front is the stack top.
        for _ in 1..self.queue.len() {
            let older = self.queue.pop_front().unwrap();
            self.queue.push_back(older);
        }
    }

    pub fn pop(&mut self) -> i32 {
        self.queue.pop_front().unwrap()
    }

    pub fn top(&self) -> i32 {
        *self.queue.front().unwrap()
    }

    pub fn empty(&self) -> bool {
        self.queue.is_empty()
    }
}

/** LC 225. One array-queue: rotate the older elements behind each new push, so the newest fronts the queue. */
export class MyStack {
  private queue: number[] = [];

  push(x: number): void {
    this.queue.push(x);
    // rotate every older element behind the newcomer; the queue front is now the stack top
    for (let older = 1; older < this.queue.length; older++) {
      this.queue.push(this.queue.shift()!);
    }
  }

  pop(): number {
    return this.queue.shift()!;
  }

  top(): number {
    return this.queue[0];
  }

  empty(): boolean {
    return this.queue.length === 0;
  }
}

// LC 225. One queue: after enqueueing, rotate every older element behind the
// newcomer so the queue front is always the stack top. push O(n), rest O(1).
type MyStack struct {
	rotated []int
}

func newMyStack() *MyStack {
	return &MyStack{}
}

func (s *MyStack) push(x int) {
	s.rotated = append(s.rotated, x)
	for i := 1; i < len(s.rotated); i++ { // move all older elements behind x
		s.rotated = append(s.rotated, s.rotated[0])
		s.rotated = s.rotated[1:]
	}
}

func (s *MyStack) pop() int {
	topValue := s.rotated[0]
	s.rotated = s.rotated[1:]
	return topValue
}

func (s *MyStack) top() int {
	return s.rotated[0]
}

func (s *MyStack) empty() bool {
	return len(s.rotated) == 0
}

// LC 225. One queue: after enqueueing, rotate every older element behind the
// newcomer so the queue front is always the stack top. push O(n), rest O(1).
class MyStack {
    var rotated: [Int] = []

    func push(_ x: Int) {
        rotated.append(x)
        for _ in 1..<rotated.count {  // move all older elements behind x
            rotated.append(rotated.removeFirst())
        }
    }
    func pop() -> Int { return rotated.removeFirst() }
    func top() -> Int { return rotated[0] }
    func empty() -> Bool { return rotated.isEmpty }
}

class MyQueue:
    """LC 232. Implement Queue using Stacks.

    Two stacks: push always lands on the in-stack; when the out-stack
    runs dry, pour the entire in-stack into it, which reverses order so
    the oldest element surfaces on top. Each element moves between
    stacks at most once, so every operation is amortized O(1) even
    though a single pop can be O(n).
    """

    def __init__(self) -> None:
        self._inbox: list[int] = []
        self._outbox: list[int] = []

    def push(self, x: int) -> None:
        self._inbox.append(x)

    def pop(self) -> int:
        self.peek()
        return self._outbox.pop()

    def peek(self) -> int:
        if not self._outbox:  # pour only when dry; pouring early would scramble order
            while self._inbox:
                self._outbox.append(self._inbox.pop())
        return self._outbox[-1]

    def empty(self) -> bool:
        return not self._inbox and not self._outbox

// LC 232. Push onto inStack; when outStack runs dry, pour inStack into it,
// which reverses order so the oldest element surfaces. Each element moves
// between stacks at most once, so everything is amortized O(1).
class MyQueue {
    vector<int> inStack, outStack;

    void pourIfNeeded() {
        if (!outStack.empty()) return;
        while (!inStack.empty()) {
            outStack.push_back(inStack.back());
            inStack.pop_back();
        }
    }

   public:
    void push(int x) { inStack.push_back(x); }
    int pop() {
        pourIfNeeded();
        int frontValue = outStack.back();
        outStack.pop_back();
        return frontValue;
    }
    int peek() {
        pourIfNeeded();
        return outStack.back();
    }
    bool empty() { return inStack.empty() && outStack.empty(); }
};

/// LC 232. Two Vec stacks: push lands on inbox; pop and peek serve from
/// outbox, pouring the whole inbox into it (which reverses the order, so
/// the oldest surfaces) only when outbox runs dry. Each element moves
/// between stacks at most once, so every operation is amortized O(1).
pub struct MyQueue {
    inbox: Vec<i32>,
    outbox: Vec<i32>,
}

impl MyQueue {
    pub fn new() -> Self {
        MyQueue { inbox: Vec::new(), outbox: Vec::new() }
    }

    pub fn push(&mut self, x: i32) {
        self.inbox.push(x);
    }

    fn refill_outbox(&mut self) {
        if self.outbox.is_empty() {
            while let Some(value) = self.inbox.pop() {
                self.outbox.push(value);
            }
        }
    }

    pub fn pop(&mut self) -> i32 {
        self.refill_outbox();
        self.outbox.pop().unwrap()
    }

    pub fn peek(&mut self) -> i32 {
        self.refill_outbox();
        *self.outbox.last().unwrap()
    }

    pub fn empty(&self) -> bool {
        self.inbox.is_empty() && self.outbox.is_empty()
    }
}

/** LC 232. Two stacks: pour inbox into outbox only when outbox runs dry, so each element moves once. */
export class MyQueue {
  private inbox: number[] = [];
  private outbox: number[] = [];

  push(x: number): void {
    this.inbox.push(x);
  }

  pop(): number {
    this.peek(); // guarantees the oldest element sits on top of outbox
    return this.outbox.pop()!;
  }

  peek(): number {
    if (this.outbox.length === 0) {
      // pouring reverses the inbox, surfacing the oldest element
      while (this.inbox.length > 0) this.outbox.push(this.inbox.pop()!);
    }
    return this.outbox[this.outbox.length - 1];
  }

  empty(): boolean {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }
}

// LC 232. Push onto inStack; when outStack runs dry, pour inStack into it,
// which reverses order so the oldest element surfaces. Each element moves
// between stacks at most once, so everything is amortized O(1).
type MyQueue struct {
	inStack  []int
	outStack []int
}

func newMyQueue() *MyQueue {
	return &MyQueue{}
}

func (q *MyQueue) push(x int) {
	q.inStack = append(q.inStack, x)
}

func (q *MyQueue) pop() int {
	frontValue := q.peek()
	q.outStack = q.outStack[:len(q.outStack)-1]
	return frontValue
}

func (q *MyQueue) peek() int {
	if len(q.outStack) == 0 { // pour only when dry; pouring early would scramble order
		for len(q.inStack) > 0 {
			q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
			q.inStack = q.inStack[:len(q.inStack)-1]
		}
	}
	return q.outStack[len(q.outStack)-1]
}

func (q *MyQueue) empty() bool {
	return len(q.inStack) == 0 && len(q.outStack) == 0
}

// LC 232. Push onto inStack; when outStack runs dry, pour inStack into it,
// which reverses order so the oldest element surfaces. Each element moves
// between stacks at most once, so everything is amortized O(1).
class MyQueue {
    var inStack: [Int] = []
    var outStack: [Int] = []

    func pourIfNeeded() {
        if !outStack.isEmpty { return }
        while let moved = inStack.popLast() { outStack.append(moved) }
    }
    func push(_ x: Int) { inStack.append(x) }
    func pop() -> Int {
        pourIfNeeded()
        return outStack.removeLast()
    }
    func peek() -> Int {
        pourIfNeeded()
        return outStack.last!
    }
    func empty() -> Bool { return inStack.isEmpty && outStack.isEmpty }
}

class MinStack:
    """LC 155. Min Stack.

    Each entry stores a (value, min_at_depth) pair: the minimum of the
    whole stack at the moment of that push. Popping automatically
    restores the previous minimum with no recomputation. All four
    operations O(1), O(n) space.
    """

    def __init__(self) -> None:
        self._entries: list[tuple[int, int]] = []

    def push(self, val: int) -> None:
        min_at_depth = min(val, self._entries[-1][1]) if self._entries else val
        self._entries.append((val, min_at_depth))

    def pop(self) -> None:
        self._entries.pop()

    def top(self) -> int:
        return self._entries[-1][0]

    def get_min(self) -> int:
        return self._entries[-1][1]

// LC 155. Each entry snapshots (value, minAtDepth): the stack minimum at that
// depth, so popping restores the previous minimum with no recomputation.
class MinStack {
    vector<pair<int, int>> entries;  // (value, minAtDepth)

   public:
    void push(int val) {
        int minAtDepth = entries.empty() ? val : min(val, entries.back().second);
        entries.push_back({val, minAtDepth});
    }
    void pop() { entries.pop_back(); }
    int top() { return entries.back().first; }
    int getMin() { return entries.back().second; }
};

/// LC 155. Each entry stores (value, min_at_depth): a snapshot of the
/// stack's minimum at that depth. Popping automatically restores the
/// previous minimum with no recomputation, so all four operations are O(1).
pub struct MinStack {
    entries: Vec<(i32, i32)>,
}

impl MinStack {
    pub fn new() -> Self {
        MinStack { entries: Vec::new() }
    }

    pub fn push(&mut self, val: i32) {
        let min_at_depth = self.entries.last().map_or(val, |&(_, min)| min.min(val));
        self.entries.push((val, min_at_depth));
    }

    pub fn pop(&mut self) {
        self.entries.pop();
    }

    pub fn top(&self) -> i32 {
        self.entries.last().unwrap().0
    }

    pub fn get_min(&self) -> i32 {
        self.entries.last().unwrap().1
    }
}

/** LC 155. Each entry snapshots [value, minAtDepth]; popping restores the previous minimum for free. */
export class MinStack {
  private entries: [number, number][] = [];

  push(val: number): void {
    const minAtDepth = this.entries.length === 0 ? val : Math.min(val, this.getMin());
    this.entries.push([val, minAtDepth]);
  }

  pop(): void {
    this.entries.pop();
  }

  top(): number {
    return this.entries[this.entries.length - 1][0];
  }

  getMin(): number {
    return this.entries[this.entries.length - 1][1];
  }
}

// LC 155. Each entry snapshots (value, minAtDepth): the stack minimum at that
// depth, so popping restores the previous minimum with no recomputation.
type MinStack struct {
	entries [][2]int // (value, minAtDepth)
}

func newMinStack() *MinStack {
	return &MinStack{}
}

func (s *MinStack) push(val int) {
	minAtDepth := val
	if len(s.entries) > 0 && s.entries[len(s.entries)-1][1] < val {
		minAtDepth = s.entries[len(s.entries)-1][1]
	}
	s.entries = append(s.entries, [2]int{val, minAtDepth})
}

func (s *MinStack) pop() {
	s.entries = s.entries[:len(s.entries)-1]
}

func (s *MinStack) top() int {
	return s.entries[len(s.entries)-1][0]
}

func (s *MinStack) getMin() int {
	return s.entries[len(s.entries)-1][1]
}

// LC 155. Each entry snapshots (value, minAtDepth): the stack minimum at that
// depth, so popping restores the previous minimum with no recomputation.
class MinStack {
    var entries: [(value: Int, minAtDepth: Int)] = []

    func push(_ val: Int) {
        let minAtDepth = entries.isEmpty ? val : min(val, entries.last!.minAtDepth)
        entries.append((val, minAtDepth))
    }
    func pop() { entries.removeLast() }
    func top() -> Int { return entries.last!.value }
    func getMin() -> Int { return entries.last!.minAtDepth }
}

def eval_rpn(tokens: list[str]) -> int:
    """LC 150. Evaluate Reverse Polish Notation.

    Push numbers onto a stack; on each operator pop two values, apply,
    and push the result. Operand order is the classic slip: the first
    pop is the RIGHT operand, which matters for subtraction and
    division. O(n) time, O(n) space.
    """
    operands: list[int] = []
    for token in tokens:
        if token in ("+", "-", "*", "/"):
            right = operands.pop()  # first pop is the RIGHT operand
            left = operands.pop()
            if token == "+":
                operands.append(left + right)
            elif token == "-":
                operands.append(left - right)
            elif token == "*":
                operands.append(left * right)
            else:
                # int(a / b), not a // b: LC truncates toward zero, but Python
                # floor-divides, so 6 // -132 would give -1 instead of 0.
                operands.append(int(left / right))
        else:
            operands.append(int(token))
    return operands[0]

// LC 150. Stack of operands; on an operator, the FIRST pop is the right
// operand, which matters for '-' and '/'. The problem wants division
// truncated toward zero, and C++ integer division already does exactly that.
int evalRPN(vector<string> tokens) {
    vector<long long> operands;
    for (const string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            long long right = operands.back();  // first pop is the right operand
            operands.pop_back();
            long long left = operands.back();
            operands.pop_back();
            if (token == "+") operands.push_back(left + right);
            else if (token == "-") operands.push_back(left - right);
            else if (token == "*") operands.push_back(left * right);
            else operands.push_back(left / right);  // truncates toward zero, as required
        } else {
            operands.push_back(stoll(token));
        }
    }
    return static_cast<int>(operands.back());
}

/// LC 150. Push numbers; each operator pops two and pushes the result.
/// The first pop is the RIGHT operand -- the order matters for - and /.
/// Rust's integer `/` already truncates toward zero, exactly as required.
pub fn eval_rpn(tokens: Vec<String>) -> i32 {
    let mut operands: Vec<i32> = Vec::new();
    for token in &tokens {
        match token.as_str() {
            "+" | "-" | "*" | "/" => {
                let right = operands.pop().unwrap();
                let left = operands.pop().unwrap();
                operands.push(match token.as_str() {
                    "+" => left + right,
                    "-" => left - right,
                    "*" => left * right,
                    _ => left / right,
                });
            }
            num => operands.push(num.parse().unwrap()),
        }
    }
    operands[0]
}

/** LC 150. Push numbers; each operator pops right then left, and division truncates toward zero. */
export function evalRPN(tokens: string[]): number {
  const operands: number[] = [];
  for (const token of tokens) {
    if (token === "+" || token === "-" || token === "*" || token === "/") {
      const right = operands.pop()!; // first pop is the RIGHT operand
      const left = operands.pop()!;
      if (token === "+") operands.push(left + right);
      else if (token === "-") operands.push(left - right);
      else if (token === "*") operands.push(left * right);
      else operands.push(Math.trunc(left / right)); // trunc, not floor: LC division rounds toward zero
    } else {
      operands.push(Number(token));
    }
  }
  return operands[0];
}

// LC 150. Stack of operands; on an operator, the FIRST pop is the right
// operand, which matters for '-' and '/'. The problem wants division
// truncated toward zero, and Go integer division already does exactly that.
func evalRPN(tokens []string) int {
	operands := []int{}
	for _, token := range tokens {
		switch token {
		case "+", "-", "*", "/":
			right := operands[len(operands)-1] // first pop is the right operand
			left := operands[len(operands)-2]
			operands = operands[:len(operands)-2]
			switch token {
			case "+":
				operands = append(operands, left+right)
			case "-":
				operands = append(operands, left-right)
			case "*":
				operands = append(operands, left*right)
			default:
				operands = append(operands, left/right) // truncates toward zero, as required
			}
		default:
			value, _ := strconv.Atoi(token)
			operands = append(operands, value)
		}
	}
	return operands[len(operands)-1]
}

// LC 150. Stack of operands; on an operator, the FIRST pop is the right
// operand, which matters for '-' and '/'. The problem wants division
// truncated toward zero, and Swift integer division already does exactly that.
func evalRPN(_ tokens: [String]) -> Int {
    var operands: [Int] = []
    for token in tokens {
        if token == "+" || token == "-" || token == "*" || token == "/" {
            let right = operands.removeLast()  // first pop is the right operand
            let left = operands.removeLast()
            if token == "+" { operands.append(left + right) }
            else if token == "-" { operands.append(left - right) }
            else if token == "*" { operands.append(left * right) }
            else { operands.append(left / right) }  // truncates toward zero, as required
        } else {
            operands.append(Int(token)!)
        }
    }
    return operands.last!
}

def asteroid_collision(asteroids: list[int]) -> list[int]:
    """LC 735. Asteroid Collision.

    Only a right-mover already on the stack can collide with an
    incoming left-mover. The left-mover pops every strictly smaller
    right-mover, destroys both on a tie, and dies against a larger top;
    with no opposing top it survives and is pushed. O(n) time, O(n)
    space.
    """
    survivors: list[int] = []
    for asteroid in asteroids:
        alive = True
        # collision requires top moving right (> 0) AND newcomer moving left (< 0)
        while alive and asteroid < 0 and survivors and survivors[-1] > 0:
            if survivors[-1] < -asteroid:
                survivors.pop()  # smaller right-mover explodes; keep checking the next top
            elif survivors[-1] == -asteroid:
                survivors.pop()  # equal sizes: both explode
                alive = False
            else:
                alive = False  # larger right-mover survives; the newcomer explodes
        if alive:
            survivors.append(asteroid)
    return survivors

// LC 735. Only a right-moving top vs a left-moving newcomer collides: pop
// strictly smaller right-movers, explode both on a tie, drop a smaller
// newcomer. Everything else just pushes.
vector<int> asteroidCollision(vector<int> asteroids) {
    vector<int> survivors;
    for (int asteroid : asteroids) {
        bool alive = true;
        while (alive && asteroid < 0 && !survivors.empty() && survivors.back() > 0) {
            if (survivors.back() < -asteroid) survivors.pop_back();  // top explodes, keep checking
            else if (survivors.back() == -asteroid) {
                survivors.pop_back();  // equal sizes: both explode
                alive = false;
            } else {
                alive = false;  // larger top: newcomer explodes
            }
        }
        if (alive) survivors.push_back(asteroid);
    }
    return survivors;
}

/// LC 735. Only a right-mover already on the stack collides with an
/// incoming left-mover. Pop strictly smaller right-movers, pop both on an
/// equal-size meeting, and drop the newcomer when the top is bigger;
/// everything else just pushes.
pub fn asteroid_collision(asteroids: Vec<i32>) -> Vec<i32> {
    let mut survivors: Vec<i32> = Vec::new();
    for incoming in asteroids {
        let mut incoming_alive = true;
        // Collisions only happen while a right-mover tops the stack and the newcomer moves left.
        while incoming_alive && incoming < 0 && survivors.last().map_or(false, |&top| top > 0) {
            let top = *survivors.last().unwrap();
            if top < -incoming {
                survivors.pop();
            } else {
                if top == -incoming {
                    survivors.pop(); // equal sizes: both explode
                }
                incoming_alive = false;
            }
        }
        if incoming_alive {
            survivors.push(incoming);
        }
    }
    survivors
}

/** LC 735. Stack of survivors: a left-mover pops smaller right-movers; equal sizes destroy both. */
export function asteroidCollision(asteroids: number[]): number[] {
  const survivors: number[] = [];
  for (const asteroid of asteroids) {
    let alive = true;
    // only a right-moving top meeting a left-moving newcomer collides
    while (alive && asteroid < 0 && survivors.length > 0 && survivors[survivors.length - 1] > 0) {
      const top = survivors[survivors.length - 1];
      if (top < -asteroid) {
        survivors.pop(); // smaller right-mover explodes; keep checking the next top
      } else {
        if (top === -asteroid) survivors.pop(); // equal sizes: both explode
        alive = false;
      }
    }
    if (alive) survivors.push(asteroid);
  }
  return survivors;
}

// LC 735. Only a right-moving top vs a left-moving newcomer collides: pop
// strictly smaller right-movers, explode both on a tie, drop a smaller
// newcomer. Everything else just pushes.
func asteroidCollision(asteroids []int) []int {
	survivors := []int{}
	for _, asteroid := range asteroids {
		alive := true
		for alive && asteroid < 0 && len(survivors) > 0 && survivors[len(survivors)-1] > 0 {
			if survivors[len(survivors)-1] < -asteroid {
				survivors = survivors[:len(survivors)-1] // top explodes, keep checking
			} else if survivors[len(survivors)-1] == -asteroid {
				survivors = survivors[:len(survivors)-1] // equal sizes: both explode
				alive = false
			} else {
				alive = false // larger top: newcomer explodes
			}
		}
		if alive {
			survivors = append(survivors, asteroid)
		}
	}
	return survivors
}

// LC 735. Only a right-moving top vs a left-moving newcomer collides: pop
// strictly smaller right-movers, explode both on a tie, drop a smaller
// newcomer. Everything else just pushes.
func asteroidCollision(_ asteroids: [Int]) -> [Int] {
    var survivors: [Int] = []
    for asteroid in asteroids {
        var alive = true
        while alive && asteroid < 0 && !survivors.isEmpty && survivors.last! > 0 {
            if survivors.last! < -asteroid {
                survivors.removeLast()  // top explodes, keep checking
            } else if survivors.last! == -asteroid {
                survivors.removeLast()  // equal sizes: both explode
                alive = false
            } else {
                alive = false  // larger top: newcomer explodes
            }
        }
        if alive { survivors.append(asteroid) }
    }
    return survivors
}

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """LC 739. Daily Temperatures.

    Keep a stack of indices still waiting for a warmer day, their
    temperatures decreasing from bottom to top. Pushing indices rather
    than temperatures is the point: the answer is a distance. Each
    index is pushed and popped at most once. O(n) time, O(n) space.
    """
    answers = [0] * len(temperatures)
    unresolved_indices: list[int] = []
    for today, temperature in enumerate(temperatures):
        # today is the first warmer day for every colder index on the stack
        while unresolved_indices and temperatures[unresolved_indices[-1]] < temperature:
            colder_day = unresolved_indices.pop()
            answers[colder_day] = today - colder_day
        unresolved_indices.append(today)
    return answers

// LC 739. Stack of indices still waiting for a warmer day, temperatures
// decreasing top-down; a warmer day resolves every colder index it beats.
// Indices, not temperatures, because the answer is a distance.
vector<int> dailyTemperatures(vector<int> temperatures) {
    int n = static_cast<int>(temperatures.size());
    vector<int> answer(n, 0);
    vector<int> unresolvedIndices;
    for (int day = 0; day < n; ++day) {
        while (!unresolvedIndices.empty() && temperatures[unresolvedIndices.back()] < temperatures[day]) {
            answer[unresolvedIndices.back()] = day - unresolvedIndices.back();  // days waited
            unresolvedIndices.pop_back();
        }
        unresolvedIndices.push_back(day);
    }
    return answer;
}

/// LC 739. Monotonic stack of INDICES with decreasing temperatures: a
/// warmer day pops every colder index, and the answer is the index gap
/// (indices, not temperatures, because the answer is a distance). Each
/// index is pushed and popped at most once: O(n).
pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let mut answers = vec![0; temperatures.len()];
    let mut unresolved_indices: Vec<usize> = Vec::new();
    for (today, &temp) in temperatures.iter().enumerate() {
        while unresolved_indices.last().map_or(false, |&day| temperatures[day] < temp) {
            let colder_day = unresolved_indices.pop().unwrap();
            answers[colder_day] = (today - colder_day) as i32;
        }
        unresolved_indices.push(today);
    }
    answers
}

/** LC 739. Monotonic stack of indices with non-increasing temps; a warmer day resolves pops by distance. */
export function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array<number>(temperatures.length).fill(0);
  const unresolvedIndices: number[] = []; // temperatures at these indices only ever decrease
  for (let day = 0; day < temperatures.length; day++) {
    while (
      unresolvedIndices.length > 0 &&
      temperatures[unresolvedIndices[unresolvedIndices.length - 1]] < temperatures[day]
    ) {
      const resolved = unresolvedIndices.pop()!;
      answer[resolved] = day - resolved; // the answer is a distance, hence indices on the stack
    }
    unresolvedIndices.push(day);
  }
  return answer;
}

// LC 739. Stack of indices still waiting for a warmer day, temperatures
// decreasing top-down; a warmer day resolves every colder index it beats.
// Indices, not temperatures, because the answer is a distance.
func dailyTemperatures(temperatures []int) []int {
	answer := make([]int, len(temperatures))
	unresolvedIndices := []int{}
	for day, temperature := range temperatures {
		for len(unresolvedIndices) > 0 && temperatures[unresolvedIndices[len(unresolvedIndices)-1]] < temperature {
			colderDay := unresolvedIndices[len(unresolvedIndices)-1]
			answer[colderDay] = day - colderDay // days waited
			unresolvedIndices = unresolvedIndices[:len(unresolvedIndices)-1]
		}
		unresolvedIndices = append(unresolvedIndices, day)
	}
	return answer
}

// LC 739. Stack of indices still waiting for a warmer day, temperatures
// decreasing top-down; a warmer day resolves every colder index it beats.
// Indices, not temperatures, because the answer is a distance.
func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    var answer = [Int](repeating: 0, count: temperatures.count)
    var unresolvedIndices: [Int] = []
    for day in 0..<temperatures.count {
        while let colderDay = unresolvedIndices.last, temperatures[colderDay] < temperatures[day] {
            answer[colderDay] = day - colderDay  // days waited
            unresolvedIndices.removeLast()
        }
        unresolvedIndices.append(day)
    }
    return answer
}

class StockSpanner:
    """LC 901. Online Stock Span.

    Monotonic stack of (price, span) pairs. Each new price pops every
    pair priced at or below it and absorbs their spans, so a popped run
    collapses into a single entry and is never re-examined. Amortized
    O(1) per call, O(n) space.
    """

    def __init__(self) -> None:
        self._price_spans: list[tuple[int, int]] = []

    def next(self, price: int) -> int:
        span = 1
        # absorb every prior run priced at or below today's price
        while self._price_spans and self._price_spans[-1][0] <= price:
            span += self._price_spans.pop()[1]
        self._price_spans.append((price, span))
        return span

// LC 901. Monotonic stack of (price, span) pairs: each call pops every pair
// priced at or below the new price and absorbs their spans, so popped runs
// collapse into one entry and every call is amortized O(1).
class StockSpanner {
    vector<pair<int, int>> priceSpans;  // (price, span of days it absorbed)

   public:
    int next(int price) {
        int span = 1;
        while (!priceSpans.empty() && priceSpans.back().first <= price) {
            span += priceSpans.back().second;  // absorb the whole popped run at once
            priceSpans.pop_back();
        }
        priceSpans.push_back({price, span});
        return span;
    }
};

/// LC 901. Monotonic stack of (price, span) pairs: each call pops every
/// pair priced at or below today, absorbing their spans into the new
/// entry, then pushes the collapsed pair. Collapsing popped runs into one
/// pair is what makes each call amortized O(1).
pub struct StockSpanner {
    price_spans: Vec<(i32, i32)>,
}

impl StockSpanner {
    pub fn new() -> Self {
        StockSpanner { price_spans: Vec::new() }
    }

    pub fn next(&mut self, price: i32) -> i32 {
        let mut span = 1;
        // Whole runs already known to be <= price merge into today's span.
        while self.price_spans.last().map_or(false, |&(prior, _)| prior <= price) {
            span += self.price_spans.pop().unwrap().1;
        }
        self.price_spans.push((price, span));
        span
    }
}

/** LC 901. Monotonic stack of [price, span] pairs; popped runs collapse into the new span, amortized O(1). */
export class StockSpanner {
  private priceSpans: [number, number][] = []; // prices strictly decrease down the stack

  next(price: number): number {
    let span = 1;
    while (this.priceSpans.length > 0 && this.priceSpans[this.priceSpans.length - 1][0] <= price) {
      span += this.priceSpans.pop()![1]; // absorb the popped run so it is never re-scanned
    }
    this.priceSpans.push([price, span]);
    return span;
  }
}

// LC 901. Monotonic stack of (price, span) pairs: each call pops every pair
// priced at or below the new price and absorbs their spans, so popped runs
// collapse into one entry and every call is amortized O(1).
type StockSpanner struct {
	priceSpans [][2]int // (price, span of days it absorbed)
}

func newStockSpanner() *StockSpanner {
	return &StockSpanner{}
}

func (s *StockSpanner) next(price int) int {
	span := 1
	for len(s.priceSpans) > 0 && s.priceSpans[len(s.priceSpans)-1][0] <= price {
		span += s.priceSpans[len(s.priceSpans)-1][1] // absorb the whole popped run at once
		s.priceSpans = s.priceSpans[:len(s.priceSpans)-1]
	}
	s.priceSpans = append(s.priceSpans, [2]int{price, span})
	return span
}

// LC 901. Monotonic stack of (price, span) pairs: each call pops every pair
// priced at or below the new price and absorbs their spans, so popped runs
// collapse into one entry and every call is amortized O(1).
class StockSpanner {
    var priceSpans: [(price: Int, span: Int)] = []

    func next(_ price: Int) -> Int {
        var span = 1
        while let top = priceSpans.last, top.price <= price {
            span += top.span  // absorb the whole popped run at once
            priceSpans.removeLast()
        }
        priceSpans.append((price, span))
        return span
    }
}

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    """LC 853. Car Fleet.

    Sort cars by position descending (closest to the target first) and
    compute each car's solo arrival time. A car arriving no later than
    the fleet directly ahead catches up and merges into it, so only a
    strictly later arrival starts a new fleet. The stack height is the
    fleet count. O(n log n) time, O(n) space.
    """
    arrival_times: list[float] = []
    for pos, spd in sorted(zip(position, speed), reverse=True):
        time_to_target = (target - pos) / spd
        # arriving at or before the fleet ahead means catching it and merging
        if not arrival_times or time_to_target > arrival_times[-1]:
            arrival_times.append(time_to_target)
    return len(arrival_times)

// LC 853. Walk cars from closest to target backward; a car whose arrival time
// is at most the fleet ahead's catches it and merges, so only a strictly
// slower arrival starts a new fleet. Stack height = fleet count.
int carFleet(int target, vector<int> position, vector<int> speed) {
    int n = static_cast<int>(position.size());
    vector<int> order(n);
    for (int i = 0; i < n; ++i) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return position[a] > position[b]; });
    vector<double> arrivalTimes;  // one entry per fleet, increasing toward the back of the road
    for (int car : order) {
        double arrival = static_cast<double>(target - position[car]) / speed[car];
        if (arrivalTimes.empty() || arrival > arrivalTimes.back())
            arrivalTimes.push_back(arrival);  // can't catch the fleet ahead: new fleet
    }
    return static_cast<int>(arrivalTimes.size());
}

/// LC 853. Sort cars by position descending (nearest the target first) and
/// compute f64 arrival_times; a car arriving no later than the fleet ahead
/// merges into it, so only a strictly later arrival starts a new fleet.
/// The stack height at the end is the fleet count.
pub fn car_fleet(target: i32, position: Vec<i32>, speed: Vec<i32>) -> i32 {
    let mut cars: Vec<(i32, i32)> = position.into_iter().zip(speed).collect();
    cars.sort_unstable_by_key(|&(pos, _)| std::cmp::Reverse(pos));
    let mut arrival_times: Vec<f64> = Vec::new();
    for (pos, spd) in cars {
        let arrival = (target - pos) as f64 / spd as f64;
        // Arriving no later than the fleet ahead means this car merges into it.
        if arrival_times.last().map_or(true, |&ahead| arrival > ahead) {
            arrival_times.push(arrival);
        }
    }
    arrival_times.len() as i32
}

/** LC 853. Lead car first (sort by position desc); push an arrival time only when it exceeds the stack top. */
export function carFleet(target: number, position: number[], speed: number[]): number {
  const byPositionDesc = position.map((_, car) => car).sort((a, b) => position[b] - position[a]);
  const fleetArrivalTimes: number[] = [];
  for (const car of byPositionDesc) {
    const arrivalTime = (target - position[car]) / speed[car];
    // arriving no later than the fleet ahead means catching it and merging, so no new fleet
    if (fleetArrivalTimes.length === 0 || arrivalTime > fleetArrivalTimes[fleetArrivalTimes.length - 1]) {
      fleetArrivalTimes.push(arrivalTime);
    }
  }
  return fleetArrivalTimes.length;
}

// LC 853. Walk cars from closest to target backward; a car whose arrival time
// is at most the fleet ahead's catches it and merges, so only a strictly
// slower arrival starts a new fleet. Stack height = fleet count.
func carFleet(target int, position []int, speed []int) int {
	n := len(position)
	order := make([]int, n)
	for i := range order {
		order[i] = i
	}
	sort.Slice(order, func(a, b int) bool { return position[order[a]] > position[order[b]] })
	arrivalTimes := []float64{} // one entry per fleet, increasing toward the back of the road
	for _, car := range order {
		arrival := float64(target-position[car]) / float64(speed[car])
		if len(arrivalTimes) == 0 || arrival > arrivalTimes[len(arrivalTimes)-1] {
			arrivalTimes = append(arrivalTimes, arrival) // can't catch the fleet ahead: new fleet
		}
	}
	return len(arrivalTimes)
}

// LC 853. Walk cars from closest to target backward; a car whose arrival time
// is at most the fleet ahead's catches it and merges, so only a strictly
// slower arrival starts a new fleet. Stack height = fleet count.
func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
    let cars = zip(position, speed).sorted { $0.0 > $1.0 }  // closest to target first
    var arrivalTimes: [Double] = []  // one entry per fleet, increasing toward the back of the road
    for (pos, spd) in cars {
        let arrival = Double(target - pos) / Double(spd)
        if arrivalTimes.isEmpty || arrival > arrivalTimes.last! {
            arrivalTimes.append(arrival)  // can't catch the fleet ahead: new fleet
        }
    }
    return arrivalTimes.count
}

def simplify_path(path: str) -> str:
    """LC 71. Simplify Path.

    Split on '/' and run a stack of directory names: skip empty pieces
    and '.', pop on '..', push everything else. Rejoining the stack
    under a leading '/' rebuilds the canonical path. O(n) time, O(n)
    space.
    """
    directories: list[str] = []
    for piece in path.split("/"):
        if piece == "" or piece == ".":
            continue
        if piece == "..":
            if directories:  # '..' at the root is silently ignored
                directories.pop()
        else:
            directories.append(piece)
    return "/" + "/".join(directories)

// LC 71. Split on '/' into a stack of directory names: skip "" and ".",
// pop on ".." (silently a no-op at the root), then rejoin under a leading '/'.
string simplifyPath(string path) {
    vector<string> dirs;
    stringstream pieces(path);
    string piece;
    while (getline(pieces, piece, '/')) {
        if (piece.empty() || piece == ".") continue;
        if (piece == "..") {
            if (!dirs.empty()) dirs.pop_back();  // ".." at the root is ignored
        } else {
            dirs.push_back(piece);
        }
    }
    string canonical;
    for (const string& dir : dirs) canonical += "/" + dir;
    return canonical.empty() ? "/" : canonical;
}

/// LC 71. Split on '/' and run a stack of directory names: skip empty
/// pieces and ".", pop on ".." (silently a no-op at the root), push the
/// rest. Rejoining under a leading '/' is the canonical path.
pub fn simplify_path(path: String) -> String {
    let mut dirs: Vec<&str> = Vec::new();
    for piece in path.split('/') {
        match piece {
            "" | "." => {}
            ".." => {
                dirs.pop(); // ".." above the root pops nothing, by design
            }
            dir => dirs.push(dir),
        }
    }
    format!("/{}", dirs.join("/"))
}

/** LC 71. Split on '/': skip '' and '.', pop on '..', push the rest, rejoin under a leading '/'. */
export function simplifyPath(path: string): string {
  const directories: string[] = [];
  for (const piece of path.split("/")) {
    if (piece === "" || piece === ".") continue;
    if (piece === "..") directories.pop(); // popping an empty stack silently ignores '..' at the root
    else directories.push(piece);
  }
  return "/" + directories.join("/");
}

// LC 71. Split on '/' into a stack of directory names: skip "" and ".",
// pop on ".." (silently a no-op at the root), then rejoin under a leading '/'.
func simplifyPath(path string) string {
	dirs := []string{}
	for _, piece := range strings.Split(path, "/") {
		if piece == "" || piece == "." {
			continue
		}
		if piece == ".." {
			if len(dirs) > 0 { // ".." at the root is ignored
				dirs = dirs[:len(dirs)-1]
			}
		} else {
			dirs = append(dirs, piece)
		}
	}
	return "/" + strings.Join(dirs, "/")
}

// LC 71. Split on '/' into a stack of directory names: skip "." (split already
// drops empty pieces), pop on ".." (a no-op at the root), rejoin under '/'.
func simplifyPath(_ path: String) -> String {
    var dirs: [String] = []
    for piece in path.split(separator: "/") {
        if piece == "." { continue }
        if piece == ".." {
            if !dirs.isEmpty { dirs.removeLast() }  // ".." at the root is ignored
        } else {
            dirs.append(String(piece))
        }
    }
    return "/" + dirs.joined(separator: "/")
}

def decode_string(s: str) -> str:
    """LC 394. Decode String.

    One pass with two stacks, repeat counts and partial strings: '['
    pushes the pending count and the string built so far, then resets
    both; ']' repeats the current segment by the popped count and
    appends it to the popped outer string. Nesting works because each
    ']' closes exactly the most recent '['. O(output) time and space.
    """
    repeat_counts: list[int] = []
    partial_strings: list[str] = []
    current = ""
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)  # multi-digit counts accumulate digit by digit
        elif ch == "[":
            repeat_counts.append(count)
            partial_strings.append(current)
            count = 0
            current = ""
        elif ch == "]":
            # the segment since '[' repeats, glued onto the suspended outer string
            current = partial_strings.pop() + current * repeat_counts.pop()
        else:
            current += ch
    return current

// LC 394. Two stacks: '[' saves the repeat count and the string built so far,
// ']' rebuilds as saved prefix + current segment repeated. Nesting works
// because each ']' closes exactly the most recent '['.
string decodeString(string s) {
    vector<int> repeatCounts;
    vector<string> savedPrefixes;
    string current;
    int count = 0;
    for (char ch : s) {
        if (isdigit(static_cast<unsigned char>(ch))) {
            count = count * 10 + (ch - '0');  // multi-digit counts accumulate
        } else if (ch == '[') {
            repeatCounts.push_back(count);
            savedPrefixes.push_back(current);
            current.clear();
            count = 0;
        } else if (ch == ']') {
            string rebuilt = savedPrefixes.back();
            savedPrefixes.pop_back();
            for (int i = 0; i < repeatCounts.back(); ++i) rebuilt += current;
            repeatCounts.pop_back();
            current = move(rebuilt);
        } else {
            current += ch;
        }
    }
    return current;
}

/// LC 394. Two stacks in lockstep -- repeat_counts and the enclosing
/// partial strings: '[' pushes both and resets, ']' repeats the current
/// segment by the popped count and appends it to the popped string.
/// Nesting works because each ']' closes exactly the most recent '['.
pub fn decode_string(s: String) -> String {
    let mut repeat_counts: Vec<usize> = Vec::new();
    let mut enclosing_segments: Vec<String> = Vec::new();
    let mut segment = String::new();
    let mut pending_count = 0usize;
    for ch in s.chars() {
        match ch {
            // Counts can be multi-digit, so accumulate digit by digit.
            '0'..='9' => pending_count = pending_count * 10 + ch.to_digit(10).unwrap() as usize,
            '[' => {
                repeat_counts.push(pending_count);
                pending_count = 0;
                // Park the enclosing string and start the bracketed segment fresh.
                enclosing_segments.push(std::mem::take(&mut segment));
            }
            ']' => {
                let repeated = segment.repeat(repeat_counts.pop().unwrap());
                segment = enclosing_segments.pop().unwrap();
                segment.push_str(&repeated);
            }
            letter => segment.push(letter),
        }
    }
    segment
}

/** LC 394. Two stacks (counts, parent strings); ']' repeats the current segment into its parent. */
export function decodeString(s: string): string {
  const repeatCounts: number[] = [];
  const parentSegments: string[] = [];
  let currentSegment = "";
  let currentCount = 0;
  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      currentCount = currentCount * 10 + Number(ch); // multi-digit counts accumulate digit by digit
    } else if (ch === "[") {
      repeatCounts.push(currentCount);
      parentSegments.push(currentSegment);
      currentCount = 0;
      currentSegment = "";
    } else if (ch === "]") {
      // the just-closed segment repeats, then reattaches to the string it was nested inside
      currentSegment = parentSegments.pop()! + currentSegment.repeat(repeatCounts.pop()!);
    } else {
      currentSegment += ch;
    }
  }
  return currentSegment;
}

// LC 394. Two stacks: '[' saves the repeat count and the string built so far,
// ']' rebuilds as saved prefix + current segment repeated. Nesting works
// because each ']' closes exactly the most recent '['.
func decodeString(s string) string {
	repeatCounts := []int{}
	savedPrefixes := []string{}
	current := ""
	count := 0
	for i := 0; i < len(s); i++ {
		ch := s[i]
		switch {
		case ch >= '0' && ch <= '9':
			count = count*10 + int(ch-'0') // multi-digit counts accumulate
		case ch == '[':
			repeatCounts = append(repeatCounts, count)
			savedPrefixes = append(savedPrefixes, current)
			current = ""
			count = 0
		case ch == ']':
			rebuilt := savedPrefixes[len(savedPrefixes)-1] + strings.Repeat(current, repeatCounts[len(repeatCounts)-1])
			savedPrefixes = savedPrefixes[:len(savedPrefixes)-1]
			repeatCounts = repeatCounts[:len(repeatCounts)-1]
			current = rebuilt
		default:
			current += string(ch)
		}
	}
	return current
}

// LC 394. Two stacks: '[' saves the repeat count and the string built so far,
// ']' rebuilds as saved prefix + current segment repeated. Nesting works
// because each ']' closes exactly the most recent '['.
func decodeString(_ s: String) -> String {
    var repeatCounts: [Int] = []
    var savedPrefixes: [String] = []
    var current = ""
    var count = 0
    for ch in s {
        if let digit = ch.wholeNumberValue {
            count = count * 10 + digit  // multi-digit counts accumulate
        } else if ch == "[" {
            repeatCounts.append(count)
            savedPrefixes.append(current)
            current = ""
            count = 0
        } else if ch == "]" {
            current = savedPrefixes.removeLast() + String(repeating: current, count: repeatCounts.removeLast())
        } else {
            current.append(ch)
        }
    }
    return current
}

class FreqStack:
    """LC 895. Maximum Frequency Stack.

    A count map from value to frequency plus one stack per frequency
    level: a value's k-th copy lives on the stack for level k. Popping
    from the max-frequency stack breaks ties by recency for free, and
    lower copies resurface as the maximum drops. O(1) per operation,
    O(n) space.
    """

    def __init__(self) -> None:
        self._counts: dict[int, int] = {}
        self._level_stacks: dict[int, list[int]] = {}
        self._max_freq = 0

    def push(self, val: int) -> None:
        freq = self._counts.get(val, 0) + 1
        self._counts[val] = freq
        self._level_stacks.setdefault(freq, []).append(val)
        self._max_freq = max(self._max_freq, freq)

    def pop(self) -> int:
        val = self._level_stacks[self._max_freq].pop()
        self._counts[val] -= 1
        if not self._level_stacks[self._max_freq]:  # level emptied, so the max drops by one
            self._max_freq -= 1
        return val

// LC 895. Count per value plus one stack per frequency level; pop takes from
// the top level, which breaks ties by recency. Copies left on lower levels
// resurface as the maximum frequency drops. Every operation O(1).
class FreqStack {
    unordered_map<int, int> countOf;        // value -> current frequency
    vector<vector<int>> stacksByFrequency;  // [f-1] = values whose push raised their count to f

   public:
    void push(int val) {
        int newCount = ++countOf[val];
        if (static_cast<int>(stacksByFrequency.size()) < newCount) stacksByFrequency.push_back({});
        stacksByFrequency[newCount - 1].push_back(val);
    }
    int pop() {
        int val = stacksByFrequency.back().back();
        stacksByFrequency.back().pop_back();
        if (stacksByFrequency.back().empty()) stacksByFrequency.pop_back();  // max frequency drops
        --countOf[val];
        return val;
    }
};

/// LC 895. counts maps value -> frequency, and frequency_levels[f - 1] is
/// a stack of every value at the moment it reached frequency f (so a value
/// appears on one stack per occurrence). Pop serves the top level: ties
/// break by recency for free, and lower copies resurface as the maximum
/// frequency drops. Every operation is O(1).
pub struct FreqStack {
    counts: HashMap<i32, usize>,
    frequency_levels: Vec<Vec<i32>>,
}

impl FreqStack {
    pub fn new() -> Self {
        FreqStack { counts: HashMap::new(), frequency_levels: Vec::new() }
    }

    pub fn push(&mut self, val: i32) {
        let freq = self.counts.entry(val).or_insert(0);
        *freq += 1;
        if self.frequency_levels.len() < *freq {
            self.frequency_levels.push(Vec::new()); // val just set a new maximum frequency
        }
        self.frequency_levels[*freq - 1].push(val);
    }

    pub fn pop(&mut self) -> i32 {
        let top_level = self.frequency_levels.last_mut().unwrap();
        let val = top_level.pop().unwrap();
        if top_level.is_empty() {
            self.frequency_levels.pop(); // the maximum frequency just dropped by one
        }
        *self.counts.get_mut(&val).unwrap() -= 1;
        val
    }
}

/** LC 895. Count map + one stack per frequency; pop the max-frequency stack and copies resurface lower. */
export class FreqStack {
  private countOf = new Map<number, number>();
  private stacksByFrequency: number[][] = []; // stacksByFrequency[f - 1]: values in push order at frequency f
  private maxFrequency = 0;

  push(val: number): void {
    const count = (this.countOf.get(val) ?? 0) + 1;
    this.countOf.set(val, count);
    if (count > this.maxFrequency) {
      this.maxFrequency = count;
      this.stacksByFrequency.push([]);
    }
    this.stacksByFrequency[count - 1].push(val); // copies stay on every lower-frequency stack
  }

  pop(): number {
    const topStack = this.stacksByFrequency[this.maxFrequency - 1];
    const val = topStack.pop()!; // stack order breaks frequency ties by recency for free
    this.countOf.set(val, this.maxFrequency - 1);
    if (topStack.length === 0) {
      this.stacksByFrequency.pop();
      this.maxFrequency--;
    }
    return val;
  }
}

// LC 895. Count per value plus one stack per frequency level; pop takes from
// the top level, which breaks ties by recency. Copies left on lower levels
// resurface as the maximum frequency drops. Every operation O(1).
type FreqStack struct {
	countOf           map[int]int // value -> current frequency
	stacksByFrequency [][]int     // [f-1] = values whose push raised their count to f
}

func newFreqStack() *FreqStack {
	return &FreqStack{countOf: map[int]int{}}
}

func (s *FreqStack) push(val int) {
	s.countOf[val]++
	newCount := s.countOf[val]
	if len(s.stacksByFrequency) < newCount {
		s.stacksByFrequency = append(s.stacksByFrequency, nil)
	}
	s.stacksByFrequency[newCount-1] = append(s.stacksByFrequency[newCount-1], val)
}

func (s *FreqStack) pop() int {
	top := len(s.stacksByFrequency) - 1
	level := s.stacksByFrequency[top]
	val := level[len(level)-1]
	s.stacksByFrequency[top] = level[:len(level)-1]
	if len(s.stacksByFrequency[top]) == 0 { // level emptied: max frequency drops
		s.stacksByFrequency = s.stacksByFrequency[:top]
	}
	s.countOf[val]--
	return val
}

// LC 895. Count per value plus one stack per frequency level; pop takes from
// the top level, which breaks ties by recency. Copies left on lower levels
// resurface as the maximum frequency drops. Every operation O(1).
class FreqStack {
    var countOf: [Int: Int] = [:]        // value -> current frequency
    var stacksByFrequency: [[Int]] = []  // [f-1] = values whose push raised their count to f

    func push(_ val: Int) {
        let newCount = (countOf[val] ?? 0) + 1
        countOf[val] = newCount
        if stacksByFrequency.count < newCount { stacksByFrequency.append([]) }
        stacksByFrequency[newCount - 1].append(val)
    }
    func pop() -> Int {
        let val = stacksByFrequency[stacksByFrequency.count - 1].removeLast()
        if stacksByFrequency.last!.isEmpty { stacksByFrequency.removeLast() }  // max frequency drops
        countOf[val]! -= 1
        return val
    }
}

def largest_rectangle_area(heights: list[int]) -> int:
    """LC 84. Largest Rectangle in Histogram.

    Maintain an increasing stack of indices. When a shorter bar
    arrives, each pop fixes the popped bar as the rectangle's height,
    bounded by the first shorter bar on each side; the gap between the
    new stack top and the current index is the width. Each index is
    pushed and popped once. O(n) time, O(n) space.
    """
    best = 0
    rising_indices: list[int] = []
    # the appended 0 is a sentinel bar that flushes everything left on the stack
    for i, height in enumerate(heights + [0]):
        while rising_indices and heights[rising_indices[-1]] > height:
            fixed_height = heights[rising_indices.pop()]
            # width is the open gap between the new stack top and i, both exclusive
            width = i if not rising_indices else i - rising_indices[-1] - 1
            best = max(best, fixed_height * width)
        rising_indices.append(i)
    return best

// LC 84. Increasing stack of indices; when the current bar is shorter than
// the top, each pop finalizes one bar, bounded by the first shorter bar on
// each side. A zero-height sentinel appended at the end flushes the stack.
int largestRectangleArea(vector<int> heights) {
    heights.push_back(0);  // sentinel: shorter than every bar, forces a full flush
    vector<int> increasingIndices;
    int best = 0;
    for (int i = 0; i < static_cast<int>(heights.size()); ++i) {
        while (!increasingIndices.empty() && heights[increasingIndices.back()] > heights[i]) {
            int height = heights[increasingIndices.back()];
            increasingIndices.pop_back();
            int leftBound = increasingIndices.empty() ? -1 : increasingIndices.back();  // first shorter bar on the left
            best = max(best, height * (i - leftBound - 1));  // width is exclusive of both bounds
        }
        increasingIndices.push_back(i);
    }
    return best;
}

/// LC 84. Increasing stack of indices: a shorter bar pops taller ones, and
/// each popped height times the width between the new stack top and the
/// current index (both exclusive) finalizes that bar's best rectangle.
/// A zero-height sentinel chained after the array flushes the stack: O(n).
pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut unresolved_indices: Vec<usize> = Vec::new();
    let mut best_area = 0;
    for (i, &bar) in heights.iter().chain(std::iter::once(&0)).enumerate() {
        while unresolved_indices.last().map_or(false, |&top| heights[top] > bar) {
            let height = heights[unresolved_indices.pop().unwrap()];
            // The popped bar extends from just past the next-shorter bar on its left to i - 1.
            let left_edge = unresolved_indices.last().map_or(0, |&below| below + 1);
            best_area = best_area.max(height * (i - left_edge) as i32);
        }
        unresolved_indices.push(i);
    }
    best_area
}

/** LC 84. Increasing index stack; each pop fixes one bar's area between its shorter neighbors. */
export function largestRectangleArea(heights: number[]): number {
  const ascendingIndices: number[] = [];
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const height = i === heights.length ? 0 : heights[i]; // zero-height sentinel flushes the whole stack
    while (
      ascendingIndices.length > 0 &&
      heights[ascendingIndices[ascendingIndices.length - 1]] > height
    ) {
      const barHeight = heights[ascendingIndices.pop()!];
      // width runs from just past the next-shorter bar on the left up to (not including) i
      const width =
        ascendingIndices.length === 0 ? i : i - ascendingIndices[ascendingIndices.length - 1] - 1;
      best = Math.max(best, barHeight * width);
    }
    ascendingIndices.push(i);
  }
  return best;
}

// LC 84. Increasing stack of indices; when the current bar is shorter than
// the top, each pop finalizes one bar, bounded by the first shorter bar on
// each side. A zero-height sentinel appended at the end flushes the stack.
func largestRectangleArea(heights []int) int {
	bars := make([]int, len(heights), len(heights)+1)
	copy(bars, heights)
	bars = append(bars, 0) // sentinel: shorter than every bar, forces a full flush
	increasingIndices := []int{}
	best := 0
	for i, height := range bars {
		for len(increasingIndices) > 0 && bars[increasingIndices[len(increasingIndices)-1]] > height {
			fixedHeight := bars[increasingIndices[len(increasingIndices)-1]]
			increasingIndices = increasingIndices[:len(increasingIndices)-1]
			leftBound := -1 // first shorter bar on the left
			if len(increasingIndices) > 0 {
				leftBound = increasingIndices[len(increasingIndices)-1]
			}
			if area := fixedHeight * (i - leftBound - 1); area > best { // width is exclusive of both bounds
				best = area
			}
		}
		increasingIndices = append(increasingIndices, i)
	}
	return best
}

// LC 84. Increasing stack of indices; when the current bar is shorter than
// the top, each pop finalizes one bar, bounded by the first shorter bar on
// each side. A zero-height sentinel appended at the end flushes the stack.
func largestRectangleArea(_ heights: [Int]) -> Int {
    var bars = heights
    bars.append(0)  // sentinel: shorter than every bar, forces a full flush
    var increasingIndices: [Int] = []
    var best = 0
    for i in 0..<bars.count {
        while let top = increasingIndices.last, bars[top] > bars[i] {
            let height = bars[top]
            increasingIndices.removeLast()
            let leftBound = increasingIndices.last ?? -1  // first shorter bar on the left
            best = max(best, height * (i - leftBound - 1))  // width is exclusive of both bounds
        }
        increasingIndices.append(i)
    }
    return best
}