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. Given the following Python code snippet implementing the AllOne data structure, what is the output of getMaxKey() after these operations?

all_one = AllOne() all_one.inc('apple') all_one.inc('banana') all_one.inc('apple') all_one.dec('banana') print(all_one.getMaxKey())

easy

A. "" (empty string)

B. "apple"

C. "banana"

D. Raises an exception

Solution

1. Step 1: Trace increments and decrements

   After inc('apple') twice, 'apple' count = 2. 'banana' incremented once then decremented once, so removed.

2. Step 2: Check getMaxKey()

   Max count bucket is 2 with 'apple'. So getMaxKey() returns 'apple'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only 'apple' remains with max count 2 [OK]

Hint: Max key is the one with highest count after updates [OK]

Common Mistakes:

• Forgetting to remove 'banana' after dec to zero count

2. Given the following code snippet for the optimal Twitter design, what is the output of getNewsFeed(1) after these operations?

twitter = Twitter()
twitter.postTweet(1, 5)
twitter.postTweet(2, 6)
twitter.followees[1] = {2}
print(twitter.getNewsFeed(1))

Assume getNewsFeed returns a list of tweetIds sorted from most recent to oldest.

easy

A. [6]

B. [5, 6]

C. [5]

D. [6, 5]

Solution

1. Step 1: Trace postTweet calls

   User 1 posts tweet 5 at time=1, user 2 posts tweet 6 at time=2.

2. Step 2: Trace getNewsFeed(1)

   User 1 follows user 2, so heap contains tweets with times 1 (tweet 5) and 2 (tweet 6). Max heap pops tweet 6 first, then tweet 5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap orders tweets by descending time, so output is [6, 5] [OK]

Hint: Heap orders tweets by negative time for max behavior [OK]

Common Mistakes:

• Returning tweets in posting order instead of time order
• Ignoring followees' tweets

3. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output?

medium

A. Line where merged.append([x, max_h]) is called unconditionally

B. Line where x, h1 = left[i] inside first if

C. Line where max_h is computed with max(h1, h2)

D. Line where i and j are incremented in the else block

Solution

1. Step 1: Identify difference from correct code

   The bug is that merged.append is called every iteration without checking if height changed, causing redundant points.

2. Step 2: Understand impact of redundant points

   Appending points even when max_h equals previous height leads to unnecessary key points, failing correctness checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct code appends only if height changes [OK]

Hint: Appending only on height change avoids redundant points [OK]

Common Mistakes:

• Appending every iteration regardless of height change
• Incorrect pointer increments

4. Suppose the UndergroundSystem is extended to allow multiple check-ins by the same passenger without requiring a check-out first (i.e., passengers can start multiple trips before finishing any). Which modification to the data structure or algorithm is necessary to handle this correctly?

hard

A. Keep a stack of check-in nodes per passenger id to track multiple active trips.

B. Use a hash map from passenger id to a single check-in node, overwriting previous check-ins.

C. Store all check-ins in a linked list and traverse fully on each checkOut to find the earliest unmatched check-in.

D. Disallow multiple check-ins by the same passenger to avoid complexity.

Solution

1. Step 1: Understand the problem extension

   Passengers can have multiple active trips simultaneously, so a single check-in per id is insufficient.

2. Step 2: Choose data structure to track multiple check-ins

   A stack per passenger id allows tracking multiple check-ins in order, enabling correct matching on checkOut.

3. Step 3: Why other options fail

   Overwriting check-ins loses data (A). Traversing full list each time (C) is inefficient. Disallowing multiple check-ins (D) is not a solution.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack per id supports multiple active trips correctly [OK]

Hint: Stack per id tracks multiple active check-ins [OK]

Common Mistakes:

• Overwriting check-in info loses data

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)