Implement stack variants and path-sum check

Coding tasks

Solve the following algorithmic problems.

1) MinStack

Design a stack supporting:

• push(x), pop(), top()
• getMin() returning the minimum element currently in the stack

All operations should run in O(1) time.

2) MaxStack

Design a stack supporting:

• push(x), pop(), top()
• peekMax() returning the maximum element currently in the stack
• popMax() removing and returning the maximum element (if multiple maxima exist, remove the one closest to the top)

State expected time complexities and trade-offs.

3) Streaming median (data stream)

Given a very large stream of integers, support inserting numbers and querying the current median at any time.

4) Tree path sum with upward-only path

Given a binary tree with positive integer node values and an integer target, determine whether there exists a single-direction path that starts at any node and only moves upward to parent nodes such that the sum of the nodes on that path equals target.

Return true/false.

Include any reasonable constraints you assume (e.g., number of nodes, value ranges) and handle edge cases (single node, skewed tree, large target).

MinStack — O(1) getMin

Design a stack that supports push(x), pop(), top(), and getMin() (return the current minimum), all in O(1) time.

To make this executable, implement a driver minStack(ops, args) that replays a sequence of operations. ops is a list of method-name strings — the first is always "MinStack" (the constructor) — and args is a parallel list where args[i] is the argument list for ops[i] ([x] for push, [] otherwise). Return a list the same length as ops: the result of each call, using null/None for the constructor and for void operations (push).

Assume pop/top/getMin are only called on a non-empty stack and -10^9 <= x <= 10^9.

Constraints

• 1 <= number of operations <= 10^4
• -10^9 <= x <= 10^9
• pop, top, getMin are only called on a non-empty stack
• The first op is always the constructor 'MinStack'

Examples

Example 1

Input: (['MinStack','push','push','push','getMin','pop','top','getMin'], [[],[-2],[0],[-3],[],[],[],[]])
Output: [None, None, None, None, -3, -3, 0, -2]

Explanation: Push -2,0,-3. getMin -> -3. Pop -3. top -> 0. getMin -> -2.

Example 2

Input: (['MinStack','push','getMin','top','pop'], [[],[5],[],[],[]])
Output: [None, None, 5, 5, 5]

Explanation: Single element: min, top, and pop all return 5.

Hints

1. Keep a second stack that stores, at each level, the minimum of all elements at or below it.
2. On push, the new running minimum is min(x, previous running minimum).
3. Because the auxiliary stack mirrors the main stack, getMin is just its top.

MaxStack — peekMax and popMax

Design a stack supporting push(x), pop(), top(), peekMax() (return the current maximum), and popMax() (remove and return the maximum; if several elements equal the maximum, remove the one closest to the top).

Implement a driver maxStack(ops, args) that replays operations the same way as the MinStack driver: ops[0] is the constructor "MaxStack", args[i] is the argument list for ops[i]. Return the list of results (None for the constructor and for void operations push).

A straightforward implementation gives O(n) for peekMax/popMax; a balanced-BST + doubly-linked-list approach achieves O(log n).

Constraints

• 1 <= number of operations <= 10^4
• -10^9 <= x <= 10^9
• pop, top, peekMax, popMax are only called on a non-empty stack
• popMax removes the topmost occurrence when the maximum is duplicated

Examples

Example 1

Input: (['MaxStack','push','push','push','top','popMax','top','peekMax','pop','top'], [[],[5],[1],[5],[],[],[],[],[],[]])
Output: [None, None, None, None, 5, 5, 1, 5, 1, 5]

Explanation: Stack [5,1,5]. top -> 5. popMax removes the TOP 5 -> 5, leaving [5,1]. top -> 1. peekMax -> 5. pop -> 1. top -> 5.

Example 2

Input: (['MaxStack','push','peekMax','popMax','push','top'], [[],[7],[],[],[3],[]])
Output: [None, None, 7, 7, None, 3]

Explanation: Push 7. peekMax/popMax -> 7 (now empty). Push 3. top -> 3.

Hints

1. The simplest correct approach scans the list for the maximum on demand.
2. For popMax with duplicates, scan from the TOP downward and delete the first match so you remove the occurrence closest to the top.
3. To reach O(log n), pair an ordered multiset (TreeMap of value -> stack of node ids) with a doubly linked list so you can delete an interior node in O(1) once located.

Streaming median (data stream)

Support inserting integers from a large stream and querying the current median at any time. Implement a driver medianFinder(ops, args) where ops[0] is the constructor "MedianFinder", addNum carries [x], and findMedian carries []. Return the list of results: None for the constructor and for addNum, and a float median for each findMedian.

The median of an even-sized set is the average of the two middle values (so always return a float, e.g. 42.0, 1.5).

Constraints

• 1 <= number of operations <= 10^5
• -10^9 <= x <= 10^9
• findMedian is only called after at least one addNum
• Even-sized median is the average of the two middle elements (return a float)

Examples

Example 1

Input: (['MedianFinder','addNum','addNum','findMedian','addNum','findMedian'], [[],[1],[2],[],[3],[]])
Output: [None, None, None, 1.5, None, 2.0]

Explanation: After {1,2}: median (1+2)/2 = 1.5. After {1,2,3}: median = 2.0.

Example 2

Input: (['MedianFinder','addNum','findMedian'], [[],[42],[]])
Output: [None, None, 42.0]

Explanation: Single element: median is that element as a float.

Hints

1. Maintain two heaps: a max-heap of the smaller half and a min-heap of the larger half.
2. Keep their sizes balanced so they differ by at most 1; the small half holds the extra element when the count is odd.
3. If sizes are equal the median is the average of both heap tops; otherwise it is the top of the larger (small) half.

Tree path sum — upward-only path

Given a binary tree of positive integers and an integer target, determine whether there exists a single-direction path that starts at any node and moves only upward (toward the root, through parent pointers) whose node values sum to target. Return true/false.

The tree is given by two parallel arrays so it is serializable: values[i] is node i's value, and parent[i] is the index of node i's parent (or -1 if node i is the root). A path is any node followed by a contiguous chain of its ancestors (length >= 1).

Constraints

• 0 <= number of nodes <= 10^4
• All node values are positive integers (1 <= value <= 10^9)
• parent[i] is a valid index < i's... not required, but -1 marks the root
• 1 <= target <= 10^14
• An empty tree returns false

Examples

Example 1

Input: ([5, 3, 8, 1], [-1, 0, 0, 1], 9)
Output: True

Explanation: Node 3 (value 1) -> node 1 (value 3) -> node 0 (value 5) sums to 1+3+5 = 9.

Example 2

Input: ([5, 3, 8, 1], [-1, 0, 0, 1], 8)
Output: True

Explanation: Node 1 (value 3) -> node 0 (value 5) sums to 8; also single node 2 has value 8.

Hints

1. An upward path is just a node plus a contiguous run of its parents — try each node as the path's lower endpoint.
2. Walk from a start node up through parent pointers, accumulating the sum.
3. Because all values are positive, the running sum is monotincreasing — stop early (break) once it exceeds target.