LeetCode 1381 - Design a Stack With Increment Operation

Difficulty: 🟡 Medium
Topics: Array, Stack, Design

Solution

Problem Understanding

This problem requires designing a specialized stack data structure, called CustomStack, that not only supports the usual push and pop operations but also an incremental operation that can increase the value of the bottom k elements by a given amount. In other words, this stack behaves like a standard stack for pushing and popping elements, but it also allows batch modifications on a prefix of the stack efficiently.

The input to the system consists of a maximum stack size maxSize and a series of operations: push(x) adds an element if the stack has not reached its limit, pop() removes the top element (or returns -1 if empty), and increment(k, val) increases the first k elements from the bottom by val. The output is expected only for pop() operations, as push() and increment() return None.

Constraints indicate that maxSize and the number of operations are modest (≤ 1000), which allows for straightforward data structures like lists or slices. However, naive approaches for increment can lead to unnecessary repeated updates if we implement it by looping over elements, motivating a more efficient approach.

Key edge cases include trying to push onto a full stack, popping from an empty stack, or incrementing more elements than currently exist.

Approaches

The brute-force approach is to implement a standard list-backed stack and perform each increment(k, val) operation by iterating over the first k elements. This is correct but inefficient, because each increment takes O(k) time. In the worst case, with repeated increments on a full stack, the solution can reach O(n * k) time, which is acceptable for small inputs but could be optimized.

The optimal approach uses an auxiliary array to defer increments until pop time. Instead of immediately updating the bottom k elements, we maintain an "increment pending" array where each position tracks the total increment that should be applied when that element is popped. When popping, we propagate any pending increment to the next element below. This ensures that push and pop operations remain O(1) and increment also becomes O(1).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k) per increment, O(1) push/pop	O(maxSize)	Directly updates bottom k elements during increment
Optimal	O(1) per operation	O(maxSize)	Uses deferred increment propagation to achieve constant time operations

Algorithm Walkthrough

Initialize a stack with a fixed maximum size and an auxiliary array inc of the same size to track pending increments for each element.
push(x) checks if the stack is full. If not, it appends x to the stack.
pop() removes the top element. Before returning, it applies any pending increment stored for that element. It also propagates the pending increment to the next element below in the stack, if present.
increment(k, val) adds val to the inc array at index min(k, len(stack)) - 1. This defers the increment until the corresponding element is popped.
Each operation maintains the stack invariant: elements in the stack plus their deferred increments equal the effective stack value at any time.

Why it works: By deferring increments, we avoid repeated updates of elements in the middle of the stack. The propagation during pop() ensures that increments are correctly applied in order, maintaining correctness while reducing time complexity.

Python Solution

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.inc = [0] * maxSize
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        if len(self.stack) < self.maxSize:
            self.stack.append(x)

    def pop(self) -> int:
        if not self.stack:
            return -1
        index = len(self.stack) - 1
        if index > 0:
            self.inc[index - 1] += self.inc[index]
        res = self.stack.pop() + self.inc[index]
        self.inc[index] = 0
        return res

    def increment(self, k: int, val: int) -> None:
        if self.stack:
            index = min(k, len(self.stack)) - 1
            self.inc[index] += val

This Python implementation uses a list stack for storage and an array inc for deferred increments. push simply appends if space allows. pop applies the deferred increment and propagates it downwards. increment updates only one element in inc to defer the operation.

Go Solution

type CustomStack struct {
    stack   []int
    inc     []int
    maxSize int
}

func Constructor(maxSize int) CustomStack {
    return CustomStack{
        stack:   make([]int, 0, maxSize),
        inc:     make([]int, maxSize),
        maxSize: maxSize,
    }
}

func (this *CustomStack) Push(x int) {
    if len(this.stack) < this.maxSize {
        this.stack = append(this.stack, x)
    }
}

func (this *CustomStack) Pop() int {
    n := len(this.stack)
    if n == 0 {
        return -1
    }
    if n > 1 {
        this.inc[n-2] += this.inc[n-1]
    }
    res := this.stack[n-1] + this.inc[n-1]
    this.stack = this.stack[:n-1]
    this.inc[n-1] = 0
    return res
}

func (this *CustomStack) Increment(k int, val int) {
    n := len(this.stack)
    if n == 0 {
        return
    }
    index := k
    if k > n {
        index = n
    }
    this.inc[index-1] += val
}

In Go, slices are used for dynamic storage, with an auxiliary slice inc for deferred increments. The Push and Pop functions handle slice resizing safely, and propagation works identically to the Python version.

Worked Examples

For the input:

stk = CustomStack(3)
stk.push(1)   -> [1], inc=[0,0,0]
stk.push(2)   -> [1,2], inc=[0,0,0]
stk.pop()     -> returns 2, stack=[1], inc=[0,0,0]
stk.push(2)   -> [1,2], inc=[0,0,0]
stk.push(3)   -> [1,2,3], inc=[0,0,0]
stk.push(4)   -> ignored (stack full)
stk.increment(5,100) -> inc=[0,0,100]
stk.increment(2,100) -> inc=[0,100,100]
stk.pop()     -> returns 103 (3 + 100), propagate 100 down -> inc=[100,200,0], stack=[1,2]
stk.pop()     -> returns 202 (2 + 200), propagate 100 -> inc=[300,0], stack=[1]
stk.pop()     -> returns 301 (1 + 300), stack=[], inc=[0,0,0]
stk.pop()     -> returns -1

State propagation ensures correctness while avoiding O(k) operations for increments.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per operation	All `push`, `pop`, and `increment` use constant time due to deferred increments
Space	O(maxSize)	Two arrays of size `maxSize` store elements and deferred increments

This approach is optimal for the constraints given, ensuring fast operations and minimal memory overhead.

Test Cases

# Example from problem statement
stk = CustomStack(3)
stk.push(1)
stk.push(2)
assert stk.pop() == 2  # pop top element
stk.push(2)
stk.push(3)
stk.push(4)  # ignored
stk.increment(5,100)
stk.increment(2,100)
assert stk.pop() == 103
assert stk.pop() == 202
assert stk.pop() == 201
assert stk.pop() == -1

# Edge case: pop from empty stack
stk = CustomStack(2)
assert stk.pop() == -1

# Increment more than stack size
stk.push(5)
stk.push(10)
stk.increment(5, 5)
assert stk.pop() == 15
assert stk.pop() == 10

# Push to maxSize
stk.push(1)
stk.push(2)
stk.push(3)  # ignored if maxSize=2
assert stk.pop() == 2

Test	Why
Example	Validates normal operations and deferred increments
Pop empty	Ensures `-1` returned for empty stack
Increment > size	Checks increment does not overflow stack bounds
Push to maxSize	Ensures stack respects maximum size

Edge Cases

Popping from an empty stack: If the stack is empty, pop() should return -1. The implementation explicitly checks the stack length to handle this correctly.
Increment more elements than exist: Calling increment(k, val) with k larger than the current stack size should only affect existing elements. Using min(k, len(stack)) ensures correctness.
**Pushing when stack