Design a Stack With Increment Operation

📋

Problem

Imagine you are designing a special stack for a game where you can push and pop elements, but also increment the bottom k elements efficiently to boost players' scores.

Design a stack which supports the following operations: - push(x): Push element x onto the stack if the stack hasn't reached the max size. - pop(): Pop and return the top element of the stack. If the stack is empty, return -1. - increment(k, val): Increment the bottom k elements of the stack by val. If there are less than k elements, increment all of them. Implement the CustomStack class: - CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack. - void push(int x) pushes x onto the stack if the stack hasn't reached the max size. - int pop() pops and returns the top of the stack or -1 if the stack is empty. - void increment(int k, int val) increments the bottom k elements of the stack by val.

1 ≤ maxSize ≤ 10001 ≤ x ≤ 10001 ≤ k ≤ 10000 ≤ val ≤ 1000At most 1000 calls will be made to each method push, pop, and increment.

Edge cases: Pop from empty stack → returns -1Increment with k larger than current stack size → increments all elementsPush when stack is full → element is ignored

</>

IDE

class CustomStack: def __init__(self, maxSize: int): pass def push(self, x: int) -> None: pass def pop(self) -> int: pass def increment(self, k: int, val: int) -> None: passclass CustomStack { public CustomStack(int maxSize) { // constructor } public void push(int x) { // push method } public int pop() { // pop method return 0; } public void increment(int k, int val) { // increment method } }class CustomStack { public: CustomStack(int maxSize) { // constructor } void push(int x) { // push method } int pop() { // pop method return 0; } void increment(int k, int val) { // increment method } };class CustomStack { constructor(maxSize) { // constructor } push(x) { // push method } pop() { // pop method return -1; } increment(k, val) { // increment method } }

class CustomStack:
    def __init__(self, maxSize: int):
        # Write your solution here
        pass
    def push(self, x: int) -> None:
        pass
    def pop(self) -> int:
        pass
    def increment(self, k: int, val: int) -> None:
        pass

class CustomStack {
    public CustomStack(int maxSize) {
        // Write your solution here
    }
    public void push(int x) {
        // Write your solution here
    }
    public int pop() {
        // Write your solution here
        return -1;
    }
    public void increment(int k, int val) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

class CustomStack {
public:
    CustomStack(int maxSize) {
        // Write your solution here
    }
    void push(int x) {
        // Write your solution here
    }
    int pop() {
        // Write your solution here
        return -1;
    }
    void increment(int k, int val) {
        // Write your solution here
    }
};

class CustomStack {
    constructor(maxSize) {
        // Write your solution here
    }
    push(x) {
        // Write your solution here
    }
    pop() {
        // Write your solution here
        return -1;
    }
    increment(k, val) {
        // Write your solution here
    }
}

Common Bugs to Avoid

Wrong: Pop returns incorrect values after increment callsIncrement applied incorrectly to top elements or all elements instead of bottom k elements✅ Apply increment only to bottom min(k, stack size) elements in the increment method

Wrong: Pop returns -1 even when stack is not emptyPop method does not check if stack is empty before popping✅ Add check if stack is empty before popping and return -1 if empty

Wrong: Push allows more elements than maxSizePush method does not check current stack size before pushing✅ Check if stack size < maxSize before pushing new element

Wrong: Increment calls overwrite previous increments instead of accumulatingIncrement method resets increments instead of adding to existing increments✅ Add increments cumulatively to auxiliary increments array or directly to elements

Wrong: Solution times out on large inputsBrute force increment implementation with O(n*k) complexity✅ Implement lazy increment approach using auxiliary array to achieve O(n) total time

✓

Test Cases

Focus on handling boundary conditions like empty stack and full stack correctly.

Check your increment logic carefully for cumulative and partial increments.

Optimize your increment operation to avoid nested loops for large inputs.

t1_01basic

Input{"operations":["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"],"arguments":[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]}

Expected[null,null,null,2,null,null,null,null,null,103,202,201,-1]

⏱ Performance - must finish in 2000ms

We create a stack of max size 3. Push 1 and 2. Pop returns 2. Push 2, 3, 4 (4 is ignored because stack is full). Increment bottom 5 elements by 100 (all elements incremented). Increment bottom 2 elements by 100. Pop returns 103 (3 + 100), next pop returns 202 (2 + 100 + 100), next pop returns 201 (1 + 100 + 100), last pop returns -1 because stack is empty.

💡 Simulate each operation step-by-step to track stack state and increments.

💡 Remember increment affects bottom k elements, capped by current stack size.

💡 Pop returns top element with all increments applied; push ignores if full.

Why it failed: Incorrect output means increment or push/pop logic is wrong. Fix by ensuring increment only affects bottom min(k, stack size) elements and push ignores if stack is full. This is the canonical example test.

✓ Correctly handles push, pop, and increment operations as per problem statement.

t1_02basic

Input{"operations":["CustomStack","push","push","increment","pop","pop","pop"],"arguments":[[2],[5],[10],[1,5],[],[],[]]}

Expected[null,null,null,null,15,10,-1]

⏱ Performance - must finish in 2000ms

Stack max size 2. Push 5 and 10. Increment bottom 1 element by 5 (only bottom element 5 incremented). Pop returns 15 (5+5), next pop returns 10, last pop returns -1 (empty).

💡 Check how increment affects only bottom k elements.

💡 Verify pop returns top element with increments applied.

💡 Ensure pop returns -1 when stack is empty.

Why it failed: Failing this test usually means increment or pop logic is incorrect. Fix by applying increments only to bottom min(k, stack size) elements and returning -1 on empty pop.

✓ Correctly applies increments and handles pop on empty stack.

t2_01edge

Input{"operations":["CustomStack","pop","increment","pop"],"arguments":[[5],[],[3,10],[]]}

Expected[null,-1,null,-1]

⏱ Performance - must finish in 2000ms

Pop from empty stack returns -1. Increment on empty stack does nothing. Subsequent pop still returns -1.

💡 Test behavior when stack is empty.

💡 Increment should not fail or change anything if stack is empty.

💡 Pop should consistently return -1 when empty.

Why it failed: If pop does not return -1 on empty stack, fix by checking stack emptiness before popping. This is the empty stack edge case.

✓ Handles empty stack pop and increment gracefully.

t2_02edge

Input{"operations":["CustomStack","push","increment","pop"],"arguments":[[1],[100],[5,0],[]]}

Expected[null,null,null,100]

⏱ Performance - must finish in 2000ms

Stack max size 1. Push 100. Increment bottom 5 elements by 0 (no change). Pop returns 100 unchanged.

💡 Check increment with val=0 does not alter stack.

💡 Pop should return original value if no increments applied.

💡 Push should succeed when stack not full.

Why it failed: If increment with val=0 changes values, fix by skipping increment when val=0. This is the zero increment edge case.

✓ Correctly handles zero increment without changing stack.

t2_03edge

Input{"operations":["CustomStack","push","push","push","push","pop","pop","pop","pop"],"arguments":[[3],[1],[2],[3],[4],[],[],[],[]]}

Expected[null,null,null,null,null,3,2,1,-1]

⏱ Performance - must finish in 2000ms

Stack max size 3. Push 1,2,3 succeed. Push 4 ignored (stack full). Pops return 3,2,1 then -1 (empty).

💡 Verify push ignores elements when stack is full.

💡 Pop returns top element or -1 if empty.

💡 Stack size should never exceed maxSize.

Why it failed: If push allows more than maxSize elements, fix by checking stack size before push. This is the push full stack edge case.

✓ Correctly enforces maxSize limit on push.

t3_01corner

Input{"operations":["CustomStack","push","push","increment","pop","pop"],"arguments":[[3],[1],[2],[1,10],[],[]]}

Expected[null,null,null,null,12,2]

⏱ Performance - must finish in 2000ms

Increment only bottom 1 element by 10. Pop returns 12 (1+10), next pop returns 2 unchanged.

💡 Check increment applies only to bottom k elements, not top.

💡 Avoid greedy increment of top elements.

💡 Apply increments lazily or directly to bottom elements.

Why it failed: If increment applies to top elements or all elements incorrectly, fix by applying increment only to bottom min(k, stack size) elements. This is the greedy trap test.

✓ Correctly increments only bottom k elements.

t3_02corner

Input{"operations":["CustomStack","push","push","increment","increment","pop","pop"],"arguments":[[3],[1],[2],[2,10],[2,20],[],[]]}

Expected[null,null,null,null,null,32,21]

⏱ Performance - must finish in 2000ms

Increment bottom 2 elements by 10, then again by 20. Pops return 32 (2+10+20) and 21 (1+10+20).

💡 Check increments accumulate correctly over multiple calls.

💡 Avoid resetting increments or overwriting previous increments.

💡 Use auxiliary array or lazy propagation to accumulate increments.

Why it failed: If increments overwrite previous increments instead of accumulating, fix by adding increments cumulatively. This is the increment accumulation test.

✓ Correctly accumulates increments over multiple calls.

t3_03corner

Input{"operations":["CustomStack","push","increment","pop","pop"],"arguments":[[1],[1000],[1000,1000],[],[]]}

Expected[null,null,null,2000,-1]

⏱ Performance - must finish in 2000ms

Push 1000, increment bottom 1000 elements by 1000 (only one element). Pop returns 2000 (1000+1000), next pop returns -1 (empty).

💡 Test increment with k equal to maxSize.

💡 Ensure increment applies to all elements if k >= stack size.

💡 Pop returns top element with all increments applied.

Why it failed: If increment does not apply to all elements when k >= stack size, fix by using min(k, stack size) in increment. This is the exact boundary test.

✓ Correctly handles increment with k equal or greater than stack size.

t4_01performance

Input{"_description":"n=1000 at constraint boundary - executor generates this input with mixed push, pop, increment operations"}

Expectednull

⏱ Performance - must finish in 2000ms

Test with 1000 operations to ensure O(n) or O(n*maxSize) solutions run within time limit.

💡 Brute force increment on bottom k elements is O(n*k) and may time out.

💡 Use lazy increment array to achieve O(n) total time.

💡 Avoid nested loops over stack for each increment.

Why it failed: TLE indicates brute force increment approach with O(n*k) complexity. Fix by implementing lazy increment technique with auxiliary array. This is the performance test.

✓ Solution runs efficiently within time limits using lazy increment approach.

Practice

1. You are given a singly linked list where each node contains an additional random pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both next and random pointers. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Sort nodes by their values and then copy them sequentially, assigning random pointers based on sorted order.

B. Use a brute force approach with nested loops to assign random pointers after copying nodes.

C. Use dynamic programming to store intermediate results of copied nodes and their random pointers.

D. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a linked list with random pointers efficiently, preserving structure.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows O(1) extra space and O(n) time by leveraging the original list's structure to assign random pointers without extra data structures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interleaving nodes avoids extra hash maps and nested loops [OK]

Hint: Interleaving nodes enables O(1) space copying [OK]

Common Mistakes:

• Assuming nested loops are needed for random pointer assignment
• Thinking sorting helps with random pointers
• Confusing DP with linked list copying

2. You need to design a system that supports posting tweets and retrieving the 10 most recent tweets from a user's timeline, including tweets from users they follow. Which approach best balances efficient posting and retrieving the top recent tweets in real-time?

easy

A. Store all tweets in a global list and scan it entirely each time to find the top 10 recent tweets.

B. Maintain a linked list of tweets per user, a hashmap for followees, and use a max heap to merge the most recent tweets from followees efficiently.

C. Use a dynamic programming approach to precompute the top tweets for each user after every post.

D. Use a simple array per user and sort all tweets from followees every time the feed is requested.

Solution

1. Step 1: Understand the problem constraints

   The system must support fast posting and retrieving the top 10 recent tweets from a user's followees including themselves.

2. Step 2: Evaluate approaches

   Brute force scanning or sorting all tweets each time is inefficient. DP is not applicable here. Using linked lists per user and a max heap for merging recent tweets achieves O(1) posting and O(k log F) retrieval, where F is followees count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linked list + hashmap + heap is the optimal pattern for this problem [OK]

Hint: Linked list + heap merges recent tweets efficiently [OK]

Common Mistakes:

• Thinking sorting all tweets each time is efficient
• Trying DP for a streaming feed problem

3. Given the following code snippet for flattening a multilevel doubly linked list, what is the value of curr.val after the first iteration of the outer while loop when the input list is: 1 - 2 - 3, where node 2 has a child list 4 - 5?

easy

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Initialize curr to head (node with val=1)

   First iteration: curr.val = 1, no child, so move to next node.

2. Step 2: After first iteration, curr moves to node with val=2

   Thus, after the first iteration, curr.val is 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr.val is 1 after first iteration of the loop [OK]

Hint: curr starts at head with val=1 and moves after processing [OK]

Common Mistakes:

• Assuming curr.val changes before moving
• Confusing iteration count with node value

4. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Solution

1. Step 1: Trace set and snap operations

   Initially, data[0] = [(-1,0)]. After set(0,5), data[0] = [(-1,0),(0,5)] because snap_id=0. Then snap() increments snap_id to 1 and returns 0. Then set(0,6) appends (1,6) to data[0].

2. Step 2: Trace get(0,0)

   For snap_id=0, bisect_right finds insertion point for (0,inf) in data[0] = [(-1,0),(0,5),(1,6)]. It returns index 2, so i=1. data[0][1] = (0,5), so get returns 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Value at snap 0 is 5, not the later set 6 [OK]

Hint: Get returns value at or before snap_id using binary search [OK]

Common Mistakes:

• Returning latest value ignoring snap_id
• Off-by-one in bisect index

5. Examine the following buggy code snippet for the MedianFinder class. Which line contains the subtle bug that can cause incorrect median calculation?

medium

A. Condition 'if self.low_size > self.high_size:' for balancing heaps

B. Line that pushes to high heap and increments high_size

C. Line that pushes to low heap and increments low_size

D. Condition 'elif self.high_size > self.low_size + 1:' for balancing heaps

Solution

1. Step 1: Understand balancing condition

   The heaps must be balanced so that their sizes differ by at most 1.

2. Step 2: Identify incorrect condition

   The condition 'if self.low_size > self.high_size:' moves an element from low to high even when sizes differ by only 1, causing imbalance.

3. Step 3: Correct condition

   The condition should be 'if self.low_size > self.high_size + 1:' to ensure size difference is more than 1 before balancing.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Balancing condition must check if low_size > high_size + 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Balancing heaps too aggressively
• Incorrect size difference checks