260. Implement Two Stacks in One Array

You're given a single array of fixed capacity n that must hold two independent stacks (stack 1 growing from one end, stack 2 growing from the other, sharing the space between them). Simulate m operations, each 'PUSH1 x' (push x onto stack 1), 'PUSH2 x' (push x onto stack 2), 'POP1', or 'POP2'. On POP1/POP2, print the removed value, or 'EMPTY' if that stack has no elements. On PUSH1/PUSH2, if the two stacks have collectively filled the entire array (no space at all remains, regardless of how it's distributed between the two), print 'OVERFLOW' instead of pushing; otherwise push silently (no output). Print one result per line, in the order POP/overflowing-PUSH operations occurred.

Input: The first line contains an integer n, the shared array's capacity. The second line contains an integer m, the number of operations. Each of the next m lines contains one operation: 'PUSH1 x', 'PUSH2 x', 'POP1', or 'POP2'. Output: Print one line per POP1/POP2/overflowing-PUSH operation, in order, printing the removed value, 'EMPTY', or 'OVERFLOW'.

1 <= n <= 10^5, 1 <= m <= 10^5

A pop from EITHER stack immediately frees up space the OTHER stack can use, even space 'beyond' where that other stack originally started - the boundary between the two stacks is entirely dynamic, not fixed.

Fit two independent stacks into a single shared array, growing toward each other from opposite ends. Brute force: Split the array into two FIXED halves, one per stack - this works but wastes space if one stack needs more room than its fixed half while the other stays nearly empty, an inefficient use of the shared capacity. Optimised: Growing the two stacks from OPPOSITE ends toward each other (rather than a fixed midpoint split) lets either stack use as much of the total capacity as it needs, as long as their combined size never exceeds the array - a much more flexible and space-efficient use of the shared array.

Use one physical array of size n, initially dividing it at its midpoint: stack 1 grows rightward from index 0 and stack 2 grows leftward from index n-1. When one side's half fills up while the other half still has unused space, shift the dividing boundary by moving one or more existing elements across to free room before completing the push, only reporting 'OVERFLOW' once truly no space remains anywhere in the array. This correctly allows the two stacks to share the full capacity, but the occasional rebalancing shift costs time proportional to how many elements must be moved. Time: O(1) per operation typically, O(n) when a rebalance is triggered Space: O(1) extra (in-place within the array)

Represent stack 1 and stack 2 as two separate dynamically growing lists rather than sharing one physical array, and keep a running combined-size counter. On every PUSH, check whether the combined counter has already reached n before appending to the relevant list (printing 'OVERFLOW' if so); on every POP, remove and print the last element of the relevant list, or 'EMPTY' if it is empty. This is functionally correct and simple to reason about, but it does not actually use a single shared array of fixed capacity as the problem intends, only emulating the capacity limit with a counter. Time: O(1) per operation Space: O(n)

Use a single array of size n with two indices: top1 starting at -1 and growing upward for stack 1, and top2 starting at n and growing downward for stack 2. Before any push, check for overflow with the simple condition top1 + 1 == top2 (meaning the two stacks have collectively met in the middle with no gap left); otherwise write the new value and move the relevant pointer. Because both stacks share the same contiguous space fluidly from opposite ends, no shifting or rebalancing is ever required, and every push/pop is a pure constant-time pointer update. Time: O(1) per operation Space: O(1) extra (in-place within the array)

1. Grow stack 1 from index 0 UPWARD, and stack 2 from index n-1 DOWNWARD - each stack tracks its own 'top' pointer independently. 2. On a push, check if the two stacks' next positions would COLLIDE (the array is genuinely full) - if so, report OVERFLOW; otherwise, push and advance that stack's pointer toward the other. 3. On a pop, remove from the appropriate end and retreat that stack's pointer, freeing up space the OTHER stack can now use.

Time: O(1) per operation. Space: O(n), for the single shared array (versus O(n) split into two separate fixed-size arrays, but used far more flexibly here).

n = 1 (only one of the two stacks can hold anything at a time); POP1/POP2 called on an empty respective stack (print 'EMPTY'); a PUSH once the two stacks have collectively filled the entire array, however unevenly split between them (print 'OVERFLOW', per the hints).

Be ready to explain why OVERFLOW is a condition on the COMBINED size of both stacks (not a fixed per-stack limit) - this flexible boundary is the entire point of sharing one array instead of using two separate ones.