Design a Stack With Increment Operation

🎯

Design a Stack With Increment Operation

mediumDESIGNAmazonGoogle

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.

💡 This problem is about designing a custom stack data structure that supports not only push and pop but also an increment operation on the bottom k elements. Beginners often struggle because a naive approach to incrementing bottom elements leads to inefficient solutions, and understanding how to optimize this with lazy updates is key.

📋

Problem Statement

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.

💡

Example

Input"CustomStack customStack = new CustomStack(3);\ncustomStack.push(1);\ncustomStack.push(2);\ncustomStack.pop();\ncustomStack.push(2);\ncustomStack.push(3);\ncustomStack.push(4);\ncustomStack.increment(5, 100);\ncustomStack.increment(2, 100);\ncustomStack.pop();\ncustomStack.pop();\ncustomStack.pop();\ncustomStack.pop();"

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

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.

• Pop from empty stack → returns -1
• Increment with k larger than current stack size → increments all elements
• Push when stack is full → element is ignored
• Increment with val = 0 → no change to elements

⚠️

Common Mistakes

Incrementing elements directly in increment() method

Leads to O(n*k) time complexity and TLE on large inputs

✅ Use lazy increments array to defer increments until pop

Not propagating increments down on pop

Elements popped later miss increments, causing wrong results

✅ Add increments[i] to increments[i-1] before popping element at i

Pushing elements even when stack is full

Stack size exceeds maxSize, violating constraints

✅ Check stack size before pushing and ignore push if full

Returning wrong value on pop when stack is empty

Returns error or crashes instead of -1

✅ Check if stack is empty and return -1 accordingly

Incrementing increments array out of bounds

Runtime error or incorrect increments

✅ Use min(k, stack size) to limit increment index

🧠

Brute Force (Direct Increment on Bottom k Elements)

💡 This approach exists to establish a baseline understanding. It directly implements the increment operation by iterating over the bottom k elements each time, which is intuitive but inefficient.

Intuition

For each increment call, simply loop through the bottom k elements and add val to each. Push and pop behave normally.

Algorithm

1. Initialize an empty stack with max size.
2. For push, add element if stack not full.
3. For pop, remove and return top element or -1 if empty.
4. For increment(k, val), loop from bottom to min(k, stack size) and add val to each element.

💡 The increment step is the bottleneck and makes this approach inefficient for large inputs.

</>

Code

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.maxSize = maxSize

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

    def pop(self) -> int:
        if not self.stack:
            return -1
        return self.stack.pop()

    def increment(self, k: int, val: int) -> None:
        limit = min(k, len(self.stack))
        for i in range(limit):
            self.stack[i] += val

# Driver code to test
if __name__ == '__main__':
    cs = CustomStack(3)
    cs.push(1)
    cs.push(2)
    print(cs.pop())  # 2
    cs.push(2)
    cs.push(3)
    cs.push(4)  # ignored
    cs.increment(5, 100)
    cs.increment(2, 100)
    print(cs.pop())  # 103
    print(cs.pop())  # 202
    print(cs.pop())  # 201
    print(cs.pop())  # -1

Line Notes

self.stack = []Initialize an empty list to simulate the stack

if len(self.stack) < self.maxSizeCheck stack size before pushing to avoid overflow

return self.stack.pop()Pop top element if stack not empty

for i in range(limit)Increment bottom k elements by iterating through them

import java.util.*;

class CustomStack {
    private int maxSize;
    private List<Integer> stack;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new ArrayList<>();
    }

    public void push(int x) {
        if (stack.size() < maxSize) {
            stack.add(x);
        }
    }

    public int pop() {
        if (stack.isEmpty()) return -1;
        return stack.remove(stack.size() - 1);
    }

    public void increment(int k, int val) {
        int limit = Math.min(k, stack.size());
        for (int i = 0; i < limit; i++) {
            stack.set(i, stack.get(i) + val);
        }
    }

    public static void main(String[] args) {
        CustomStack cs = new CustomStack(3);
        cs.push(1);
        cs.push(2);
        System.out.println(cs.pop()); // 2
        cs.push(2);
        cs.push(3);
        cs.push(4); // ignored
        cs.increment(5, 100);
        cs.increment(2, 100);
        System.out.println(cs.pop()); // 103
        System.out.println(cs.pop()); // 202
        System.out.println(cs.pop()); // 201
        System.out.println(cs.pop()); // -1
    }
}

Line Notes

this.stack = new ArrayList<>()Use ArrayList to simulate stack behavior

if (stack.size() < maxSize)Prevent pushing beyond max size

return stack.remove(stack.size() - 1)Pop last element if stack not empty

for (int i = 0; i < limit; i++)Increment bottom k elements by iterating

#include <iostream>
#include <vector>
using namespace std;

class CustomStack {
    int maxSize;
    vector<int> stack;
public:
    CustomStack(int maxSize) {
        this->maxSize = maxSize;
    }

    void push(int x) {
        if ((int)stack.size() < maxSize) {
            stack.push_back(x);
        }
    }

    int pop() {
        if (stack.empty()) return -1;
        int val = stack.back();
        stack.pop_back();
        return val;
    }

    void increment(int k, int val) {
        int limit = min(k, (int)stack.size());
        for (int i = 0; i < limit; i++) {
            stack[i] += val;
        }
    }
};

int main() {
    CustomStack cs(3);
    cs.push(1);
    cs.push(2);
    cout << cs.pop() << "\n"; // 2
    cs.push(2);
    cs.push(3);
    cs.push(4); // ignored
    cs.increment(5, 100);
    cs.increment(2, 100);
    cout << cs.pop() << "\n"; // 103
    cout << cs.pop() << "\n"; // 202
    cout << cs.pop() << "\n"; // 201
    cout << cs.pop() << "\n"; // -1
    return 0;
}

Line Notes

vector<int> stack;Use vector to simulate stack with dynamic size

if ((int)stack.size() < maxSize)Check size before pushing to avoid overflow

int val = stack.back();Store top element before popping

for (int i = 0; i < limit; i++)Increment bottom k elements by iterating

class CustomStack {
    constructor(maxSize) {
        this.maxSize = maxSize;
        this.stack = [];
    }

    push(x) {
        if (this.stack.length < this.maxSize) {
            this.stack.push(x);
        }
    }

    pop() {
        if (this.stack.length === 0) return -1;
        return this.stack.pop();
    }

    increment(k, val) {
        let limit = Math.min(k, this.stack.length);
        for (let i = 0; i < limit; i++) {
            this.stack[i] += val;
        }
    }
}

// Test
const cs = new CustomStack(3);
cs.push(1);
cs.push(2);
console.log(cs.pop()); // 2
cs.push(2);
cs.push(3);
cs.push(4); // ignored
cs.increment(5, 100);
cs.increment(2, 100);
console.log(cs.pop()); // 103
console.log(cs.pop()); // 202
console.log(cs.pop()); // 201
console.log(cs.pop()); // -1

Line Notes

this.stack = []Initialize empty array to simulate stack

if (this.stack.length < this.maxSize)Prevent pushing beyond max size

return this.stack.pop()Pop top element if stack not empty

for (let i = 0; i < limit; i++)Increment bottom k elements by iterating

⏱

Complexity

TimeO(n*k) where n is number of increment calls and k is increment size

SpaceO(maxSize) for the stack storage

Each increment operation loops over up to k elements, so if many increments occur, total time can be large.

💡 For n=1000 increments and k=1000, this means up to 1,000,000 operations, which is slow.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large test cases, motivating optimization.

🧠

Better Approach (Lazy Increment Using Auxiliary Array)

💡 This approach introduces a clever lazy increment technique to avoid incrementing all bottom k elements immediately, improving efficiency.

Intuition

Instead of incrementing elements directly, store increments in an auxiliary array and apply them when popping elements.

Algorithm

1. Initialize stack and an increments array of same max size with zeros.
2. Push elements normally if stack not full.
3. For increment(k, val), add val to increments[k-1] to mark pending increment for bottom k elements.
4. For pop, apply increments from increments array to the popped element and propagate increments down.

💡 The key is that increments are stored and propagated lazily, avoiding repeated work.

</>

Code

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

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

    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

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

# Driver code to test
if __name__ == '__main__':
    cs = CustomStack(3)
    cs.push(1)
    cs.push(2)
    print(cs.pop())  # 2
    cs.push(2)
    cs.push(3)
    cs.push(4)  # ignored
    cs.increment(5, 100)
    cs.increment(2, 100)
    print(cs.pop())  # 103
    print(cs.pop())  # 202
    print(cs.pop())  # 201
    print(cs.pop())  # -1

Line Notes

self.inc = [0] * maxSizeInitialize increments array to store lazy increments

if len(self.stack) < self.maxSizeCheck stack size before pushing

self.inc[i-1] += self.inc[i]Propagate increments down when popping

self.inc[limit-1] += valAdd val to increments at position limit-1 to mark lazy increment

import java.util.*;

class CustomStack {
    private int maxSize;
    private List<Integer> stack;
    private int[] inc;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new ArrayList<>();
        this.inc = new int[maxSize];
    }

    public void push(int x) {
        if (stack.size() < maxSize) {
            stack.add(x);
        }
    }

    public int pop() {
        int i = stack.size() - 1;
        if (i < 0) return -1;
        if (i > 0) inc[i - 1] += inc[i];
        int res = stack.remove(i) + inc[i];
        inc[i] = 0;
        return res;
    }

    public void increment(int k, int val) {
        int limit = Math.min(k, stack.size());
        if (limit > 0) inc[limit - 1] += val;
    }

    public static void main(String[] args) {
        CustomStack cs = new CustomStack(3);
        cs.push(1);
        cs.push(2);
        System.out.println(cs.pop()); // 2
        cs.push(2);
        cs.push(3);
        cs.push(4); // ignored
        cs.increment(5, 100);
        cs.increment(2, 100);
        System.out.println(cs.pop()); // 103
        System.out.println(cs.pop()); // 202
        System.out.println(cs.pop()); // 201
        System.out.println(cs.pop()); // -1
    }
}

Line Notes

this.inc = new int[maxSize]Initialize increments array for lazy increments

if (stack.size() < maxSize)Check stack size before pushing

if (i > 0) inc[i - 1] += inc[i]Propagate increments down when popping

if (limit > 0) inc[limit - 1] += valAdd val to increments at limit-1 lazily

#include <iostream>
#include <vector>
using namespace std;

class CustomStack {
    int maxSize;
    vector<int> stack;
    vector<int> inc;
public:
    CustomStack(int maxSize) {
        this->maxSize = maxSize;
        inc.resize(maxSize, 0);
    }

    void push(int x) {
        if ((int)stack.size() < maxSize) {
            stack.push_back(x);
        }
    }

    int pop() {
        int i = (int)stack.size() - 1;
        if (i < 0) return -1;
        if (i > 0) inc[i - 1] += inc[i];
        int res = stack.back() + inc[i];
        stack.pop_back();
        inc[i] = 0;
        return res;
    }

    void increment(int k, int val) {
        int limit = min(k, (int)stack.size());
        if (limit > 0) inc[limit - 1] += val;
    }
};

int main() {
    CustomStack cs(3);
    cs.push(1);
    cs.push(2);
    cout << cs.pop() << "\n"; // 2
    cs.push(2);
    cs.push(3);
    cs.push(4); // ignored
    cs.increment(5, 100);
    cs.increment(2, 100);
    cout << cs.pop() << "\n"; // 103
    cout << cs.pop() << "\n"; // 202
    cout << cs.pop() << "\n"; // 201
    cout << cs.pop() << "\n"; // -1
    return 0;
}

Line Notes

inc.resize(maxSize, 0)Initialize increments vector with zeros

if ((int)stack.size() < maxSize)Check stack size before pushing

if (i > 0) inc[i - 1] += inc[i]Propagate increments down lazily on pop

if (limit > 0) inc[limit - 1] += valAdd val lazily to increments array

class CustomStack {
    constructor(maxSize) {
        this.maxSize = maxSize;
        this.stack = [];
        this.inc = new Array(maxSize).fill(0);
    }

    push(x) {
        if (this.stack.length < this.maxSize) {
            this.stack.push(x);
        }
    }

    pop() {
        let i = this.stack.length - 1;
        if (i < 0) return -1;
        if (i > 0) this.inc[i - 1] += this.inc[i];
        let res = this.stack.pop() + this.inc[i];
        this.inc[i] = 0;
        return res;
    }

    increment(k, val) {
        let limit = Math.min(k, this.stack.length);
        if (limit > 0) this.inc[limit - 1] += val;
    }
}

// Test
const cs = new CustomStack(3);
cs.push(1);
cs.push(2);
console.log(cs.pop()); // 2
cs.push(2);
cs.push(3);
cs.push(4); // ignored
cs.increment(5, 100);
cs.increment(2, 100);
console.log(cs.pop()); // 103
console.log(cs.pop()); // 202
console.log(cs.pop()); // 201
console.log(cs.pop()); // -1

Line Notes

this.inc = new Array(maxSize).fill(0)Initialize increments array with zeros

if (this.stack.length < this.maxSize)Check stack size before pushing

if (i > 0) this.inc[i - 1] += this.inc[i]Propagate increments down lazily on pop

if (limit > 0) this.inc[limit - 1] += valAdd val lazily to increments array

⏱

Complexity

TimeO(n) total for n operations

SpaceO(maxSize) for stack and increments array

Each increment is O(1) by lazy update, pop is O(1) with propagation, push is O(1). So total O(n) for n operations.

💡 For n=1000 operations, this means roughly 1000 steps, which is efficient.

Interview Verdict: Accepted and efficient

This approach is optimal for the problem constraints and is what interviewers expect after brute force.

🧠

Optimal Approach (Same as Better but Explained with Stack + Lazy Increment)

💡 This approach is the same as the better approach but emphasizes the conceptual understanding of lazy increments and propagation during pop.

Intuition

Store increments lazily and propagate them down the stack on pop to ensure each element gets the correct total increment without repeated work.

Algorithm

1. Initialize stack and increments array.
2. Push elements if stack not full.
3. For increment(k, val), add val to increments[k-1].
4. On pop, add increments[i] to popped element, propagate increments[i] to increments[i-1], reset increments[i].

💡 The propagation step ensures increments accumulate correctly for remaining elements.

</>

Code

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

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

    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

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

# Driver code to test
if __name__ == '__main__':
    cs = CustomStack(3)
    cs.push(1)
    cs.push(2)
    print(cs.pop())  # 2
    cs.push(2)
    cs.push(3)
    cs.push(4)  # ignored
    cs.increment(5, 100)
    cs.increment(2, 100)
    print(cs.pop())  # 103
    print(cs.pop())  # 202
    print(cs.pop())  # 201
    print(cs.pop())  # -1

Line Notes

self.inc = [0] * maxSizeCreate increments array to hold lazy increments

if len(self.stack) < self.maxSizeEnsure stack does not exceed max size

self.inc[i-1] += self.inc[i]Propagate increments down to next element on pop

self.inc[limit-1] += valAdd increment lazily to the increments array

import java.util.*;

class CustomStack {
    private int maxSize;
    private List<Integer> stack;
    private int[] inc;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new ArrayList<>();
        this.inc = new int[maxSize];
    }

    public void push(int x) {
        if (stack.size() < maxSize) {
            stack.add(x);
        }
    }

    public int pop() {
        int i = stack.size() - 1;
        if (i < 0) return -1;
        if (i > 0) inc[i - 1] += inc[i];
        int res = stack.remove(i) + inc[i];
        inc[i] = 0;
        return res;
    }

    public void increment(int k, int val) {
        int limit = Math.min(k, stack.size());
        if (limit > 0) inc[limit - 1] += val;
    }

    public static void main(String[] args) {
        CustomStack cs = new CustomStack(3);
        cs.push(1);
        cs.push(2);
        System.out.println(cs.pop()); // 2
        cs.push(2);
        cs.push(3);
        cs.push(4); // ignored
        cs.increment(5, 100);
        cs.increment(2, 100);
        System.out.println(cs.pop()); // 103
        System.out.println(cs.pop()); // 202
        System.out.println(cs.pop()); // 201
        System.out.println(cs.pop()); // -1
    }
}

Line Notes

this.inc = new int[maxSize]Initialize increments array for lazy increments

if (stack.size() < maxSize)Check stack size before pushing

if (i > 0) inc[i - 1] += inc[i]Propagate increments down lazily on pop

if (limit > 0) inc[limit - 1] += valAdd val lazily to increments array

#include <iostream>
#include <vector>
using namespace std;

class CustomStack {
    int maxSize;
    vector<int> stack;
    vector<int> inc;
public:
    CustomStack(int maxSize) {
        this->maxSize = maxSize;
        inc.resize(maxSize, 0);
    }

    void push(int x) {
        if ((int)stack.size() < maxSize) {
            stack.push_back(x);
        }
    }

    int pop() {
        int i = (int)stack.size() - 1;
        if (i < 0) return -1;
        if (i > 0) inc[i - 1] += inc[i];
        int res = stack.back() + inc[i];
        stack.pop_back();
        inc[i] = 0;
        return res;
    }

    void increment(int k, int val) {
        int limit = min(k, (int)stack.size());
        if (limit > 0) inc[limit - 1] += val;
    }
};

int main() {
    CustomStack cs(3);
    cs.push(1);
    cs.push(2);
    cout << cs.pop() << "\n"; // 2
    cs.push(2);
    cs.push(3);
    cs.push(4); // ignored
    cs.increment(5, 100);
    cs.increment(2, 100);
    cout << cs.pop() << "\n"; // 103
    cout << cs.pop() << "\n"; // 202
    cout << cs.pop() << "\n"; // 201
    cout << cs.pop() << "\n"; // -1
    return 0;
}

Line Notes

inc.resize(maxSize, 0)Initialize increments vector with zeros

if ((int)stack.size() < maxSize)Check stack size before pushing

if (i > 0) inc[i - 1] += inc[i]Propagate increments down lazily on pop

if (limit > 0) inc[limit - 1] += valAdd val lazily to increments array

class CustomStack {
    constructor(maxSize) {
        this.maxSize = maxSize;
        this.stack = [];
        this.inc = new Array(maxSize).fill(0);
    }

    push(x) {
        if (this.stack.length < this.maxSize) {
            this.stack.push(x);
        }
    }

    pop() {
        let i = this.stack.length - 1;
        if (i < 0) return -1;
        if (i > 0) this.inc[i - 1] += this.inc[i];
        let res = this.stack.pop() + this.inc[i];
        this.inc[i] = 0;
        return res;
    }

    increment(k, val) {
        let limit = Math.min(k, this.stack.length);
        if (limit > 0) this.inc[limit - 1] += val;
    }
}

// Test
const cs = new CustomStack(3);
cs.push(1);
cs.push(2);
console.log(cs.pop()); // 2
cs.push(2);
cs.push(3);
cs.push(4); // ignored
cs.increment(5, 100);
cs.increment(2, 100);
console.log(cs.pop()); // 103
console.log(cs.pop()); // 202
console.log(cs.pop()); // 201
console.log(cs.pop()); // -1

Line Notes

this.inc = new Array(maxSize).fill(0)Initialize increments array with zeros

if (this.stack.length < this.maxSize)Check stack size before pushing

if (i > 0) this.inc[i - 1] += this.inc[i]Propagate increments down lazily on pop

if (limit > 0) this.inc[limit - 1] += valAdd val lazily to increments array

⏱

Complexity

TimeO(n) total for n operations

SpaceO(maxSize) for stack and increments array

Same as better approach; lazy increments make all operations O(1) amortized.

💡 This approach is the most efficient and practical for interviews.

Interview Verdict: Accepted and optimal

This is the recommended approach to implement in interviews after explaining the lazy increment idea.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the lazy increment approach (Approach 2 or 3) in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(maxSize)	No	N/A	Mention only - never code
2. Better (Lazy Increment)	O(n)	O(maxSize)	No	N/A	Code this for optimal solution
3. Optimal (Lazy Increment with Propagation)	O(n)	O(maxSize)	No	N/A	Same as Approach 2, emphasize understanding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, starting from brute force to optimal solutions. Practice explaining each approach clearly and test edge cases.

How to Present

Step 1: Clarify problem constraints and operations.Step 2: Describe brute force approach and its inefficiency.Step 3: Introduce lazy increment idea and implement better approach.Step 4: Explain optimal approach with increment propagation.Step 5: Write clean code and test with examples and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your ability to design custom data structures, optimize naive solutions, and handle edge cases efficiently.

Common Follow-ups

• What if increment operation was called very frequently? → Lazy increments handle this efficiently.
• Can you optimize space usage? → The increments array is minimal; further optimization is not needed.

💡 These follow-ups check your understanding of optimization and space-time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Need to design custom data structure with push/pop. 2) Additional operation modifies multiple elements (increment bottom k). 3) Naive approach is inefficient due to repeated updates. 4) Lazy or deferred updates can optimize performance.

Signature Phrases

'increment the bottom k elements of the stack by val''push and pop operations with max size'

NOT This Pattern When

Standard stack problems without extra operations or lazy updates

Similar Problems

Min Stack - stack with extra operations maintaining stateDesign a Queue With Increment Operation - similar lazy update pattern

Practice

1. You need to design a data structure that supports setting values at indices, taking snapshots of the entire array state, and retrieving values at any snapshot efficiently. Which approach best balances time and space complexity for frequent set and get operations?

easy

A. Store full copies of the array on every snapshot to allow O(1) get operations.

B. Maintain a hash map per index storing (snap_id, value) pairs and use binary search to retrieve values for get operations.

C. Use a single global hash map keyed by (index, snap_id) and perform linear search for get operations.

D. Use a segment tree to store snapshots and query values at any snapshot.

Solution

1. Step 1: Understand problem requirements

   The data structure must efficiently support set, snap, and get operations with many snapshots and updates.

2. Step 2: Evaluate approaches

   Storing full snapshots (B) uses too much space and is slow for many snaps. A global hash map with linear search (C) makes get operations slow. Segment trees (D) are complex and not optimal here. Using a hash map per index with binary search (A) allows O(1) amortized set and snap, and O(log m) get, balancing time and space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per index enables fast retrieval [OK]

Hint: Binary search per index enables fast retrieval [OK]

Common Mistakes:

• Thinking full snapshots are efficient for many snaps
• Using linear search for get causes slow queries

2. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random  # Bug here
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

medium

A. Line assigning curr.next.random = curr.random

B. Line inserting copied nodes: curr.next = new_node

C. Line advancing curr in Step 1: curr = new_node.next

D. Line separating original and copied lists: curr.next = curr.next.next

Solution

1. Step 1: Analyze random pointer assignment

   The line assigns curr.next.random = curr.random, but curr.random points to original nodes, not copied nodes.

2. Step 2: Correct assignment

   It should be curr.next.random = curr.random.next to point to the copied node corresponding to curr.random.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect random pointer assignment breaks copied list correctness [OK]

Hint: Random pointer must point to copied node, not original [OK]

Common Mistakes:

• Assigning random pointer directly to original node
• Mixing original and copied nodes after weaving
• Forgetting to advance curr by two nodes

3. Consider the following buggy LFUCache get method. Which line contains the subtle bug that can cause incorrect eviction behavior?

def get(self, key: int) -> int:
    if key not in self.key_val_freq:
        return -1
    val, freq = self.key_val_freq[key]
    del self.freq_keys[freq][key]
    if not self.freq_keys[freq]:
        del self.freq_keys[freq]
        # BUG: missing update of min_freq here
    self.freq_keys[freq + 1][key] = None
    self.key_val_freq[key] = (val, freq + 1)
    return val

What is the bug?

medium

A. Missing update of min_freq after deleting freq_keys[freq]

B. Line deleting freq_keys[freq] when empty

C. Line deleting key from freq_keys[freq]

D. Line adding key to freq_keys[freq + 1]

Solution

1. Step 1: Identify the role of min_freq

   min_freq tracks the smallest frequency present in the cache, needed for correct eviction.

2. Step 2: Check frequency list deletion

   When freq_keys[freq] becomes empty and is deleted, if freq equals min_freq, min_freq must be incremented to freq + 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing min_freq update causes stale min_freq and wrong eviction [OK]

Hint: min_freq must update when freq list empties [OK]

Common Mistakes:

• Forgetting to update min_freq after freq list deletion
• Confusing key deletion with frequency list deletion
• Assuming min_freq updates automatically

4. What is the time complexity of the get and put operations in an optimal LRU Cache implementation using a hash map and a doubly linked list with capacity n?

medium

A. O(n) for get and put due to list traversal

B. O(1) amortized for get and put using hash map and doubly linked list

C. O(log n) due to balancing the linked list

D. O(1) for get but O(n) for put due to eviction

Solution

1. Step 1: Analyze get operation

   Hash map provides O(1) access to node; doubly linked list allows O(1) removal and insertion to update usage order.

2. Step 2: Analyze put operation

   Insertion involves hash map update and linked list insertion/removal, all O(1). Eviction removes tail node in O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both get and put run in constant time using combined data structures [OK]

Hint: Hash map + doubly linked list -> O(1) get and put [OK]

Common Mistakes:

• Assuming list removal is O(n)
• Confusing amortized with worst-case
• Thinking linked list needs balancing

5. Consider the following buggy addRange method for the RangeModule. Which line contains the subtle bug that causes incorrect interval merging?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] > left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

medium

A. Line with condition: if i != 0 and self.intervals[self.starts[i-1]] > left:

B. Line with bisect_left call: i = bisect_left(self.starts, left)

C. Line deleting intervals: for k in self.starts[i:j]: del self.intervals[k]

D. Line updating self.starts: self.starts[i:j] = [left]

Solution

1. Step 1: Analyze the condition for merging overlapping intervals

   The condition uses > instead of >=, so intervals that exactly touch at the boundary are not merged.

2. Step 2: Consequence of the bug

   This causes fragmented intervals and incorrect query results because adjacent intervals are not merged properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using > instead of >= misses boundary merges [OK]

Hint: Check interval overlap condition carefully for off-by-one errors [OK]

Common Mistakes:

• Using strict inequality instead of inclusive for merging intervals