Design a Stack With Increment Operation

#5 Most AskedMedium

Design a Stack With Increment Operation #5 Most Asked

Medium

Cloudflare

22 views

Topics:

ArraysStacks

Design a stack that supports increment operations on its elements.

Implement the CustomStack class:

CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack.
void push(int x) Adds x to the top of the stack if the stack has not reached the maxSize.
int pop() Pops and returns the top of the stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack stk = new CustomStack(3); // Stack is Empty []
stk.push(1);                          // stack becomes [1]
stk.push(2);                          // stack becomes [1, 2]
stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
stk.push(2);                          // stack becomes [1, 2]
stk.push(3);                          // stack becomes [1, 2, 3]
stk.push(4);                          // stack still [1, 2, 3], Do not add another elements as size is 4
stk.increment(5, 100);                // stack becomes [101, 102, 103]
stk.increment(2, 100);                // stack becomes [201, 202, 103]
stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes [201]
stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes []
stk.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

1 <= maxSize, x, k <= 1000
0 <= val <= 100
At most 1000 calls will be made to each method of increment, push and pop each separately.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `maxSize`? Can it be zero or negative?
What are the valid ranges for the integer `x` pushed onto the stack and the `val` used in the `increment` operation? Can they be negative or zero?
If `pop()` is called on an empty stack, what should happen? Should it return a specific value like -1 or `None`, or should it throw an exception?
If `increment(k, val)` is called when `k` is greater than the current number of elements in the stack, should it increment all existing elements, or should it only increment up to the number of elements present?
What should the `increment` operation do if the stack is empty or if `k` is less than or equal to 0?

Brute Force Solution

Approach

We can simulate the stack's behavior directly by keeping track of each element's current value. When an increment operation happens, we can re-calculate the final value for all affected elements.

Here's how the algorithm would work step-by-step:

Imagine you have a list of numbers representing the stack.
When you add a new number to the stack, just add it to the end of your list.
When you need to peek at the top number, just look at the very last number in your list.
When you need to remove the top number, just take the last number off your list.
When you need to increment some of the bottom numbers, go through each of those numbers in your list from the bottom up to the specified limit.
For each of those numbers, add the increment amount to its current value.
Keep doing these operations on your list, and that will show you what the stack would look like and how its top element would behave.

Code Implementation

class CustomStack:

    def __init__(self, maxSize):
        self.stack_elements = []
        self.maximum_size = maxSize

    def push(self, x):
        # Ensure we do not exceed the maximum allowed size of the stack
        if len(self.stack_elements) < self.maximum_size:
            self.stack_elements.append(x)

    def pop(self):
        # Only pop if there are elements available in the stack
        if self.stack_elements:
            return self.stack_elements.pop()
        return -1

    def increment(self, k, val):
        # Determine the actual number of elements to increment to avoid index out of bounds
        elements_to_increment = min(k, len(self.stack_elements))
        for i in range(elements_to_increment):
            self.stack_elements[i] += val

    def peek(self):
        # Return the top element without removing it, or -1 if the stack is empty
        if self.stack_elements:
            return self.stack_elements[-1]
        return -1

Big(O) Analysis

Time Complexity

O(n) – The push, pop, and peek operations on the simulated stack (a list) take constant time, O(1), as they only involve accessing or modifying the end of the list. The increment operation, however, iterates through a portion of the list up to a specified limit 'k' (where k is at most the current size of the stack, n). In the worst case, this increment operation might traverse all 'n' elements if 'k' is equal to the stack size. Therefore, the dominant cost comes from the increment operation, leading to a time complexity of O(n) in the worst case for that specific operation, and O(n) overall for a sequence of operations that includes an increment of the entire stack.

Space Complexity

O(N) – The solution uses a list to simulate the stack's behavior, directly storing each element. This list grows with the number of elements pushed onto the stack, where N represents the maximum number of elements that can be stored. During the increment operation, we iterate through a portion of this existing list but do not create any new data structures that scale with the input size beyond the primary list itself. Therefore, the auxiliary space complexity is O(N) due to the storage of stack elements.

Optimal Solution

Approach

We can create a stack that supports an increment operation by tracking how much to add to each element. Instead of directly updating every element in the stack when an increment is requested, we defer the addition until it's absolutely necessary, like when we remove an element.

Here's how the algorithm would work step-by-step:

Imagine the stack is built on top of a special kind of foundation that can remember instructions.
When we add a new item, we just place it on top as usual.
When we're asked to increment a range of items, instead of going down and changing each one, we tell the foundation to remember an instruction: 'add this much to all items from this level down to the bottom'. We only store this instruction at the level where the increment starts.
When we remove an item from the top, we first check if the foundation has any instructions for this level. If it does, we apply that instruction to the item being removed, and then pass that instruction down to the level below it, so it's ready for the next item.
We keep doing this, applying any stored increment instructions and passing them down as we remove items from the top.
This way, we only do the actual additions when we need to retrieve an item, making the increment operation very fast.

Code Implementation

class CustomStack:

    def __init__(self, maxSize):
        self.maximum_stack_size = maxSize
        self.stack_elements = []
        # Deferred increments are stored per element index.
        self.deferred_increments = [0] * maxSize

    def push(self, element_value):
        if len(self.stack_elements) < self.maximum_stack_size:
            self.stack_elements.append(element_value)

    def pop(self):
        if not self.stack_elements:
            return -1

        current_index = len(self.stack_elements) - 1
        increment_to_apply = self.deferred_increments[current_index]

        # Pass down the increment to the element below if it exists.
        if current_index > 0:
            self.deferred_increments[current_index - 1] += increment_to_apply

        # Reset the increment for the current element as it's being processed.
        self.deferred_increments[current_index] = 0
        return self.stack_elements.pop() + increment_to_apply

    def increment(self, lower_bound_index, increment_value):
        # Only apply increment if the lower bound is within stack limits.
        if lower_bound_index < len(self.stack_elements):
            self.deferred_increments[min(lower_bound_index, len(self.stack_elements) - 1)] += increment_value

Big(O) Analysis

Time Complexity

O(1) – The push operation involves adding an element to the end of a list and potentially adding a zero to the increment array, both constant time operations. The pop operation involves checking and applying any pending increments from the increment array, which is a constant time operation as it only affects the top element. The increment operation involves storing the increment value at a specific index in the increment array, which is also a constant time operation. Since each operation takes a fixed amount of time regardless of the number of elements in the stack, the time complexity is O(1).

Space Complexity

O(N) – The solution uses an auxiliary array, let's call it 'increments', to store the increment values. This array is of the same size as the maximum capacity of the stack, N. Each element in this 'increments' array stores the pending increment for the corresponding stack element. Therefore, the auxiliary space complexity is directly proportional to the maximum size of the stack, N. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Pushing to a full stack	The push operation should simply do nothing and not add the element to maintain the maxSize constraint.
Popping from an empty stack	The pop operation should return a sentinel value (e.g., -1) or throw an exception to indicate an invalid operation.
Incrementing more elements than present in the stack (k > current stack size)	The increment operation should apply to all existing elements in the stack if k exceeds the current number of elements.
Incrementing zero or a negative number of elements (k <= 0)	The increment operation should have no effect if k is zero or negative.
Incrementing with a zero or negative value (val == 0 or val < 0)	The increment operation should correctly add zero or the negative value to the specified bottom elements.
Stack with maxSize of 0	The stack should behave as if it can never hold any elements, with push operations always failing and pop operations always returning a sentinel.
Multiple consecutive push and pop operations	The underlying data structure must efficiently handle the dynamic resizing and indexing required for these mixed operations.
Large number of elements and frequent increment operations	The increment operation's time complexity should be considered to ensure overall efficiency, potentially requiring an optimized approach like lazy propagation.

Pushing to a full stack

How to Handle:

The push operation should simply do nothing and not add the element to maintain the maxSize constraint.

Popping from an empty stack

How to Handle:

The pop operation should return a sentinel value (e.g., -1) or throw an exception to indicate an invalid operation.

Incrementing more elements than present in the stack (k > current stack size)

How to Handle:

The increment operation should apply to all existing elements in the stack if k exceeds the current number of elements.

Incrementing zero or a negative number of elements (k <= 0)

How to Handle:

The increment operation should have no effect if k is zero or negative.

Incrementing with a zero or negative value (val == 0 or val < 0)

How to Handle:

The increment operation should correctly add zero or the negative value to the specified bottom elements.

Stack with maxSize of 0

How to Handle:

The stack should behave as if it can never hold any elements, with push operations always failing and pop operations always returning a sentinel.

Multiple consecutive push and pop operations

How to Handle:

The underlying data structure must efficiently handle the dynamic resizing and indexing required for these mixed operations.

Large number of elements and frequent increment operations

How to Handle:

The increment operation's time complexity should be considered to ensure overall efficiency, potentially requiring an optimized approach like lazy propagation.