Design a Stack With Increment Operation

Medium

Cloudflare

4 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

Design a Stack With Increment Operation

Medium

Cloudflare

4 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 the size of `maxSize`, and the values of `val` and `k` in the `increment` operation?
What should happen if `k` is larger than the current stack size? Should I increment all elements in the stack or just the bottom `k`?
Will there be multiple calls to `push`, `pop`, and `increment` after the stack reaches its maximum size?
Is `maxSize` guaranteed to be a non-negative integer?
Are we optimizing for space or time complexity, given the potential trade-offs between using a lazy propagation approach versus eagerly updating the stack during the increment operation?

Brute Force Solution

Approach

We need to create a special stack that can also increase the values of existing items. A brute force method would directly implement each operation as simply as possible, without any clever tricks or optimizations.

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

To push a new number onto the stack, just add it to the top of the stack.
To remove the top number, simply take it off the top of the stack.
To increment the bottom numbers, go through each of those numbers from the bottom up and add the given value to them. If there are fewer numbers in the stack than what needs to be incremented, then just increment the ones that exist.

Code Implementation

class CustomStack:

    def __init__(self, max_size):
        self.stack = []
        self.max_size = max_size

    def push(self, value):
        if len(self.stack) < self.max_size:
            self.stack.append(value)

    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            return -1

    def increment(self, number_of_elements, value):
        # Determine how many elements to increment
        increment_range = min(number_of_elements, len(self.stack))

        # Iterate through the bottom elements of the stack
        for index in range(increment_range):
            # Increment each element within the range.
            self.stack[index] += value

Big(O) Analysis

Time Complexity

O(k) – The push and pop operations take constant time, O(1), as they simply involve adding or removing an element from the top of the stack. The increment operation iterates through the bottom k elements of the stack, where k is the number of elements to increment. Therefore, the increment operation takes O(k) time, where k is a parameter of the increment function, independent of the total number of elements 'n' in the stack. If k can grow proportionally to n, then increment will be O(n). Otherwise, the complexity depends on the value of k.

Space Complexity

O(1) – The brute force method described operates directly on the stack's underlying data structure. The push and pop operations don't require any auxiliary space. The increment operation, while iterating through stack elements, modifies them in place and doesn't create any new data structures to store intermediate results or temporary copies. Therefore, the space complexity is constant, independent of the number of elements N in the stack.

Optimal Solution

Approach

We need to design a special stack that can not only push and pop values, but also increment several of its bottom elements. The clever idea is to avoid changing many stack values individually when incrementing; instead, we store increment amounts separately for efficiency.

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

First, create two containers. One will hold the stack's values, like a normal stack. The other will hold the increment values corresponding to each element in the stack.
When pushing a new value onto the stack, also push a 'zero' into the increment container. This means, initially, the new value doesn't need to be incremented by anything.
When popping a value, retrieve both the stack value and its corresponding increment value. Add the increment to the stack value and return the result. Also, if there are any values underneath in the stack, add current increment value to the item underneath the top item.
For the increment operation, take the number of elements to increment and the increment value. Add the increment value to the corresponding element in the increment container. Elements beyond the specified number of elements are not affected.
By storing increments separately, we can apply increments to many elements quickly, without needing to modify each individual stack value right away.

Code Implementation

class CustomStack:

    def __init__(self, max_size: int):
        self.max_size = max_size
        self.stack_values = []
        self.increment_values = []

    def push(self, value: int) -> None:
        if len(self.stack_values) < self.max_size:
            self.stack_values.append(value)
            # Initialize increment value to 0 for new element
            self.increment_values.append(0)

    def pop(self) -> int:
        if not self.stack_values:
            return -1

        stack_index = len(self.stack_values) - 1
        value_to_pop = self.stack_values.pop()
        increment_to_pop = self.increment_values.pop()

        value_to_return = value_to_pop + increment_to_pop

        # Propagate increment to the element below.
        if self.increment_values:
            self.increment_values[-1] += increment_to_pop

        return value_to_return

    def increment(self, number_of_elements: int, value: int) -> None:
        # Increment only the bottom 'number_of_elements' elements
        number_of_elements_to_inc = min(number_of_elements, len(self.stack_values))

        if number_of_elements_to_inc > 0:
            # Apply increment to the appropriate element.
            self.increment_values[number_of_elements_to_inc - 1] += value

Big(O) Analysis

Time Complexity

O(k) – The push operation involves appending to both the stack and the increments array, which takes O(1) time. The pop operation also involves popping from both the stack and the increments array. Additionally, it adds the top increment value to the element beneath it, which takes O(1). The increment operation adds a value to the increments array at a specific index, up to k elements from the bottom of the stack, where k is the number of elements to increment. Therefore, the increment operation takes O(k) time, as it iterates through a portion of the array to modify the corresponding increment values.

Space Complexity

O(N) – The solution uses two containers to store data. One container stores the stack's values, and the other stores the increment values corresponding to each element in the stack. Both containers grow linearly with the number of elements pushed onto the stack. Therefore, if N is the maximum number of elements ever present in the stack, the auxiliary space used is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
maxSize is zero	The CustomStack should be initialized but `push` operations will have no effect.
Pushing more elements than maxSize allows	Only the first maxSize elements should be stored; subsequent `push` calls should be ignored.
Popping from an empty stack	`pop` should return -1 if the stack is empty.
Incrementing with k = 0	The increment operation should have no effect as no elements are incremented.
Incrementing with k larger than the stack size	All elements in the stack should be incremented by val.
Large val during increment causing integer overflow	Use a data type (e.g., long) that can accommodate larger numbers or perform overflow checks and handle appropriately (e.g. throwing exception or clamping).
A sequence of pushes, pops, and increments that leave the stack empty then followed by an increment	Increment should have no effect if the stack is empty after the pop sequence.
maxSize is a very large number (close to the integer limit)	Ensure memory allocation doesn't exceed available resources, potentially leading to program crashes due to OOM or other issues; it might be necessary to consider alternative data structures or approaches if scalability is crucial.