276. Implement n Queues in a Single Array

You're given a single array of fixed capacity n shared by k independent, numbered queues (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 'ENQUEUE id x' (enqueue x into queue id) or 'DEQUEUE id' (dequeue the front of queue id). On DEQUEUE id, print the removed value, or 'EMPTY' if that queue currently has no elements. On ENQUEUE id x, if the queues collectively already hold n elements, print 'OVERFLOW' instead of enqueuing; otherwise enqueue silently (no output). Print one result per line, in the order DEQUEUE/overflowing-ENQUEUE operations occurred.

Input: The first line contains n, the shared array's total capacity. The second line contains k, the number of independent queues. The third line contains m, the number of operations. Each of the next m lines contains one operation: 'ENQUEUE id x' or 'DEQUEUE id'. Output: Print one line per DEQUEUE/overflowing-ENQUEUE operation, in order, printing the removed value, 'EMPTY', or 'OVERFLOW'.

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

A single queue is completely free to grow and use the ENTIRE shared capacity if every other queue happens to stay empty - there's no individual, per-queue cap at all, only the shared combined one.

Share ONE fixed-size array among several independent queues, so the total space used across all of them never exceeds the array's size, however that usage is distributed. Brute force: Give each of the k queues its own separately-sized fixed array (splitting the total capacity n evenly, say n/k each) - this technically works but wastes space badly whenever usage is uneven across queues (one queue needing more room than its fixed share, while another sits mostly empty). Optimised: Rather than pre-allocating a fixed slice of the array to each queue, track only a SHARED total count against the shared capacity n, letting any individual queue grow as large as it needs to (using its own independent FIFO structure), as long as the combined total across all queues stays within the shared limit - this is a much more flexible use of the available space than rigid pre-partitioning.

Give each of the k queues its own plain array that gets used like a queue by shifting all remaining elements left whenever the front is dequeued, and maintain one shared counter of the total elements across all queues to check against n before any enqueue. This correctly enforces the shared capacity and allows any distribution among queues, but shifting elements on every dequeue makes each dequeue operation cost time proportional to that queue's current size. Time: O(size of queue) per dequeue, O(1) per enqueue Space: O(n)

Give each queue its own resizable circular buffer (a proper queue with head/tail pointers) so both enqueue and dequeue are O(1) amortized within that queue, while still checking a shared total-count variable against n before allowing an enqueue. This fixes the shifting cost of the brute approach, but the k separate buffers may individually over-allocate capacity, so it doesn't truly implement 'a single shared array' the way the problem intends, only mimics its behavior with separate structures. Time: O(1) amortized per operation Space: O(n)

Allocate exactly one data array of size n plus a parallel 'next' index array to chain elements together as singly linked lists, one chain per queue, and maintain a separate free list threading together all currently-unused slots (initially all n of them). Enqueue pops a slot off the free list, writes the value there, and links it to the tail of that queue's chain; dequeue unlinks the head of a queue's chain and returns its slot to the free list. Every operation is O(1) worst case (not just amortized), and the array truly is shared and split exactly as the problem describes, with zero wasted or over-allocated space beyond the fixed n slots. Time: O(1) per operation Space: O(n + k)

1. Give each of the k queues its own independent tracking of front/rear/order (conceptually its own separate FIFO), while all of them draw from the SAME shared underlying array/capacity. 2. On ENQUEUE for a given queue id, first check whether the COMBINED element count across ALL queues has already reached the shared capacity n - if so, report OVERFLOW. 3. Otherwise, add the new value to that specific queue's own structure, incrementing the shared total count. 4. On DEQUEUE for a given queue id, remove and report that queue's own front value (or EMPTY if that particular queue has none), decrementing the shared total count.

Time: O(1) per ENQUEUE/DEQUEUE operation - each queue's own structure supports instant front/rear access, and checking the shared count against capacity is a single instant comparison. Space: O(n) total, shared flexibly across however many individual queues actually need it at any given moment.

k = n (each queue could combined hold only n elements total, one per id in the extreme); a single queue growing to fill the entire shared capacity while the others stay empty (per the hints); DEQUEUE on an individually-empty queue (print 'EMPTY'); ENQUEUE once the combined total across all queues reaches n (print 'OVERFLOW').

Be ready to explain the key design insight clearly: the constraint is on the COMBINED total across all queues, not a per-queue limit - many candidates initially over-complicate this by trying to give each queue its own separately-bounded capacity.