Problem 🤔

Imagine a literal stack of plates. If the stack gets too high, it’ll fall!

So when stacks get too high we will start a new stack.

Let’s impement a class StackSet. This class will be composed of a few stacks. We’ll move on to the next stack when we surpass a threshold of items in a stack.

push and pop should behave exactly like a regular stack. Abstract the underlying logic from the user.

Real World Applications 🌎

Honestly, the gif above explains everything!

More realistically — this is a type of partitioning we can do on a larger data set. Asymptotically, it would be the same, but realistically, we could make the latency much lower by searching specific partitions.

The Finer Details 🔎

How will we represent a set of stacks? We can use a list of list. Each sublist represents a stack.

Additionally, each stack can’t run infinitley, so let’s define a capacity. This will represent the max amount of items we are willing to support per stack.

Now for push. So let’s always push on the “latest” stack being used. If we reach the threshold we can simply add another stack.

How about pop? A little tricker — if we’re popping off the last element of the current stack, we need to make sure to remove that stack as well.

Solution 💡

Complexity Analysis 🧮

Time Complexity

O(1)

No extra operations for push and pop.

Space Complexity

O(n)

Maintain stack with max n elements.

Follow up — implement popAt

Implement popAt(i: int), which performs a pop operation on the i-th stack.

There’s one complication that we need to support here. Let’s assume that we’re trying to pop an item off the i-th stack, such that 0 < i < len(self.stacks). This would mean that now the i-th stack is not at max capacity! So we need to “rebalance” the stacks. The easiest way to do that is to pop off (or bubble off) the last element off every stack k >> i. In essence, we are shifting the top element off of every stack once to the left.

Complexity Analysis 🧮

Let’s anaylyze the complexity for the popAt(i) function.

Time Complexity

O(n)

We may need to shift n elements in the worst case.

Space Complexity

O(1)

No extra space required for this algorithm, just our maintenance which is factored in the time complexity.

Takeaways 🎉🥳

• This can be tricky to code in an interview setting! Be careful with indexes and confirming they are valid / inbounds!

Resources 📚

Cracking the Coding Interview, 3.3, Stack of Plates