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 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

2. 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

3. 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

4. What is the amortized time complexity of the put operation in the optimal LFU Cache implementation using a frequency map of doubly linked lists and hash maps?

medium

A. O(n), where n is the number of keys in the cache

B. O(f), where f is the number of distinct frequencies

C. O(log n), due to maintaining frequency order

D. O(1), amortized constant time

Solution

1. Step 1: Analyze data structures used

   Hash maps provide O(1) access to keys and frequencies. Doubly linked lists allow O(1) insertion and deletion of keys within frequency groups.

2. Step 2: Consider operations in put

   Eviction and frequency updates involve O(1) operations on hash maps and linked lists. Frequency increments and min frequency updates are also O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal LFU cache achieves O(1) amortized put [OK]

Hint: Hash maps + linked lists enable O(1) put [OK]

Common Mistakes:

• Assuming O(n) due to scanning keys
• Thinking frequency updates cost O(log n)
• Confusing distinct frequencies with n

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