"""
# 735. Asteroid Collision

## Problem
We are given an array `asteroids` of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign
represents its direction (positive = right, negative = left). All asteroids
move at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids
meet, the smaller one explodes. If both are the same size, both explode. Two
asteroids moving in the same direction never meet.

## Examples
```text
Input:  asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: 10 and -5 collide -> 10 survives. 5 and 10 never collide.

Input:  asteroids = [8, -8]
Output: []
Explanation: 8 and -8 collide -> both explode.

Input:  asteroids = [10, 2, -5]
Output: [10]
Explanation: 2 and -5 collide -> -5 wins. 10 and -5 collide -> 10 wins.
```

## Constraints
- `2 <= asteroids.length <= 10^4`
- `-1000 <= asteroids[i] <= 1000`
- `asteroids[i] != 0`
"""

from typing import List


class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        # Only collisions happen when a left-moving asteroid meets a right-moving one on stack
        # Keep destroying top of stack while it's smaller than the incoming asteroid
        # Equal sizes destroy both; larger stack top destroys incoming
        # O(n) time, O(n) space — stack simulation of collisions
        stack = []
        for a in asteroids:
            alive = True
            while alive and a < 0 and stack and stack[-1] > 0:
                if stack[-1] < -a:
                    stack.pop()          # right asteroid destroyed
                elif stack[-1] == -a:
                    stack.pop()          # both destroyed
                    alive = False
                else:
                    alive = False        # left asteroid destroyed
            if alive:
                stack.append(a)
        return stack


if __name__ == "__main__":
    s = Solution()
    assert s.asteroidCollision([5, 10, -5]) == [5, 10]
    assert s.asteroidCollision([8, -8]) == []
    assert s.asteroidCollision([10, 2, -5]) == [10]
    assert s.asteroidCollision([-2, -1, 1, 2]) == [-2, -1, 1, 2]
    assert s.asteroidCollision([1, -1]) == []
    print("All tests passed.")

"""
# 682. Baseball Game

## Problem
You are keeping score for a baseball game with special rules. Given a list of
operations, calculate the sum of all valid scores.

Operations:
- Integer string: record a new score of that value
- `"+"`: record a new score that is the sum of the previous two scores
- `"D"`: record a new score that is double the previous score
- `"C"`: invalidate the previous score, removing it from the record

## Examples
```text
Input:  operations = ["5","2","C","D","+"]
Output: 30
Explanation:
  "5" -> record [5]
  "2" -> record [5, 2]
  "C" -> remove last -> [5]
  "D" -> double last -> [5, 10]
  "+" -> sum last two -> [5, 10, 15]
  Total = 5 + 10 + 15 = 30

Input:  operations = ["5","-2","4","C","D","9","+","+"]
Output: 27
```

## Constraints
- `1 <= operations.length <= 1000`
- `operations[i]` is `"C"`, `"D"`, `"+"`, or a string representing an integer
  in the range `[-3 * 10^4, 3 * 10^4]`
- For `"+"`, there will always be at least two previous scores
- For `"C"` and `"D"`, there will always be at least one previous score
"""

from typing import List


class Solution:
    def calPoints_list(self, operations: List[str]) -> int:
        # Simulate the record: C removes last, D doubles last, + sums last two
        # O(n) time, O(n) space — list as mutable record
        record = []
        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)

    def calPoints(self, operations: List[str]) -> int:
        # Same logic with explicit stack name for clarity
        # O(n) time, O(n) space — explicit stack (same logic, named for clarity)
        stack = []
        for op in operations:
            if op == "C":
                stack.pop()
            elif op == "D":
                stack.append(stack[-1] * 2)
            elif op == "+":
                stack.append(stack[-1] + stack[-2])
            else:
                stack.append(int(op))
        return sum(stack)


if __name__ == "__main__":
    s = Solution()
    assert s.calPoints(["5", "2", "C", "D", "+"]) == 30
    assert s.calPoints(["5", "-2", "4", "C", "D", "9", "+", "+"]) == 27
    assert s.calPoints(["1"]) == 1
    print("All tests passed.")

"""
# 853. Car Fleet

## Problem
There are `n` cars at given miles away from the starting point, all driving
towards the same `target` destination. Each car `i` has a position
`position[i]` and speed `speed[i]` (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and
drive bumper to bumper at the slower car's speed. Two cars that drive bumper
to bumper are considered a single car fleet.

Return the number of car fleets that will arrive at the destination.

## Examples
```text
Input:  target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
  Cars at 10 and 8 become a fleet (arrive at 12 at time 1 and 1).
  Car at 0 is its own fleet (arrives at time 12).
  Cars at 5 and 3 become a fleet (arrive at time 7 and 3 -> 3 catches 5).

Input:  target = 10, position = [3], speed = [3]
Output: 1

Input:  target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
```

## Constraints
- `n == position.length == speed.length`
- `1 <= n <= 10^5`
- `0 < target <= 10^6`
- `0 <= position[i] < target`
- All values of `position` are unique
- `0 < speed[i] <= 10^6`
"""

from typing import List


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Sort cars by position descending (closest to target first)
        # Compute arrival time for each car; if it arrives before the car ahead, it joins that fleet
        # A new fleet forms only when a car arrives strictly later than the current top
        # O(n log n) time, O(n) space — sort by position, stack of arrival times
        pairs = sorted(zip(position, speed), reverse=True)
        stack = []
        for pos, spd in pairs:
            time = (target - pos) / spd
            if not stack or time > stack[-1]:
                stack.append(time)
            # if time <= stack[-1], this car catches the fleet ahead -> same fleet
        return len(stack)


if __name__ == "__main__":
    s = Solution()
    assert s.carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3]) == 3
    assert s.carFleet(10, [3], [3]) == 1
    assert s.carFleet(100, [0, 2, 4], [4, 2, 1]) == 1
    assert s.carFleet(10, [6, 8], [3, 2]) == 2
    print("All tests passed.")

"""
# 739. Daily Temperatures

## Problem
Given an array of integers `temperatures` representing daily temperatures,
return an array `answer` such that `answer[i]` is the number of days you have
to wait after the `i`-th day to get a warmer temperature. If there is no
future day with a warmer temperature, `answer[i] == 0`.

## Examples
```text
Input:  temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input:  temperatures = [30,40,50,60]
Output: [1,1,1,0]

Input:  temperatures = [30,60,90]
Output: [1,1,0]
```

## Constraints
- `1 <= temperatures.length <= 10^5`
- `30 <= temperatures[i] <= 100`
"""

from typing import List


class Solution:
    def dailyTemperatures_brute(self, temperatures: List[int]) -> List[int]:
        # For each day, scan forward until a warmer day is found — O(n^2)
        # O(n^2) time, O(1) extra space — check every future day
        n = len(temperatures)
        answer = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    answer[i] = j - i
                    break
        return answer

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Monotonic decreasing stack stores indices of unresolved days
        # When a warmer day arrives, resolve all cooler days on the stack
        # O(n) time, O(n) space — decreasing monotonic stack of indices
        n = len(temperatures)
        answer = [0] * n
        stack = []  # indices with unresolved warmer day
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                idx = stack.pop()
                answer[idx] = i - idx
            stack.append(i)
        return answer


if __name__ == "__main__":
    s = Solution()
    assert s.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
    assert s.dailyTemperatures([30, 40, 50, 60]) == [1, 1, 1, 0]
    assert s.dailyTemperatures([30, 60, 90]) == [1, 1, 0]
    assert s.dailyTemperatures_brute([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
    print("All tests passed.")

"""
# 394. Decode String

## Problem
Given an encoded string, return its decoded string.

The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside
the square brackets is repeated exactly `k` times. `k` is guaranteed to be a
positive integer. You may assume the input is always valid — no extra white
spaces, square brackets are well-formed, etc.

Note: The original data does not contain any digits; all digits are only for
repeat counts `k`. For example, there won't be input like `3a` or `2[4]`.

## Examples
```text
Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

Input:  s = "3[a2[c]]"
Output: "accaccacc"

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
```

## Constraints
- `1 <= s.length <= 30`
- `s` consists of lowercase English letters, digits, and square brackets `[]`
- `s` is guaranteed to be a valid input
- All integers are in the range `[1, 300]`
"""


class Solution:
    def decodeString_stack(self, s: str) -> str:
        # On '[': save current (count, string) to stack, reset both
        # On ']': pop saved state, append current string repeated count times
        # Handles nested brackets because each level is saved/restored on stack
        # O(n) time, O(n) space — iterative stack of (repeat_count, built_string)
        stack = []
        cur_str = ""
        cur_num = 0
        for ch in s:
            if ch.isdigit():
                cur_num = cur_num * 10 + int(ch)
            elif ch == "[":
                stack.append((cur_num, cur_str))
                cur_str, cur_num = "", 0
            elif ch == "]":
                num, prev_str = stack.pop()
                cur_str = prev_str + cur_str * num
            else:
                cur_str += ch
        return cur_str

    def decodeString(self, s: str) -> str:
        # Recursive descent: parse number, skip '[', recurse for inner, skip ']'
        # Returns (decoded_string, next_index) so caller knows where to continue
        # O(n) time, O(n) space — recursive descent with index pointer
        def decode(i: int):
            result = ""
            while i < len(s) and s[i] != "]":
                if s[i].isdigit():
                    num = 0
                    while s[i].isdigit():
                        num = num * 10 + int(s[i])
                        i += 1
                    i += 1  # skip '['
                    inner, i = decode(i)
                    i += 1  # skip ']'
                    result += inner * num
                else:
                    result += s[i]
                    i += 1
            return result, i

        return decode(0)[0]


if __name__ == "__main__":
    s = Solution()
    assert s.decodeString_stack("3[a]2[bc]") == "aaabcbc"
    assert s.decodeString_stack("3[a2[c]]") == "accaccacc"
    assert s.decodeString_stack("2[abc]3[cd]ef") == "abcabccdcdcdef"
    assert s.decodeString("3[a]2[bc]") == "aaabcbc"
    assert s.decodeString("3[a2[c]]") == "accaccacc"
    assert s.decodeString("2[abc]3[cd]ef") == "abcabccdcdcdef"
    print("All tests passed.")

"""
# 150. Evaluate Reverse Polish Notation

## Problem
Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or
another expression. Division truncates toward zero.

## Examples
```text
Input:  tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input:  tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
```

## Constraints
- `1 <= tokens.length <= 10^4`
- `tokens[i]` is either an operator `+`, `-`, `*`, `/`, or an integer in the
  range `[-200, 200]`
- The given RPN expression is always valid
"""

from typing import List


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        # Push numbers; on operator, pop two operands and push result
        # Use int(a/b) instead of a//b to truncate toward zero (not floor)
        # O(n) time, O(n) space — single stack evaluation
        stack = []
        ops = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "*": lambda a, b: a * b,
            "/": lambda a, b: int(a / b),  # truncate toward zero
        }
        for t in tokens:
            if t in ops:
                b, a = stack.pop(), stack.pop()
                stack.append(ops[t](a, b))
            else:
                stack.append(int(t))
        return stack[0]


if __name__ == "__main__":
    s = Solution()
    assert s.evalRPN(["2", "1", "+", "3", "*"]) == 9
    assert s.evalRPN(["4", "13", "5", "/", "+"]) == 6
    assert s.evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) == 22
    assert s.evalRPN(["3", "-4", "/"]) == 0  # truncate toward zero: -0.75 -> 0
    print("All tests passed.")

"""
# 232. Implement Queue using Stacks

## Problem
Implement a first-in-first-out (FIFO) queue using only two stacks. The
implemented queue should support `push`, `pop`, `peek`, and `empty` operations.

You must use **only** standard stack operations: `push to top`, `peek/pop from
top`, `size`, and `is empty`.

## Operations
- `push(x)` — Push element `x` to the back of the queue.
- `pop()` — Removes the element from the front of the queue and returns it.
- `peek()` — Returns the element at the front of the queue.
- `empty()` — Returns `true` if the queue is empty, `false` otherwise.

## Examples
```text
Input:
  ["MyQueue","push","push","peek","pop","empty"]
  [[],[1],[2],[],[],[]]
Output:
  [null,null,null,1,1,false]
```

## Constraints
- `1 <= x <= 9`
- At most `100` calls will be made to `push`, `pop`, `peek`, and `empty`
- All calls to `pop` and `peek` are valid
"""


class MyQueue:
    """Approach 1: Two stacks, costly push — O(n) push, O(1) pop/peek."""

    def __init__(self):
        self.s1: list = []  # front stack
        self.s2: list = []  # temp stack

    def push(self, x: int) -> None:
        # Move all elements to s2, push new element to bottom of s1, move back
        # O(n) — move all to s2, push x to s1 (bottom), move back
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())

    def pop(self) -> int:
        # Front element is always at top of s1 after costly push
        # O(1)
        return self.s1.pop()

    def peek(self) -> int:
        # Peek top of s1 which holds the front of the queue
        # O(1)
        return self.s1[-1]

    def empty(self) -> bool:
        # Queue is empty when s1 is empty
        # O(1)
        return not self.s1


class MyQueueAmortized:
    """Approach 2: Two stacks, amortized O(1) — lazy transfer on pop/peek."""

    def __init__(self):
        self.inbox: list = []
        self.outbox: list = []

    def push(self, x: int) -> None:
        # Move all elements to s2, push new element to bottom of s1, move back
        # O(1)
        self.inbox.append(x)

    def _transfer(self) -> None:
        # Lazy transfer: only move inbox to outbox when outbox is empty
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self) -> int:
        # Front element is always at top of s1 after costly push
        # O(1) amortized
        self._transfer()
        return self.outbox.pop()

    def peek(self) -> int:
        # Peek top of s1 which holds the front of the queue
        # O(1) amortized
        self._transfer()
        return self.outbox[-1]

    def empty(self) -> bool:
        # Queue is empty when s1 is empty
        # O(1)
        return not self.inbox and not self.outbox


if __name__ == "__main__":
    for Cls in (MyQueue, MyQueueAmortized):
        q = Cls()
        q.push(1)
        q.push(2)
        assert q.peek() == 1
        assert q.pop() == 1
        assert q.empty() is False
        assert q.pop() == 2
        assert q.empty() is True
    print("All tests passed.")

"""
# 225. Implement Stack using Queues

## Problem
Implement a last-in-first-out (LIFO) stack using only two queues. The
implemented stack should support `push`, `pop`, `top`, and `empty` operations.

You must use **only** standard queue operations: `push to back`, `peek/pop from
front`, `size`, and `is empty`.

## Operations
- `push(x)` — Push element `x` onto stack.
- `pop()` — Removes the element on top of the stack and returns it.
- `top()` — Get the top element.
- `empty()` — Returns `true` if the stack is empty, `false` otherwise.

## Examples
```text
Input:
  ["MyStack","push","push","top","pop","empty"]
  [[],[1],[2],[],[],[]]
Output:
  [null,null,null,2,2,false]
```

## Constraints
- `1 <= x <= 9`
- At most `100` calls will be made to `push`, `pop`, `top`, and `empty`
- All calls to `pop` and `top` are valid
"""

from collections import deque


class MyStack:
    """Approach 1: Two queues, costly push — O(n) push, O(1) pop/top."""

    def __init__(self):
        self.q1: deque = deque()
        self.q2: deque = deque()

    def push(self, x: int) -> None:
        # Rotate all existing elements behind the new one so it's at front
        # O(n) — rotate all existing elements through q2 so x ends up at front
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        # Front of q1 is always the most recently pushed element
        # O(1)
        return self.q1.popleft()

    def top(self) -> int:
        # Peek front of q1
        # O(1)
        return self.q1[0]

    def empty(self) -> bool:
        # Stack is empty when q1 is empty
        # O(1)
        return not self.q1


class MyStackCostlyPop:
    """Approach 2: Two queues, costly pop — O(1) push, O(n) pop/top."""

    def __init__(self):
        self.q1: deque = deque()
        self.q2: deque = deque()

    def push(self, x: int) -> None:
        # Rotate all existing elements behind the new one so it's at front
        # O(1)
        self.q1.append(x)

    def pop(self) -> int:
        # Front of q1 is always the most recently pushed element
        # O(n) — drain q1 into q2 leaving last element
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        val = self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1
        return val

    def top(self) -> int:
        # Peek front of q1
        # O(n)
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        val = self.q1[0]
        self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
        return val

    def empty(self) -> bool:
        # Stack is empty when q1 is empty
        # O(1)
        return not self.q1


if __name__ == "__main__":
    for Cls in (MyStack, MyStackCostlyPop):
        st = Cls()
        st.push(1)
        st.push(2)
        assert st.top() == 2
        assert st.pop() == 2
        assert st.empty() is False
        assert st.pop() == 1
        assert st.empty() is True
    print("All tests passed.")

"""
# 84. Largest Rectangle in Histogram

## Problem
Given an array of integers `heights` representing the histogram's bar heights
where the width of each bar is `1`, return the area of the largest rectangle
in the histogram.

## Examples
```text
Input:  heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle has area 10 (bars of height 5 and 6,
             width 2).

Input:  heights = [2,4]
Output: 4
```

## Constraints
- `1 <= heights.length <= 10^5`
- `0 <= heights[i] <= 10^4`
"""

from typing import List


class Solution:
    def largestRectangleArea_brute(self, heights: List[int]) -> int:
        # For each starting bar, extend right tracking minimum height — O(n^2)
        # O(n^2) time, O(1) extra space — expand each bar left and right
        n = len(heights)
        max_area = 0
        for i in range(n):
            min_h = heights[i]
            for j in range(i, n):
                min_h = min(min_h, heights[j])
                max_area = max(max_area, min_h * (j - i + 1))
        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        # Monotonic increasing stack: when a shorter bar is found, pop taller bars
        # Each popped bar's rectangle extends from its stored start index to current i
        # 'start' tracks how far left the current bar can extend
        # O(n) time, O(n) space — increasing monotonic stack with sentinel
        stack = []  # (index, height) — index = leftmost extent of current bar
        max_area = 0
        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                idx, height = stack.pop()
                max_area = max(max_area, height * (i - idx))
                start = idx
            stack.append((start, h))
        for idx, height in stack:
            max_area = max(max_area, height * (len(heights) - idx))
        return max_area


if __name__ == "__main__":
    s = Solution()
    assert s.largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10
    assert s.largestRectangleArea([2, 4]) == 4
    assert s.largestRectangleArea([1]) == 1
    assert s.largestRectangleArea([6, 2, 5, 4, 5, 1, 6]) == 12
    assert s.largestRectangleArea_brute([2, 1, 5, 6, 2, 3]) == 10
    assert s.largestRectangleArea_brute([2, 4]) == 4
    print("All tests passed.")

"""
# 895. Maximum Frequency Stack

## Problem
Design a stack-like data structure that pushes and pops elements according to
a maximum frequency rule.

Implement the `FreqStack` class:
- `push(val)` — Pushes an integer `val` onto the stack.
- `pop()` — Removes and returns the most frequent element in the stack.
  - If there is a tie for the most frequent element, the element closest to
    the top of the stack (most recently pushed) is removed and returned.

## Examples
```text
Input:
  ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"]
  [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output:
  [null,null,null,null,null,null,null,5,7,5,4]

Explanation:
  After pushes: freq = {5:3, 7:2, 4:1}
  pop() -> 5 (freq 3, most frequent)
  pop() -> 7 (freq 2 tie between 5 and 7; 7 was pushed more recently at freq 2)
  pop() -> 5 (freq 2)
  pop() -> 4 (freq 1 tie; 4 was pushed most recently at freq 1)
```

## Constraints
- `0 <= val <= 10^9`
- At most `2 * 10^4` calls will be made to `push` and `pop`
- It is guaranteed that there will be at least one element in the stack before
  calling `pop`
"""

from collections import defaultdict


class FreqStack:
    """Approach 1: freq map + group map keyed by frequency — O(1) push and pop."""

    def __init__(self):
        self.freq: dict = defaultdict(int)          # val -> frequency
        self.group: dict = defaultdict(list)        # freq -> stack of vals
        self.max_freq: int = 0

    def push(self, val: int) -> None:
        # Increment frequency of val; append to the group for that frequency
        # Update max_freq if this val's frequency is now the highest
        # O(1) — increment freq, append to corresponding group
        self.freq[val] += 1
        f = self.freq[val]
        self.max_freq = max(self.max_freq, f)
        self.group[f].append(val)

    def pop(self) -> int:
        # Pop from the group at max_freq (most recently pushed among most frequent)
        # Decrement val's frequency; if max_freq group is now empty, decrease max_freq
        # O(1) — pop from max_freq group, decrement freq
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return val


if __name__ == "__main__":
    fs = FreqStack()
    for v in [5, 7, 5, 7, 4, 5]:
        fs.push(v)
    assert fs.pop() == 5
    assert fs.pop() == 7
    assert fs.pop() == 5
    assert fs.pop() == 4
    print("All tests passed.")

"""
# 155. Min Stack

## Problem
Design a stack that supports `push`, `pop`, `top`, and retrieving the minimum
element — all in **O(1)** time.

## Operations
- `push(val)` — Push element `val` onto the stack.
- `pop()` — Removes the element on top of the stack.
- `top()` — Gets the top element.
- `getMin()` — Retrieves the minimum element in the stack.

## Examples
```text
Input:
  ["MinStack","push","push","push","getMin","pop","top","getMin"]
  [[],[-2],[0],[-3],[],[],[],[]]
Output:
  [null,null,null,null,-3,null,0,-2]
```

## Constraints
- `-2^31 <= val <= 2^31 - 1`
- Methods `pop`, `top`, and `getMin` will always be called on non-empty stacks
- At most `3 * 10^4` calls will be made to `push`, `pop`, `top`, and `getMin`
"""


class MinStack:
    """Approach 1: Two stacks — main stack + parallel min-tracking stack."""

    def __init__(self):
        self.stack: list = []
        self.min_stack: list = []

    def push(self, val: int) -> None:
        # Push value to main stack; also push new min to min_stack
        # O(1)
        self.stack.append(val)
        self.min_stack.append(min(val, self.min_stack[-1] if self.min_stack else val))

    def pop(self) -> None:
        # Pop from both stacks to keep them in sync
        # O(1)
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        # Peek top of main stack
        # O(1)
        return self.stack[-1]

    def getMin(self) -> int:
        # Peek top of min_stack — always holds current minimum
        # O(1)
        return self.min_stack[-1]


class MinStackTuple:
    """Approach 2: Single stack of (value, current_min) tuples."""

    def __init__(self):
        self.stack: list = []  # each entry: (val, current_min)

    def push(self, val: int) -> None:
        # Push value to main stack; also push new min to min_stack
        # O(1)
        cur_min = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, cur_min))

    def pop(self) -> None:
        # Pop from both stacks to keep them in sync
        # O(1)
        self.stack.pop()

    def top(self) -> int:
        # Peek top of main stack
        # O(1)
        return self.stack[-1][0]

    def getMin(self) -> int:
        # Peek top of min_stack — always holds current minimum
        # O(1)
        return self.stack[-1][1]


if __name__ == "__main__":
    for Cls in (MinStack, MinStackTuple):
        ms = Cls()
        ms.push(-2)
        ms.push(0)
        ms.push(-3)
        assert ms.getMin() == -3
        ms.pop()
        assert ms.top() == 0
        assert ms.getMin() == -2
    print("All tests passed.")

"""
# 901. Online Stock Span

## Problem
Design an algorithm that collects daily price quotes for some stock and returns
the **span** of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of
consecutive days (starting from today and going backwards) for which the stock
price was less than or equal to today's price.

## Examples
```text
Input:
  ["StockSpanner","next","next","next","next","next","next","next"]
  [[],[100],[80],[60],[70],[60],[75],[85]]
Output:
  [null,1,1,1,2,1,4,6]

Explanation:
  next(100) -> 1  (no previous days)
  next(80)  -> 1  (80 < 100)
  next(60)  -> 1  (60 < 80)
  next(70)  -> 2  (70 >= 60, but 70 < 80)
  next(60)  -> 1
  next(75)  -> 4  (75 >= 60, 70, 60, but 75 < 80)
  next(85)  -> 6  (85 >= 75, 60, 70, 60, 80, but 85 < 100)
```

## Constraints
- `1 <= price <= 10^5`
- At most `10^4` calls will be made to `next`
"""


class StockSpanner:
    """Approach 1: Brute force — scan backwards on each call."""

    def __init__(self):
        # O(n) per call, O(n) space
        self.prices: list = []

    def next(self, price: int) -> int:
        # Collapse all previous days with price <= current into one span
        # Stack stores (price, span) pairs; accumulate spans of dominated days
        # O(n) time — linear scan back through history
        self.prices.append(price)
        span = 1
        i = len(self.prices) - 2
        while i >= 0 and self.prices[i] <= price:
            span += 1
            i -= 1
        return span


class StockSpannerOptimal:
    """Approach 2: Monotonic stack — O(1) amortized per call."""

    def __init__(self):
        self.stack: list = []  # (price, span)

    def next(self, price: int) -> int:
        # Collapse all previous days with price <= current into one span
        # Stack stores (price, span) pairs; accumulate spans of dominated days
        # O(1) amortized — collapse dominated entries into accumulated span
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span


if __name__ == "__main__":
    for Cls in (StockSpanner, StockSpannerOptimal):
        sp = Cls()
        assert sp.next(100) == 1
        assert sp.next(80) == 1
        assert sp.next(60) == 1
        assert sp.next(70) == 2
        assert sp.next(60) == 1
        assert sp.next(75) == 4
        assert sp.next(85) == 6
    print("All tests passed.")

"""
# 71. Simplify Path

## Problem
Given an absolute path for a Unix-style file system, which begins with a
slash `'/'`, transform this path into its simplified canonical path.

Rules:
- A single period `'.'` refers to the current directory.
- A double period `'..'` refers to the parent directory.
- Multiple consecutive slashes are treated as a single slash.
- Any other string is a valid directory or file name.

The canonical path must:
- Start with a single slash `'/'`
- Not end with a trailing slash (unless it is the root)
- Not have consecutive slashes
- Not contain `.` or `..`

## Examples
```text
Input:  path = "/home/"
Output: "/home"

Input:  path = "/../"
Output: "/"

Input:  path = "/home//foo/"
Output: "/home/foo"

Input:  path = "/a/./b/../../c/"
Output: "/c"
```

## Constraints
- `1 <= path.length <= 3000`
- `path` consists of English letters, digits, period `'.'`, slash `'/'`, or
  underscore `'_'`
- `path` is a valid absolute Unix path
"""


class Solution:
    def simplifyPath(self, path: str) -> str:
        # Split on '/' to get path components; skip empty strings and '.'
        # '..' pops the last directory from stack (go up one level)
        # Join remaining stack with '/' and prepend root '/'
        # O(n) time, O(n) space — split on '/', process with stack
        stack = []
        for part in path.split("/"):
            if part == "..":
                if stack:
                    stack.pop()
            elif part and part != ".":
                stack.append(part)
        return "/" + "/".join(stack)


if __name__ == "__main__":
    s = Solution()
    assert s.simplifyPath("/home/") == "/home"
    assert s.simplifyPath("/../") == "/"
    assert s.simplifyPath("/home//foo/") == "/home/foo"
    assert s.simplifyPath("/a/./b/../../c/") == "/c"
    assert s.simplifyPath("/") == "/"
    print("All tests passed.")

"""
# 20. Valid Parentheses

## Problem
Given a string `s` containing only the characters `'('`, `')'`, `'{'`, `'}'`,
`'['`, and `']'`, determine if the input string is valid.

A string is valid if:
1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

## Examples
```text
Input:  s = "()"
Output: true

Input:  s = "()[]{}"
Output: true

Input:  s = "(]"
Output: false

Input:  s = "([)]"
Output: false

Input:  s = "{[]}"
Output: true
```

## Constraints
- `1 <= s.length <= 10^4`
- `s` consists of parentheses only: `'()[]{}'`
"""


class Solution:
    def isValid(self, s: str) -> bool:
        # Push opening brackets; on closing bracket, check top matches
        # Stack empty at end means all brackets were properly closed
        # O(n) time, O(n) space — stack-based bracket matching
        stack = []
        match = {")": "(", "}": "{", "]": "["}
        for ch in s:
            if ch in match:
                if not stack or stack[-1] != match[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
        return not stack


if __name__ == "__main__":
    s = Solution()
    assert s.isValid("()") is True
    assert s.isValid("()[]{}") is True
    assert s.isValid("(]") is False
    assert s.isValid("([)]") is False
    assert s.isValid("{[]}") is True
    assert s.isValid("") is True
    print("All tests passed.")