Design a Stack With Increment Operation

▶

Steps

setup

Initialize CustomStack with maxSize 3

Create an empty stack and an increments array of size 3 initialized to zeros. The stack is empty and ready to accept elements.

💡 Initialization sets up the data structures needed for efficient push, pop, and increment operations.

Line:

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

💡 The increments array will track lazy increments for stack elements by index.

insert

Push 1 onto stack

Since the stack size is less than maxSize, push 1 onto the stack. The stack now contains one element: 1.

💡 Push adds elements to the top of the stack if there is capacity.

Line:

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

💡 Stack grows by appending elements to the end (top).

insert

Push 2 onto stack

Stack size is 1, less than maxSize 3, so push 2 onto the stack. Stack now has elements [1, 2].

💡 Push continues to add elements to the top until maxSize is reached.

Line:

if len(self.stack) < self.maxSize:
    self.stack.append(x)

💡 Stack order is maintained with newest elements at the tail.

delete

Pop top element from stack

Pop the top element (2). Since increments array is all zeros, popped value is 2. Propagate increments if needed (none here).

💡 Pop removes the top element and applies any pending increments lazily.

Line:

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

💡 Increments propagate downwards on pop, but none exist yet.

insert

Push 2 onto stack

Stack size is 1, less than maxSize 3, so push 2. Stack now [1, 2].

💡 Push adds element to top respecting max size.

Line:

if len(self.stack) < self.maxSize:
    self.stack.append(x)

💡 Stack grows again after pop.

insert

Push 3 onto stack

Stack size is 2, less than maxSize 3, so push 3. Stack now [1, 2, 3].

💡 Push continues until maxSize is reached.

Line:

if len(self.stack) < self.maxSize:
    self.stack.append(x)

💡 Stack is now full at maxSize 3.

insert

Attempt to push 4 onto full stack

Stack is full (size 3 == maxSize 3), so push 4 is ignored. Stack remains [1, 2, 3].

💡 Push does nothing if stack is at max capacity.

Line:

if len(self.stack) < self.maxSize:
    self.stack.append(x)

💡 Stack size limit prevents overflow.

expand

Increment bottom 5 elements by 100

Increment operation adds 100 to increments[2] (index min(5,3)-1=2). This means bottom 3 elements will eventually get +100 when popped.

💡 Increment is applied lazily by updating increments array at the limit index.

Line:

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

💡 Lazy increments avoid updating all elements immediately.

expand

Increment bottom 2 elements by 100

Increment operation adds 100 to increments[1] (index min(2,3)-1=1). increments array now has +100 at index 1 and +100 at index 2.

💡 Multiple increments accumulate in increments array at different indices.

Line:

limit = min(k, len(self.stack))
if limit > 0:
    self.inc[limit-1] += val

💡 Increments stack up and will be propagated on pop.

delete

Pop top element (3) with increments

Pop top element at index 2 (value 3). Add increments[2] = 100 to 3, result 103. Propagate increments[2] to increments[1], increments[2] reset to 0.

💡 Pop applies increments lazily and propagates them down the increments array.

Line:

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

💡 Increments propagate downwards to affect remaining elements.

delete

Pop top element (2) with increments

Pop top element at index 1 (value 2). Add increments[1] = 200 (100 + 100 propagated) to 2, result 202. Propagate increments[1] to increments[0], increments[1] reset to 0.

💡 Pop continues to apply and propagate increments down the stack.

Line:

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

💡 Increments accumulate and propagate correctly on multiple pops.

delete

Pop top element (1) with increments

Pop top element at index 0 (value 1). Add increments[0] = 100 (propagated) to 1, result 201. No increments to propagate further. increments[0] reset to 0.

💡 Final pop applies all remaining increments to bottom element.

Line:

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

💡 All increments are applied by the time stack is empty.

delete

Pop from empty stack

Stack is empty, so pop returns -1 indicating no elements to pop.

💡 Pop returns -1 when stack is empty to signal underflow.

Line:

if not self.stack:
    return -1

💡 Edge case handled gracefully.

class CustomStack:
    def __init__(self, maxSize: int):  # STEP 1
        self.stack = []
        self.inc = [0] * maxSize
        self.maxSize = maxSize

    def push(self, x: int) -> None:  # STEP 2,3,5,6,7
        if len(self.stack) < self.maxSize:
            self.stack.append(x)

    def pop(self) -> int:  # STEP 4,10,11,12,13
        if not self.stack:
            return -1
        i = len(self.stack) - 1
        if i > 0:
            self.inc[i-1] += self.inc[i]
        res = self.stack.pop() + self.inc[i]
        self.inc[i] = 0
        return res

    def increment(self, k: int, val: int) -> None:  # STEP 8,9
        limit = min(k, len(self.stack))
        if limit > 0:
            self.inc[limit-1] += val

if __name__ == '__main__':
    cs = CustomStack(3)  # STEP 1
    cs.push(1)           # STEP 2
    cs.push(2)           # STEP 3
    print(cs.pop())      # STEP 4
    cs.push(2)           # STEP 5
    cs.push(3)           # STEP 6
    cs.push(4)           # STEP 7 (ignored)
    cs.increment(5, 100) # STEP 8
    cs.increment(2, 100) # STEP 9
    print(cs.pop())      # STEP 10
    print(cs.pop())      # STEP 11
    print(cs.pop())      # STEP 12
    print(cs.pop())      # STEP 13

📊

Design a Stack With Increment Operation - Watch the Algorithm Execute, Step by Step

Watching each operation step-by-step reveals how lazy increments work and how the stack and increments array interact, which is difficult to grasp from code alone.

setup

insert

1

insert

1

→

2

delete

1

Result: 2

insert

1

→

2

insert

1

→

2

→

3

insert

1

→

2

→

3

expand

1

→

2

→

3

expand

1

→

2

→

3

delete

1

→

2

Result: 103

delete

1

Result: 202

delete

Result: 201

delete

Result: -1

Key Takeaways

✓ Lazy increments allow efficient increment operations without updating all elements immediately.

This insight is hard to see from code alone because the increments array is separate and propagation happens only on pop.

✓ Pop operation not only removes the top element but also propagates increments down the stack.

Visualizing this propagation clarifies how increments accumulate and affect subsequent pops.

✓ Push respects maxSize and ignores pushes when full, preventing overflow.

Seeing the stack size visually helps understand capacity constraints and why some pushes are ignored.

Practice

1. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

2. What is the average time complexity of the remove operation in the optimized Insert Delete GetRandom O(1) with duplicates data structure that uses a hash map of element to linked list nodes and a list of elements?

medium

A. O(n) because we need to find the element's index in the list before removal.

B. O(log n) due to maintaining the linked list structure during removals.

C. O(1) worst-case because linked list removals and hash map lookups are constant time.

D. O(1) average because the hash map provides direct access to an element's node for removal.

Solution

1. Step 1: Identify data structure operations

   Removal uses hash map to get a node reference in O(1) average time, then removes node from doubly linked list in O(1).

2. Step 2: Clarify average vs worst-case

   Hash map lookups are average O(1), but worst-case can degrade. Linked list removal is always O(1). So overall average is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map + linked list enables average O(1) removals [OK]

Hint: Hash map + linked list enables average O(1) removals [OK]

Common Mistakes:

• Confusing average and worst-case complexities
• Assuming linked list removal is O(log n)
• Thinking index search is needed

3. Suppose the linked list with random pointers can contain cycles formed by random pointers (i.e., random pointers may create cycles independent of next pointers). Which approach correctly copies such a list without infinite loops or duplicate nodes?

hard

A. Use the optimal weaving approach as is, since it handles all cases in O(1) space.

B. Use a recursive approach with memoization to track already copied nodes and avoid infinite recursion.

C. Use the brute force approach but skip assigning random pointers to avoid cycles.

D. Modify the optimal approach to break cycles by removing random pointers before copying.

Solution

1. Step 1: Understand cycle implications

   Random pointer cycles cause infinite loops if naive traversal is used without tracking visited nodes.

2. Step 2: Identify safe approach

   Recursive copying with memoization tracks visited nodes, preventing infinite recursion and duplicate copies.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Memoization ensures each node is copied once even with cycles [OK]

Hint: Memoization prevents infinite recursion in cyclic graphs [OK]

Common Mistakes:

• Assuming weaving approach handles cycles safely
• Ignoring cycles and causing infinite loops
• Removing random pointers loses information

4. Suppose you want to modify the skiplist to support duplicate values and allow searching for the k-th occurrence of a target. Which modification is the most appropriate to maintain efficient search and insertion?

hard

A. Insert duplicate nodes at the lowest level only, ignoring higher levels

B. Store a count of duplicates in each node and update counts on insert/erase

C. Use a hash map to track occurrences separately from the skiplist

D. Disallow duplicates and reject insertions of existing values

Solution

1. Step 1: Understand duplicate handling

   To support duplicates and k-th occurrence search, nodes must track counts or occurrences.

2. Step 2: Evaluate options

   Storing counts in nodes and updating them maintains skiplist structure and efficient operations.

3. Step 3: Reject other options

   Inserting duplicates only at lowest level breaks skiplist invariants; hash map adds overhead; disallowing duplicates contradicts requirement.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting duplicates in nodes preserves skiplist efficiency and supports k-th occurrence [OK]

Hint: Count duplicates in nodes to handle multiple occurrences efficiently [OK]

Common Mistakes:

• Ignoring duplicates in higher levels
• Using external structures breaking skiplist properties
• Disallowing duplicates despite requirement

5. Suppose the skyline problem is extended so that buildings can overlap and have negative heights (e.g., representing underground structures). Which modification to the divide and conquer approach is necessary to correctly handle this variant?

hard

A. Modify the merge step to consider absolute values of heights when computing max height

B. Adjust the merge logic to track both max and min heights at each x-coordinate and merge accordingly

C. No modification needed; the existing merge logic works for negative heights

D. Replace divide and conquer with a brute force height map simulation to handle negative heights

Solution

1. Step 1: Understand impact of negative heights

   Negative heights mean skyline can go below ground, so max height alone is insufficient to represent shape.

2. Step 2: Modify merge logic accordingly

   Need to track both max and min heights at each x to correctly merge skylines with negative and positive heights.

3. Step 3: Evaluate other options

   Using absolute values loses sign info; brute force is inefficient; no modification fails correctness.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking both max and min heights handles negative overlaps correctly [OK]

Hint: Negative heights require tracking min and max heights, not just max [OK]

Common Mistakes:

• Ignoring negative heights
• Using absolute values incorrectly
• Assuming no change needed