LeetCode Solutions Blog

Design a Stack With Increment Operation

Number: 1497

Difficulty: Medium

Paid? No

Problem Description

Design a stack that supports the usual push and pop operations along with an increment operation that adds a given value to the bottom k elements. The stack has a maximum size, and if it’s full, push operations should be ignored.

Key Insights

Use a normal stack data structure to store the elements.
To perform the increment operation efficiently, avoid iterating over the bottom k elements every time by using a lazy propagation technique.
Maintain an auxiliary array "increments" to track pending increments for each element.
When popping an element, propagate its pending increment to the next element in the stack.

Space and Time Complexity

Time Complexity: O(1) per operation (push, pop, inc)
Space Complexity: O(maxSize), to hold the stack and the auxiliary increment array

Solution

We implement the required operations by leveraging two arrays:

The primary stack to store values.
An auxiliary "increments" array of the same size as the stack that keeps track of pending increments.

For the increment operation, instead of updating the bottom k elements directly (which would take O(k) time), we add the increment value to the appropriate index in the increments array. When an element is popped, we add its pending increment to it and propagate the pending increment to the next element. This lazy propagation ensures that each operation runs in constant time.

Code Solutions

# Python solution with line-by-line comments
class CustomStack:
    def __init__(self, maxSize: int):
        # Initialize the stack with a maximum size and an increments array to hold pending increments
        self.maxSize = maxSize
        self.stack = []
        self.increments = [0] * maxSize

    def push(self, x: int) -> None:
        # Only push if the stack size is less than the maximum size
        if len(self.stack) < self.maxSize:
            self.stack.append(x)

    def pop(self) -> int:
        if not self.stack:
            # Return -1 if the stack is empty
            return -1
        i = len(self.stack) - 1  # Get index of the top element
        # If this is not the bottom element, propagate the increment to the next element
        if i > 0:
            self.increments[i - 1] += self.increments[i]
        # Pop the element and add its pending increment
        res = self.stack.pop() + self.increments[i]
        # Reset the increment for this position
        self.increments[i] = 0
        return res

    def increment(self, k: int, val: int) -> None:
        # Determine the index for the last element among the bottom k elements
        n = len(self.stack)
        if n:
            # Only update the last index in the bottom k segment
            idx = min(k, n) - 1
            self.increments[idx] += val

# Example usage:
# cs = CustomStack(3)
# cs.push(1)
# cs.push(2)
# print(cs.pop())  # Expected output: 2