Two Stacks in One Array

Problem

Implement two stacks inside one fixed-size array, growing toward each other from opposite ends.

stack_ids[i] is 0 or 1, operations[i] is "push", "pop", "top", "size", or "is_full", and values[i] is the pushed value. Stack 0 grows from index 0 upward while stack 1 grows from index capacity-1 downward, and a push fails when no free slot remains. push records a boolean, pop and top record a value or None, size records an int, and is_full records a boolean.

Return the list of recorded results.

Hint

The stacks meet when top0 + 1 equals top1; track a top index for each end.

Test cases

case 1

in: [4,[0,1,0,1,0,1,0,1,0,0,1],["push","push","push","push","size","size","top","top","is_full","pop","pop"],[1,10,2,20,0,0,0,0,0,0,0]]

expected: [true,true,true,true,2,2,2,20,true,2,20]

case 2

in: [1,[0,1,0,0],["push","push","pop","pop"],[5,6,0,0]]

expected: [true,false,5,null]

case 3

in: [2,[0,1],["pop","top"],[0,0]]

expected: [null,null]

case 4

in: [3,[0,0,1,0,1,1,0],["push","push","push","is_full","pop","size","size"],[1,2,9,0,0,0,0]]

expected: [true,true,true,true,9,0,2]

Starter codePython

def two_stacks_one_array(capacity, stack_ids, operations, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor