DSA sheet · Stack · Stack-based design pattern

Design Stack With Increment

The last problem of the stack-design pattern. We build a stack with a size limit and one extra method: increment(k, val), which adds val to the bottom k items. The teacher first stores the stack in a fixed array with an index pointer and does the increment with a loop (O(k)). Then she makes increment O(1) with a lazy "pending increment" array: instead of touching every item now, she leaves a note at one spot and passes it down only when a pop actually reaches it. This "do the work later, only when it's needed" idea shows up in many advanced data structures.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run (operation-sequence table) → ⑨ complexity & remember

• Part 0 · Stacks, array stacks and lazy work from scratch
• Part A · Array + index, increment with a loop (O(k))
• Part B · Lazy increment array, everything O(1)
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A pile of plates: add and remove only at the top. Last in, first out (LIFO). push(x) puts x on top, pop() removes and returns the top, peek reads it.

st = []
st.append(1); st.append(2)   # push   -> [1, 2]   (right end = top)
st[-1]                       # peek   -> 2
st.pop()                     # pop    -> 2
if st: st.pop()              # ALWAYS check "not empty" before pop() or [-1]

We draw stacks left = bottom, right = top. The bottom k items are the first k from the left (the oldest k).

A stack inside a fixed-size array

If the stack has a maximum size, we can create an array of exactly that size once and keep an integer idx = "position of the top item". The stack is the part arr[0..idx].

Unlike a plain stack, an array lets us reach any position by index, including the bottom. That's what makes increment possible.

Lazy work and "amortised" vs worst-case cost

Lazy means: don't do a job until someone actually needs its result. If you're told "add 100 to the bottom 1000 items", but nobody ever looks at 999 of them, updating all 1000 right away was wasted work. Instead, leave a small note and apply it later, item by item, as each one is popped.

Amortised O(1) means some calls are slow but the average is constant; worst-case O(1) means every single call is fast. Part B gets worst-case O(1) for every method. Each pop does at most one extra addition (passing the note down), which can't pile up.

Part A · Array + index, increment with a loop

LeetCode 1381

1The question in simple words

Design CustomStack(maxSize):

• push(x): add x on top, but only if the stack has fewer than maxSize items. If it's full, do nothing.
• pop(): remove and return the top. If the stack is empty, return −1.
• increment(k, val): add val to each of the bottom k items. If there are fewer than k items, add val to all of them.

Example: maxSize 3: push 1, push 2, pop → 2, push 2, push 3, push 4 (ignored, full), increment(5, 100), increment(2, 100), pop → 103, pop → 202, pop → 201, pop → −1.

2What the constraints tell us

• 1 ≤ maxSize, x, k ≤ 1000, 0 ≤ val ≤ 100, at most 1000 calls of each method → even O(k) per increment is at most about 10⁶ steps. Part A passes.
• k can be bigger than the number of items (like k = 5 with 3 items). We must clip k to the current size.
• pop on an empty stack is allowed and must return −1, so we must check for empty.

3Intuition

Since the stack has a fixed maximum size, store it in an array of that size with an index pointer to the top. push/pop just move the pointer. For increment, the bottom k items are simply positions 0 … k−1 of the array, so loop over them and add val. Clip the loop to the number of items present.

4Building the logic from the example

push with a size limit

push 1, push 2: stack [1, 2]. pop → 2. push 2, push 3: stack [1, 2, 3]. Now push 4: the stack already has 3 items and maxSize is 3. No room. So push must first check "is it full?" and if yes, just return without doing anything.

increment(5, 100) with only 3 items

Fewer than 5 items → add to all of them. In general the number of items to update is limit = min(k, idx + 1). Here min(5, 3) = 3 → [101, 102, 103].

increment(2, 100)

min(2, 3) = 2 → positions 0 and 1: [201, 202, 103].

pop four times

103, then 202, then 201. Now idx = −1, so the 4th pop returns −1.

5Approach steps

1. Create st = [0] * maxSize and idx = −1.
2. push(x): if idx == maxSize − 1 return; else idx += 1, st[idx] = x.
3. pop(): if idx == −1 return −1; else read st[idx], idx −= 1, return it.
4. increment(k, val): limit = min(k, idx + 1); add val to st[0 … limit−1].

6Code (Python)

class CustomStack:
    def __init__(self, maxSize):
        self.maxSize = maxSize
        self.st = [0] * maxSize     # fixed-size array
        self.idx = -1               # position of the top item; -1 = empty

    def push(self, x):
        if self.idx == self.maxSize - 1:    # full: ignore
            return
        self.idx += 1
        self.st[self.idx] = x

    def pop(self):
        if self.idx == -1:                  # empty
            return -1
        val = self.st[self.idx]
        self.idx -= 1
        return val

    def increment(self, k, val):
        limit = min(k, self.idx + 1)        # can't touch more items than exist
        for i in range(limit):
            self.st[i] += val

7Code line by line

8Dry run: operation-sequence table

The array is drawn with only the live part st[0..idx] (left = bottom, right = top).

9Complexity & remember

• push, pop: O(1).
• increment: O(min(k, size)), which is O(n) in the worst case.
• Space: O(n) for the array. We can't go below this: the values have to be stored somewhere.

Part B · Lazy increment array, everything O(1)

1The question again, with the new goal

Same three methods. Now make increment O(1) too, while keeping push and pop O(1).

2What the constraints tell us now

• We may use one more array of size maxSize. The teacher's rule of thumb: to lower time you often spend some space; here it's 2n instead of n, still linear.
• The only way anyone can see a value is by popping it, and pops always come from the top, one at a time. That's what lets us delay the work.

3Intuition: leave one note at the top of the range, pass it down on pop

The question asks us to add val to the bottom k items, but nobody can see those items until they're popped. If only one pop ever happens, updating all k items was wasted work. So instead of changing values now, write the increase once, as a note, on the highest item of the range. The note means "this item and every item below it still owe +val".

When that item is popped, we add its note to its value and return the sum. Then we pass the note down to the item just below, which now becomes the top. All the items further down will get the note too, one step at a time, as they come up to be popped.

4Building the logic from the example

Keep a second array inc of zeros, the same size as st. State before the increments: st = [1, 2, 3], idx = 2, inc = [0, 0, 0].

increment(5, 100)

The range is the bottom min(5, 3) = 3 items: positions 0 … 2. Its highest position is min(k − 1, idx) = min(4, 2) = 2. Write the note there: inc = [0, 0, 100]. One step, not three.

increment(2, 100)

Highest affected position = min(1, 2) = 1. inc[1] += 100 → inc = [0, 100, 100]. If a note is already there, we add to it; notes stack up.

pop → 103

Answer = st[2] + inc[2] = 3 + 100 = 103 ✓. The note at position 2 also applies to positions 0 and 1, so pass it down one step: inc[1] += 100 → 200. Then clear inc[2] = 0. idx = 1.

pop → 202

st[1] + inc[1] = 2 + 200 = 202 ✓. Pass down: inc[0] += 200 → 200. Clear inc[1]. idx = 0.

pop → 201

st[0] + inc[0] = 1 + 200 = 201 ✓. idx is 0, so there's no item below; nothing to pass. Clear inc[0]. idx = −1.

pop → −1

idx == −1, empty.

5Approach steps

1. Arrays st and inc of size maxSize (inc all zeros), idx = −1.
2. push(x): same as Part A (inc[idx] is already 0 for a fresh slot).
3. increment(k, val): i = min(k − 1, idx); if i ≥ 0 → inc[i] += val.
4. pop(): if empty return −1. Else res = st[idx] + inc[idx]; if idx > 0 → inc[idx − 1] += inc[idx]; inc[idx] = 0; idx −= 1; return res.

6Code (Python)

class CustomStack:
    def __init__(self, maxSize):
        self.maxSize = maxSize
        self.st = [0] * maxSize
        self.inc = [0] * maxSize    # inc[i] = amount still owed by items 0..i
        self.idx = -1

    def push(self, x):
        if self.idx == self.maxSize - 1:
            return
        self.idx += 1
        self.st[self.idx] = x

    def pop(self):
        if self.idx == -1:
            return -1
        i = self.idx
        res = self.st[i] + self.inc[i]      # apply the note now
        if i > 0:
            self.inc[i - 1] += self.inc[i]  # pass it to the item below
        self.inc[i] = 0                     # clear the slot for future pushes
        self.idx -= 1
        return res

    def increment(self, k, val):
        i = min(k - 1, self.idx)            # highest affected position
        if i >= 0:                          # stack might be empty
            self.inc[i] += val

7Code line by line

8Dry run: operation-sequence table

The stored values in st never changed (1, 2, 3). Only the notes moved, and each pop applied exactly what its item was owed.

Yellow = the current top and its note. Read st left = bottom, right = top.

9Complexity & remember (with a counted example)

• push, pop, increment: O(1) each, worst case. pop does one extra addition to pass the note.
• Space: O(2n) = O(n): st and inc.

Counting the saving

maxSize = 1000. Push 1000 items, call increment(1000, 1) 1000 times, then pop all 1000.

The teacher's point: an increment might be followed by only one pop, so updating every item up front can be pure waste. In an interview, the lazy version is the expected answer.

Part C · Revision page

With this problem the stack-design pattern is done. The teacher notes that with these patterns you've covered most of the common stack questions.

s = CustomStack(3)
s.push(1); s.push(2)
print(s.pop())            # 2
s.push(2); s.push(3); s.push(4)   # 4 is ignored
s.increment(5, 100)
s.increment(2, 100)
print(s.pop(), s.pop(), s.pop(), s.pop())   # 103 202 201 -1

Based on this video: Design a Stack With Increment Operation