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 incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

Solution

1. Step 1: Understand operation requirements

   Increment, decrement, getMaxKey, and getMinKey must all be O(1).

2. Step 2: Evaluate approaches

   Hash map + linear scan (B) is O(n) for max/min. Balanced BST (C) and priority queue (D) have O(log n) operations. Doubly linked list with buckets and hash maps (A) supports O(1) updates and retrievals.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket list + hash maps enable O(1) increments, decrements, and max/min retrievals [OK]

Hint: Bucket list + hash maps enable O(1) max/min updates [OK]

Common Mistakes:

• Thinking balanced BST or priority queue can achieve O(1) for all operations

2. You need to design a data structure that supports adding numbers from a stream and retrieving the median efficiently at any time. Which approach best balances insertion and median retrieval time for large data streams?

easy

A. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, balancing their sizes after each insertion.

B. Sort the entire list of numbers every time you query the median.

C. Use a balanced binary search tree to keep all numbers sorted and find the median by in-order traversal.

D. Store numbers in an unsorted array and scan it fully to find the median on each query.

Solution

1. Step 1: Understand the problem constraints

   We need efficient insertion and median retrieval for a data stream, so sorting on every query (Sort the entire list of numbers every time you query the median.) or scanning unsorted arrays (Store numbers in an unsorted array and scan it fully to find the median on each query.) is too slow.

2. Step 2: Evaluate data structures

   Using two heaps (max-heap for lower half, min-heap for upper half) allows O(log n) insertion and O(1) median retrieval by balancing sizes, which is optimal for streaming data.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps balance halves efficiently for median [OK]

Hint: Two heaps balance halves for O(log n) insert and O(1) median [OK]

Common Mistakes:

• Sorting on every query is too slow for streams
• Using one heap only cannot track median efficiently

3. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call? Operations: insert(1), insert(1), insert(2), remove(1), getRandom()

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = null
        self.next = null

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(null)
        self.tail = Node(null)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        if val not in self.idx_map:
            self.idx_map[val] = set()
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or not self.idx_map[val]:
            return false
        remove_idx = self.idx_map[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        if not self.idx_map[val]:
            del self.idx_map[val]
        return true

    def getRandom(self) -> int:
        return random.choice(self.nums)

rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()

easy

A. Either 1 or 2 but 1 is twice as likely

B. 2

C. Either 1 or 2 with equal probability

D. 1

Solution

1. Step 1: Trace insertions

   After insert(1), nums=[1], idx_map={1:{0}}; after insert(1), nums=[1,1], idx_map={1:{0,1}}; after insert(2), nums=[1,1,2], idx_map={1:{0,1},2:{2}}.

2. Step 2: Trace removal of one 1

   Remove one 1: remove_idx=1 (pop from idx_map[1]). Swap last element 2 into index 1: nums=[1,2], idx_map={1:{0},2:{1}}. So now nums has one 1 and one 2.

3. Step 3: Analyze getRandom probabilities

   nums=[1,2], so getRandom picks index 0 or 1 equally. But initially there were two 1's, after removal only one remains. So 1 and 2 are equally likely, but since the original had duplicates, the final collection has one 1 and one 2.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   After removal, one 1 and one 2 remain, so 1 is as likely as 2 [OK]

Hint: Track indices and swaps carefully to find final array state [OK]

Common Mistakes:

• Forgetting to update idx_map after swap
• Assuming getRandom returns only 2
• Ignoring that one 1 remains after removal

4. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

5. What is the time complexity of the checkOut operation in the optimal UndergroundSystem implementation that uses a linked list for check-ins, assuming n is the number of active check-ins at the time of checkout?

medium

A. O(1) because the linked list head always points to the correct check-in node

B. O(n) due to updating route data hash map entries

C. O(log n) because the linked list is sorted by check-in time

D. O(n) because it may need to traverse the linked list to find the matching check-in node

Solution

1. Step 1: Identify linked list traversal

   The checkOut method traverses the linked list from head to find the node with matching id, which can take up to O(n) time.

2. Step 2: Analyze route data update

   Updating the hash map for route data is O(1) average, so it does not dominate complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Traversal over n nodes dominates, so O(n) time [OK]

Hint: Linked list traversal dominates checkOut time [OK]

Common Mistakes:

• Assuming O(1) because head is used directly