49 — LLD: Stack with Increment Operation (LC 1381)

Understanding the Problem

Implement a stack with push(x), pop(), and a new operation increment(k, val) that adds val to the bottom k elements. All operations must be O(1) amortised.

What is the trick?

Doing the naive thing for increment costs O(k). The trick is lazy propagation: store the increment at the top-most affected index and push the debt downward when that element pops. Each increment touches one index; each pop propagates once. Constant time per op.

---

Requirements

Clarifying Questions

You: What is the stack's capacity?

Interviewer: Bounded — maxSize in the constructor. push past the cap is a no-op.

Defined by LeetCode 1381.

You: increment(k, val) when k exceeds current size?

Interviewer: Apply to all current elements.

Clamp k to size.

You: What does pop return when empty?

Interviewer: -1.

Standard problem convention.

You: Thread safety?

Interviewer: Single-threaded is fine for the core. Mention thread-safety if time permits.

Lock around all three operations in the concurrent variant.

Final Requirements

1. new CustomStack(maxSize).
2. push(x) — no-op if full.
3. pop() — return value (with any lazy increments applied) or -1.
4. increment(k, val) — add val to the bottom k elements. O(1) amortised.

Out of scope: negative val, peek, iteration, persistence.

---

Core Entities and Relationships

Entity	Responsibility
CustomStack	Aggregate root. Owns storage and increment ledger.
stack: int[]	Raw values as pushed.
inc: int[]	Parallel ledger; inc[i] is the pending credit at index i.

Why parallel arrays instead of an object per element? Because cache locality matters and the two indexes are always referenced together. In languages with fixed-size arrays it is also faster than allocating per push.

Why not apply increments eagerly? Because increment(k, val) with k = size touches every element — O(n). The lazy scheme confines the cost to the pop.

Design is iterative — there is really one entity here, but the lazy propagation deserves a careful name.

---

Class Design

CustomStack

State:

• stack: int[] — values pushed
• inc: int[] — lazy increment ledger
• maxSize: int

Methods:

• push(x) — no-op if full
• pop() — read value + inc[top], propagate inc[top] to inc[top-1], pop both arrays
• increment(k, val) — inc[min(k, size) - 1] += val

Design principles at play:

• Single Responsibility — one class, one data structure.
• Lazy Propagation — a classic algorithm idea: defer work until it becomes unavoidable.
• Amortised Analysis — increment does O(1) work; that work is later absorbed by pop at O(1).

---

Implementation

Core Logic

Invariant: the true value of the element at index i is stack[i] + inc[i] + inc[i+1] + ... + inc[top].

The lazy trick: when we record increment(k, val), we set inc[k-1] += val. The element at index k-1 owns the debt on behalf of everything below it.

When pop happens:

1. Read value = stack[top] + inc[top].
2. If top > 0, propagate inc[top-1] += inc[top] so the invariant holds for what remains.
3. Remove both arrays' top entries.
4. Return value.

Bad vs Good vs Great

Bad approach: increment loops from 0 to k-1 and adds val.

• O(k). Repeated increments on a long stack are catastrophic.

Good approach: lazy propagation as above.

• O(1) amortised, O(n) memory overhead for the ledger.

Great approach: same logic, but drop the ledger when the stack is empty to reclaim memory, and handle k > size by clamping rather than crashing.

Verification

push(1)   stack=[1]       inc=[0]
push(2)   stack=[1,2]     inc=[0,0]
push(3)   stack=[1,2,3]   inc=[0,0,0]
inc(2,5)  stack=[1,2,3]   inc=[0,5,0]
pop()     -> 3 (stack[2] + inc[2] = 3 + 0)
          propagate inc[2]=0 to inc[1] (no change)
          stack=[1,2]     inc=[0,5]
pop()     -> 7 (stack[1] + inc[1] = 2 + 5)
          propagate inc[1]=5 to inc[0]
          stack=[1]       inc=[5]
pop()     -> 6 (stack[0] + inc[0] = 1 + 5)
          stack=[]        inc=[]

All operations O(1). The invariant holds throughout.

Thread Safety

A single lock around push, pop, increment suffices. The struct is tiny; contention only matters if the stack is shared. For a concurrent multi-producer variant, consider a lock-free array deque, but the amortisation analysis no longer holds cleanly.

Complete Code Implementation

Java

public class CustomStack {
    private final int[] stack;
    private final int[] inc;
    private int top = -1;
    private final int maxSize;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
        this.inc = new int[maxSize];
    }

    public synchronized void push(int x) {
        if (top + 1 < maxSize) {
            stack[++top] = x;
            inc[top] = 0;
        }
    }

    public synchronized int pop() {
        if (top < 0) return -1;
        int value = stack[top] + inc[top];
        if (top > 0) inc[top - 1] += inc[top];
        inc[top] = 0;
        top--;
        return value;
    }

    public synchronized void increment(int k, int val) {
        int idx = Math.min(k, top + 1) - 1;
        if (idx >= 0) inc[idx] += val;
    }
}

C++

#include <mutex>
#include <vector>

class CustomStack {
public:
    explicit CustomStack(int maxSize) : maxSize(maxSize), stack(maxSize), inc(maxSize) {}

    void push(int x) {
        std::lock_guard<std::mutex> g(mu);
        if (top + 1 < maxSize) { stack[++top] = x; inc[top] = 0; }
    }

    int pop() {
        std::lock_guard<std::mutex> g(mu);
        if (top < 0) return -1;
        int value = stack[top] + inc[top];
        if (top > 0) inc[top - 1] += inc[top];
        inc[top] = 0;
        top--;
        return value;
    }

    void increment(int k, int val) {
        std::lock_guard<std::mutex> g(mu);
        int idx = std::min(k, top + 1) - 1;
        if (idx >= 0) inc[idx] += val;
    }

private:
    int maxSize, top = -1;
    std::vector<int> stack, inc;
    std::mutex mu;
};

TypeScript

class CustomStack {
  private stack: number[] = [];
  private inc: number[] = [];
  constructor(private maxSize: number) {}

  push(x: number): void {
    if (this.stack.length < this.maxSize) {
      this.stack.push(x);
      this.inc.push(0);
    }
  }

  pop(): number {
    if (this.stack.length === 0) return -1;
    const i = this.stack.length - 1;
    const value = this.stack[i] + this.inc[i];
    if (i > 0) this.inc[i - 1] += this.inc[i];
    this.stack.pop(); this.inc.pop();
    return value;
  }

  increment(k: number, val: number): void {
    const idx = Math.min(k, this.stack.length) - 1;
    if (idx >= 0) this.inc[idx] += val;
  }
}

---

Extensibility

1. "Support peek"

Add peek() returning stack[top] + inc[top] without propagating. Unchanged complexity.

2. "Support increment of the top K"

Mirror the structure: keep a second ledger incTop where incTop[i] means "debt on everything above index i". pop applies the top ledger eagerly. Symmetric but doubles the memory.

3. "Persist to disk"

Snapshot stack, inc, and top on a checkpoint boundary. On restart, replay a write-ahead log of push/pop/increment operations since the last snapshot.

---

What is Expected at Each Level

Level	Expectations
Mid	Eager increment in a loop; complexity O(k).
Senior / SMTS	Lazy propagation with inc array; O(1) amortised; clear explanation of the invariant.
Staff	Extension to bidirectional increments, durability, discussion of cache locality and branch prediction.