263. Implement N Stacks in a Single Array

You're given a single array of fixed capacity n shared by k independent, numbered stacks (1 through k) - together they may never hold more than n elements in total, however that total is distributed among them. Simulate m operations, each 'PUSH id x' (push x onto stack id) or 'POP id' (pop from stack id). On POP id, print the removed value, or 'EMPTY' if that stack currently has no elements. On PUSH id x, if the stacks collectively already hold n elements, 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 n (array capacity). The second line contains k (number of stacks). The third line contains m (number of operations). Each of the next m lines is either 'PUSH id x' or 'POP id'. Output: For each POP, print the removed value or 'EMPTY'; for each overflowing PUSH, print 'OVERFLOW'. Print one result per line, in the order these occur; successful pushes produce no output.

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

OVERFLOW is a GLOBAL condition on the combined total across every stack - a single stack can legitimately grow to fill the ENTIRE array if all other stacks remain empty, exactly generalizing the two-stack version's flexible boundary.

Generalize 'two stacks in one array' to k independent stacks all sharing a single array's capacity. Brute force: Give each of the k stacks a FIXED, equal share of the array's capacity (n/k slots each) - this works but is wasteful if some stacks need much more room than others while their neighbors stay empty, exactly the same limitation as a naive fixed-split two-stack approach. Optimised: Tracking only the COMBINED total across all k stacks (rather than enforcing per-stack limits) lets any single stack grow to use the ENTIRE array's capacity if the others happen to be empty - a genuinely flexible, efficient use of shared space, generalizing the two-stack technique to any number of stacks.

Represent each of the k stacks with its own separate dynamic array that grows and shrinks as needed, rather than fitting them into one shared fixed array, making each PUSH/POP an amortized O(1) operation on that stack's own list. Separately maintain one shared counter of the total number of elements currently stored across all k stacks; a PUSH only proceeds if this counter is below n (otherwise print OVERFLOW), and a POP on an empty stack's list prints EMPTY. This correctly enforces the shared global capacity n while giving good amortized time, at the cost of the overhead of k separate growable containers instead of one contiguous array. Time: O(1) amortized per operation Space: O(n)

Keep everything in one array of size n, without pre-assigning any fixed region to any stack; whenever a PUSH needs to insert a value for a particular stack, shift the appropriate block of the array to open up a slot exactly at that stack's boundary, keeping every stack's elements contiguous within the shared array at all times (a POP closes the gap by shifting elements back). A shared running total of elements across all stacks is checked against n to decide OVERFLOW. Because inserting or removing a slot in the middle of the array requires shifting all elements past it, each operation can cost up to O(n). Time: O(n) per operation Space: O(1)

Use one array arr of size n to hold all values, a parallel array next of size n threading singly-linked lists through arr's indices, an array top of size k giving the current top index of each stack (or -1 if empty), and a single free-list head pointing to a chain of currently unused indices. To PUSH id x: if the free list is empty print OVERFLOW; otherwise take its head index, store x there, link it above stack id's current top via next, and update top[id]. To POP id: if top[id] is -1 print EMPTY; otherwise remove that index's value, update top[id] to the next node in that stack's chain, and return the freed index to the head of the free list. Every operation touches a constant number of array cells, giving true O(1) time per operation while sharing exactly one physical array among all k stacks. Time: O(1) per operation Space: O(n)

1. Maintain each of the k stacks as its own separate list of values, all backed conceptually by the same shared array. 2. Track ONE combined running total of elements currently stored across ALL k stacks. 3. On a push, if the combined total already equals the array's capacity n, report OVERFLOW; otherwise, push onto the specific requested stack and increment the combined total. 4. On a pop, remove from the specific requested stack (or report EMPTY if that particular stack has nothing) and decrement the combined total.

Time: O(1) per operation, for both push and pop (assuming each stack's own storage, like a dynamic array or linked list, supports O(1) append/remove at its own end). Space: O(n), for the shared capacity across all k stacks combined.

Popping from a stack that is currently empty; pushing when the combined element count across all k stacks already equals n, including when a single stack alone holds all n elements; n, m up to 10^5 for performance.

Be ready to mention the more advanced 'array of k linked lists sharing one free-slot pool' implementation technique (a genuinely single physical array, not k separate logical lists) as the more rigorous, memory-efficient version of this idea, even if a simpler per-stack-list implementation is functionally equivalent for this problem's purposes.