Insert Delete GetRandom O(1)

🎯

Insert Delete GetRandom O(1)

mediumHASH_MAPAmazonFacebookGoogle

Imagine you are building a gaming platform where you need to quickly add players, remove players, and pick a random player to start a game - all in constant time.

💡 This problem is about designing a data structure that supports three operations efficiently: insert, delete, and get a random element, all in O(1) time. Beginners often struggle because naive solutions either make deletion or random access costly. Understanding how to combine a hash map with an array to achieve all operations in constant time is key.

📋

Problem Statement

Design a data structure that supports the following operations in average O(1) time: insert(val): Inserts an item val into the set if not already present. remove(val): Removes an item val from the set if present. getRandom(): Returns a random element from the current set of elements. Each element must have the same probability of being returned.

1 ≤ number of operations ≤ 10^5Values inserted are integers in the range [-10^9, 10^9]At any time, getRandom will only be called if the set is non-empty

💡

Example

Input"insert(1), insert(2), getRandom(), remove(1), getRandom()"

Output[true, true, 1 or 2, true, 2]

Insert 1 and 2 successfully. getRandom returns either 1 or 2 with equal probability. Remove 1 successfully. getRandom now returns 2 as it's the only element.

• Remove element not present → should return false
• Insert duplicate element → should return false
• getRandom on single element set → always returns that element
• Remove last element and then insert new element → structure still works

⚠️

Common Mistakes

Removing element by shifting array elements

Remove operation becomes O(n), causing timeouts

✅ Use swap-delete trick to remove in O(1)

Not updating hash map after swapping elements

Hash map points to wrong indices, causing incorrect behavior

✅ Always update the moved element's index in the hash map after swap

Using list 'remove' or 'splice' without swap-delete

Remove operation is O(n), not O(1)

✅ Avoid direct removal; swap with last element and pop

Calling getRandom on empty set

Runtime error or exception

✅ Check if set is empty before calling getRandom or define behavior

Allowing duplicates without handling them

Data structure breaks or returns incorrect results

✅ Clarify problem constraints or extend data structure to handle duplicates

🧠

Brute Force (Using List Only)

💡 This approach exists to show the naive way of solving the problem, which helps understand why it is inefficient and motivates the need for better data structures.

Intuition

Store elements in a list. Insert appends to the list. Remove searches the list linearly and removes the element. getRandom picks a random index from the list.

Algorithm

1. Initialize an empty list to store elements.
2. For insert(val), check if val is in list; if not, append it.
3. For remove(val), search the list for val and remove it if found.
4. For getRandom(), pick a random index and return the element at that index.

💡 The main difficulty is that removal requires searching the entire list, which is slow and makes the overall operations not O(1).

</>

Code

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []

    def insert(self, val: int) -> bool:
        if val in self.nums:
            return False
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.nums:
            return False
        self.nums.remove(val)
        return True

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

# Driver code
if __name__ == '__main__':
    rs = RandomizedSet()
    print(rs.insert(1))  # True
    print(rs.insert(2))  # True
    print(rs.getRandom())  # 1 or 2
    print(rs.remove(1))  # True
    print(rs.getRandom())  # 2

Line Notes

self.nums = []Initialize list to store elements for simple storage

if val in self.nums:Check presence by linear search, which is slow

self.nums.append(val)Add element at end for O(1) insertion

self.nums.remove(val)Remove element by searching and deleting, O(n) operation

random.choice(self.nums)Pick random element uniformly from list

import java.util.*;

class RandomizedSet {
    private List<Integer> nums;

    public RandomizedSet() {
        nums = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (nums.contains(val)) {
            return false;
        }
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!nums.contains(val)) {
            return false;
        }
        nums.remove(Integer.valueOf(val));
        return true;
    }

    public int getRandom() {
        Random rand = new Random();
        return nums.get(rand.nextInt(nums.size()));
    }

    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.insert(2)); // true
        System.out.println(rs.getRandom()); // 1 or 2
        System.out.println(rs.remove(1)); // true
        System.out.println(rs.getRandom()); // 2
    }
}

Line Notes

nums = new ArrayList<>();Initialize dynamic array to store elements

if (nums.contains(val))Check presence by linear search, costly for large data

nums.add(val);Add element at end in O(1) amortized

nums.remove(Integer.valueOf(val));Remove element by searching and deleting, O(n)

rand.nextInt(nums.size())Generate random index for uniform random selection

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

class RandomizedSet {
    vector<int> nums;
public:
    RandomizedSet() {
        srand(time(0));
    }

    bool insert(int val) {
        if (find(nums.begin(), nums.end(), val) != nums.end())
            return false;
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = find(nums.begin(), nums.end(), val);
        if (it == nums.end())
            return false;
        nums.erase(it);
        return true;
    }

    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
};

int main() {
    RandomizedSet rs;
    cout << rs.insert(1) << endl; // 1 (true)
    cout << rs.insert(2) << endl; // 1 (true)
    cout << rs.getRandom() << endl; // 1 or 2
    cout << rs.remove(1) << endl; // 1 (true)
    cout << rs.getRandom() << endl; // 2
    return 0;
}

Line Notes

vector<int> nums;Use vector to store elements dynamically

find(nums.begin(), nums.end(), val)Linear search to check presence, inefficient

nums.push_back(val);Add element at end in O(1) amortized

nums.erase(it);Remove element by iterator, O(n) due to shifting

rand() % nums.size()Random index generation for uniform selection

class RandomizedSet {
    constructor() {
        this.nums = [];
    }

    insert(val) {
        if (this.nums.includes(val)) {
            return false;
        }
        this.nums.push(val);
        return true;
    }

    remove(val) {
        const index = this.nums.indexOf(val);
        if (index === -1) {
            return false;
        }
        this.nums.splice(index, 1);
        return true;
    }

    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

// Test
const rs = new RandomizedSet();
console.log(rs.insert(1)); // true
console.log(rs.insert(2)); // true
console.log(rs.getRandom()); // 1 or 2
console.log(rs.remove(1)); // true
console.log(rs.getRandom()); // 2

Line Notes

this.nums = []Initialize array to hold elements

this.nums.includes(val)Check presence by linear search, slow for large arrays

this.nums.push(val)Add element at end in O(1)

this.nums.splice(index, 1)Remove element by index, O(n) due to shifting

Math.floor(Math.random() * this.nums.length)Generate random index for uniform selection

⏱

Complexity

TimeO(n) for remove and insert due to linear search

SpaceO(n) for storing elements in list

Insert and remove require searching the list which takes O(n) time. getRandom is O(1).

💡 For n=100000, each remove or insert could scan 100000 elements, which is too slow for interviews.

Interview Verdict: Use only to introduce - not acceptable for interview coding

This approach is too slow for large inputs and will time out, but it helps understand the problem and motivates better solutions.

🧠

Better (Hash Map for Presence + List for Random Access)

💡 This approach introduces a hash map to speed up presence checks and removals, but still uses a list for random access. It improves insert and remove to average O(1) but removal from list is still costly.

Intuition

Use a hash map to store element to index mapping for O(1) presence check. Insert appends to list and updates map. Remove uses map to find index but removing from middle of list is costly.

Algorithm

1. Initialize a list and a hash map from element to index.
2. For insert(val), check map; if absent, append val to list and record index in map.
3. For remove(val), check map; if present, get index, swap element at index with last element in list, update map for swapped element, pop last element, and remove val from map.
4. For getRandom(), pick random index and return element from list.

💡 The main challenge is that removing from the middle of a list requires shifting elements, which is O(n), so this is better but not optimal. Using swap-delete trick improves removal to O(1).

</>

Code

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.pos = {}

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.pos[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
        idx = self.pos[val]
        last_element = self.nums[-1]
        self.nums[idx] = last_element
        self.pos[last_element] = idx
        self.nums.pop()
        del self.pos[val]
        return True

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

# Driver code
if __name__ == '__main__':
    rs = RandomizedSet()
    print(rs.insert(1))  # True
    print(rs.insert(2))  # True
    print(rs.getRandom())  # 1 or 2
    print(rs.remove(1))  # True
    print(rs.getRandom())  # 2

Line Notes

self.pos = {}Hash map to store element to index mapping for O(1) lookup

if val in self.pos:Check presence in O(1) using hash map

self.pos[val] = len(self.nums)Record index of new element before appending

last_element = self.nums[-1]Get last element to swap with element to remove

self.nums[idx] = last_elementOverwrite element to remove with last element

self.pos[last_element] = idxUpdate map for moved element's new index

self.nums.pop()Remove last element from array in O(1)

del self.pos[val]Remove element from map

import java.util.*;

class RandomizedSet {
    private List<Integer> nums;
    private Map<Integer, Integer> pos;

    public RandomizedSet() {
        nums = new ArrayList<>();
        pos = new HashMap<>();
    }

    public boolean insert(int val) {
        if (pos.containsKey(val)) {
            return false;
        }
        pos.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!pos.containsKey(val)) {
            return false;
        }
        int idx = pos.get(val);
        int lastElement = nums.get(nums.size() - 1);
        nums.set(idx, lastElement);
        pos.put(lastElement, idx);
        nums.remove(nums.size() - 1);
        pos.remove(val);
        return true;
    }

    public int getRandom() {
        Random rand = new Random();
        return nums.get(rand.nextInt(nums.size()));
    }

    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.insert(2)); // true
        System.out.println(rs.getRandom()); // 1 or 2
        System.out.println(rs.remove(1)); // true
        System.out.println(rs.getRandom()); // 2
    }
}

Line Notes

private Map<Integer, Integer> pos;Hash map for element to index mapping

if (pos.containsKey(val))Check presence in O(1)

pos.put(val, nums.size());Record index before adding element

int lastElement = nums.get(nums.size() - 1);Get last element for swap

nums.set(idx, lastElement);Overwrite element to remove with last element

pos.put(lastElement, idx);Update map for moved element's new index

nums.remove(nums.size() - 1);Remove last element in O(1)

pos.remove(val);Remove element from map

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdlib>
#include <ctime>

using namespace std;

class RandomizedSet {
    vector<int> nums;
    unordered_map<int, int> pos;
public:
    RandomizedSet() {
        srand(time(0));
    }

    bool insert(int val) {
        if (pos.count(val))
            return false;
        pos[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!pos.count(val))
            return false;
        int idx = pos[val];
        int lastElement = nums.back();
        nums[idx] = lastElement;
        pos[lastElement] = idx;
        nums.pop_back();
        pos.erase(val);
        return true;
    }

    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
};

int main() {
    RandomizedSet rs;
    cout << rs.insert(1) << endl; // 1
    cout << rs.insert(2) << endl; // 1
    cout << rs.getRandom() << endl; // 1 or 2
    cout << rs.remove(1) << endl; // 1
    cout << rs.getRandom() << endl; // 2
    return 0;
}

Line Notes

unordered_map<int, int> pos;Hash map for element to index mapping

if (pos.count(val))Check presence in O(1)

pos[val] = nums.size();Record index before adding element

int lastElement = nums.back();Get last element for swap

nums[idx] = lastElement;Overwrite element to remove with last element

pos[lastElement] = idx;Update map for moved element's new index

nums.pop_back();Remove last element in O(1)

pos.erase(val);Remove element from map

class RandomizedSet {
    constructor() {
        this.nums = [];
        this.pos = new Map();
    }

    insert(val) {
        if (this.pos.has(val)) {
            return false;
        }
        this.pos.set(val, this.nums.length);
        this.nums.push(val);
        return true;
    }

    remove(val) {
        if (!this.pos.has(val)) {
            return false;
        }
        const idx = this.pos.get(val);
        const lastElement = this.nums[this.nums.length - 1];
        this.nums[idx] = lastElement;
        this.pos.set(lastElement, idx);
        this.nums.pop();
        this.pos.delete(val);
        return true;
    }

    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

// Test
const rs = new RandomizedSet();
console.log(rs.insert(1)); // true
console.log(rs.insert(2)); // true
console.log(rs.getRandom()); // 1 or 2
console.log(rs.remove(1)); // true
console.log(rs.getRandom()); // 2

Line Notes

this.pos = new Map();Hash map for element to index mapping

if (this.pos.has(val))Check presence in O(1)

this.pos.set(val, this.nums.length);Record index before adding element

const lastElement = this.nums[this.nums.length - 1];Get last element for swap

this.nums[idx] = lastElement;Overwrite element to remove with last element

this.pos.set(lastElement, idx);Update map for moved element's new index

this.nums.pop();Remove last element in O(1)

this.pos.delete(val);Remove element from map

⏱

Complexity

TimeO(1) average for insert, remove, and getRandom

SpaceO(n) for list and hash map

Insert and getRandom are O(1) average, and remove uses swap-delete trick to avoid shifting, making it O(1) average as well.

💡 For n=100000, all operations complete quickly, but this approach is still not the final optimal solution if shifting was used. Here, swap-delete makes it optimal.

Interview Verdict: Improvement over brute force but still not optimal for large inputs

This approach shows progress but interviewers expect a fully O(1) solution for all operations. Using swap-delete trick here makes it optimal, so this approach is effectively optimal.

🧠

Optimal (Hash Map + Array with Swap-Delete Trick)

💡 This is the standard optimal solution that achieves average O(1) time for insert, remove, and getRandom by combining a hash map and an array and using a swap-delete trick to avoid costly shifting.

Intuition

Store elements in an array and maintain a hash map from element to its index. To remove an element, swap it with the last element in the array and pop the last element, then update the hash map accordingly. This avoids shifting elements.

Algorithm

1. Initialize an array to store elements and a hash map from element to index.
2. For insert(val), if val not in map, append val to array and record index in map.
3. For remove(val), if val in map, get its index, swap element at index with last element in array, update map for swapped element, pop last element, and remove val from map.
4. For getRandom(), pick a random index and return the element at that index.

💡 The key insight is the swap-delete trick that allows removal without shifting elements, maintaining O(1) time.

</>

Code

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.pos = {}

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.pos[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
        idx = self.pos[val]
        last_element = self.nums[-1]
        self.nums[idx] = last_element
        self.pos[last_element] = idx
        self.nums.pop()
        del self.pos[val]
        return True

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

# Driver code
if __name__ == '__main__':
    rs = RandomizedSet()
    print(rs.insert(1))  # True
    print(rs.insert(2))  # True
    print(rs.getRandom())  # 1 or 2
    print(rs.remove(1))  # True
    print(rs.getRandom())  # 2

Line Notes

self.pos = {}Hash map stores element to index for O(1) lookup

if val in self.pos:Check presence quickly to avoid duplicates

self.pos[val] = len(self.nums)Record index before appending element

last_element = self.nums[-1]Get last element to swap with element to remove

self.nums[idx] = last_elementOverwrite element to remove with last element

self.pos[last_element] = idxUpdate map for moved element's new index

self.nums.pop()Remove last element from array in O(1)

del self.pos[val]Remove element from map

import java.util.*;

class RandomizedSet {
    private List<Integer> nums;
    private Map<Integer, Integer> pos;

    public RandomizedSet() {
        nums = new ArrayList<>();
        pos = new HashMap<>();
    }

    public boolean insert(int val) {
        if (pos.containsKey(val)) {
            return false;
        }
        pos.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!pos.containsKey(val)) {
            return false;
        }
        int idx = pos.get(val);
        int lastElement = nums.get(nums.size() - 1);
        nums.set(idx, lastElement);
        pos.put(lastElement, idx);
        nums.remove(nums.size() - 1);
        pos.remove(val);
        return true;
    }

    public int getRandom() {
        Random rand = new Random();
        return nums.get(rand.nextInt(nums.size()));
    }

    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.insert(2)); // true
        System.out.println(rs.getRandom()); // 1 or 2
        System.out.println(rs.remove(1)); // true
        System.out.println(rs.getRandom()); // 2
    }
}

Line Notes

private Map<Integer, Integer> pos;Hash map for element to index mapping

if (pos.containsKey(val))Check presence in O(1)

pos.put(val, nums.size());Record index before adding element

int lastElement = nums.get(nums.size() - 1);Get last element for swap

nums.set(idx, lastElement);Overwrite element to remove with last element

pos.put(lastElement, idx);Update map for moved element's new index

nums.remove(nums.size() - 1);Remove last element in O(1)

pos.remove(val);Remove element from map

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdlib>
#include <ctime>

using namespace std;

class RandomizedSet {
    vector<int> nums;
    unordered_map<int, int> pos;
public:
    RandomizedSet() {
        srand(time(0));
    }

    bool insert(int val) {
        if (pos.count(val))
            return false;
        pos[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!pos.count(val))
            return false;
        int idx = pos[val];
        int lastElement = nums.back();
        nums[idx] = lastElement;
        pos[lastElement] = idx;
        nums.pop_back();
        pos.erase(val);
        return true;
    }

    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
};

int main() {
    RandomizedSet rs;
    cout << rs.insert(1) << endl; // 1
    cout << rs.insert(2) << endl; // 1
    cout << rs.getRandom() << endl; // 1 or 2
    cout << rs.remove(1) << endl; // 1
    cout << rs.getRandom() << endl; // 2
    return 0;
}

Line Notes

unordered_map<int, int> pos;Hash map for element to index mapping

if (pos.count(val))Check presence in O(1)

pos[val] = nums.size();Record index before adding element

int lastElement = nums.back();Get last element for swap

nums[idx] = lastElement;Overwrite element to remove with last element

pos[lastElement] = idx;Update map for moved element's new index

nums.pop_back();Remove last element in O(1)

pos.erase(val);Remove element from map

class RandomizedSet {
    constructor() {
        this.nums = [];
        this.pos = new Map();
    }

    insert(val) {
        if (this.pos.has(val)) {
            return false;
        }
        this.pos.set(val, this.nums.length);
        this.nums.push(val);
        return true;
    }

    remove(val) {
        if (!this.pos.has(val)) {
            return false;
        }
        const idx = this.pos.get(val);
        const lastElement = this.nums[this.nums.length - 1];
        this.nums[idx] = lastElement;
        this.pos.set(lastElement, idx);
        this.nums.pop();
        this.pos.delete(val);
        return true;
    }

    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

// Test
const rs = new RandomizedSet();
console.log(rs.insert(1)); // true
console.log(rs.insert(2)); // true
console.log(rs.getRandom()); // 1 or 2
console.log(rs.remove(1)); // true
console.log(rs.getRandom()); // 2

Line Notes

this.pos = new Map();Hash map for element to index mapping

if (this.pos.has(val))Check presence in O(1)

this.pos.set(val, this.nums.length);Record index before adding element

const lastElement = this.nums[this.nums.length - 1];Get last element for swap

this.nums[idx] = lastElement;Overwrite element to remove with last element

this.pos.set(lastElement, idx);Update map for moved element's new index

this.nums.pop();Remove last element in O(1)

this.pos.delete(val);Remove element from map

⏱

Complexity

TimeO(1) average for insert, remove, and getRandom

SpaceO(n) for storing elements and hash map

All operations are constant time on average because of direct index access and swap-delete trick.

💡 For n=100000, all operations complete in microseconds, suitable for high-performance requirements.

Interview Verdict: Accepted - optimal solution for interviews

This is the expected solution in interviews, demonstrating mastery of hash maps and arrays for O(1) operations.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal approach (Approach 3). The first two are useful for explanation and understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) for insert and remove	O(n)	No	N/A	Mention only - never code
2. Better (Hash Map + List with shifting)	O(1) insert, O(1) remove with swap-delete trick	O(n)	No	N/A	Mention as improvement, but code swap-delete to make it optimal
3. Optimal (Hash Map + List with swap-delete)	O(1) average for all operations	O(n)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Present the brute force approach to show understanding.Step 3: Explain the better approach using a hash map for presence.Step 4: Introduce the optimal swap-delete trick solution.Step 5: Code the optimal solution carefully and test edge cases.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Coding: 10min → Testing & edge cases: 5min. Total ~23min

What the Interviewer Tests

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

Common Follow-ups

• How to handle duplicates? → Use a hash map from val to a set of indices.
• How to extend to getRandomWeighted? → Use prefix sums and binary search.

💡 These follow-ups test your ability to adapt the data structure to more complex scenarios and show deeper understanding.

🔍

Pattern Recognition

When to Use

1) Need insert, delete, and getRandom in O(1) time; 2) Elements are unique; 3) Random access required; 4) Hash map and array combination possible

Signature Phrases

Insert an item valRemove an item valReturn a random elementAll operations in average O(1) time

NOT This Pattern When

Problems requiring ordered data or range queries (e.g., segment trees, binary indexed trees) are different.

Similar Problems

Randomized Collection - allows duplicates, uses hash map to setsDesign Twitter - uses hash map and linked list for fast operationsLRU Cache - uses hash map and doubly linked list for O(1) operations

Practice

1. You are given an integer array and a target integer k. You need to determine if there exists a continuous subarray of at least length 2 whose sum is a multiple of k (including zero). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to extend subarrays until sum is divisible by k

B. Sorting the array and using two pointers to find subarrays summing to multiples of k

C. Dynamic programming that stores sums of all subarrays explicitly

D. Prefix sum combined with a hash map tracking remainders modulo k

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking sums of continuous subarrays for divisibility by k, which suggests prefix sums and modular arithmetic.

2. Step 2: Identify the approach that efficiently tracks prefix sums modulo k

   Using a hash map to store the earliest index of each remainder allows O(n) detection of subarrays with sums divisible by k.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + remainder hash map is the classic optimal approach [OK]

Hint: Prefix sums + remainder hash map solves this optimally [OK]

Common Mistakes:

• Thinking greedy can find all valid subarrays
• Trying to sort array breaks continuous subarray property
• Using DP to store all subarray sums causes O(n^2) time

2. You are given an integer array and a target sum k. You need to find the number of continuous subarrays whose sum equals k. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a sliding window technique to expand and shrink the window until the sum matches k.

B. Use nested loops to check all subarrays and sum their elements to count matches.

C. Use dynamic programming to store sums of all subarrays and count those equal to k.

D. Use prefix sums combined with a hash map to track frequencies of prefix sums and count valid subarrays in one pass.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting continuous subarrays summing to k efficiently.

2. Step 2: Evaluate approaches

   Sliding window (A) fails with negative numbers. Nested loops (D) are correct but O(n²). DP (C) is inefficient here. Prefix sum + hash map (B) tracks prefix sums and counts in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + hash map is the classic O(n) solution [OK]

Hint: Prefix sums + hash map handles negatives and counts efficiently [OK]

Common Mistakes:

• Assuming sliding window works with negative numbers
• Confusing DP with prefix sums
• Using nested loops for optimality

3. What is the time complexity of the optimal solution that uses a frequency map and first occurrence index to find the first unique character in a string of length n?

medium

A. O(n^2) because of nested loops to check duplicates

B. O(n) because it iterates over the string twice and uses constant-time hash operations

C. O(n) but with O(n) auxiliary space for frequency and index maps

D. O(n log n) due to sorting the characters by their first occurrence

Solution

1. Step 1: Identify loops and data structures used

   The algorithm iterates over the string twice: once to build frequency and index maps, once to find minimum index.

2. Step 2: Analyze time and space complexity

   Time is O(n) due to linear scans; space is O(n) for frequency and index dictionaries (worst case all unique).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time with linear auxiliary space for maps [OK]

Hint: Frequency and index maps use O(n) space, not O(1) [OK]

Common Mistakes:

• Confusing time with space complexity
• Assuming O(1) space due to limited charset
• Thinking sorting is involved

4. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n with u unique elements?

medium

A. O(n + u) since building frequency map and buckets takes linear time

B. O(n log n) due to sorting the frequency map keys

C. O(u * log u) because sorting unique elements is required

D. O(n) because frequency counting and bucket filling are linear in n

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires iterating over n elements -> O(n)

2. Step 2: Analyze bucket filling and result collection

   Filling buckets and collecting top k elements is O(n) since total frequencies sum to n, plus O(u) for iterating unique elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complexity is O(n + u), which is linear since u ≤ n [OK]

Hint: Frequency counting + bucket filling is linear [OK]

Common Mistakes:

• Assuming sorting unique keys is needed
• Confusing n with u in complexity
• Ignoring that bucket iteration is linear in total elements

5. The following code attempts to find the top k frequent elements using bucket sort. Identify the line containing the subtle bug that can cause incorrect results when multiple elements share the same frequency.

medium

A. Line: for num, count in freq.items(): buckets[count].append(num)

B. Line: for i in range(max_freq, 0, -1):

C. Line: for num in nums: freq[num] = freq.get(num, 0) + 1

D. Line: if len(res) == k: return res

Solution

1. Step 1: Understand iteration and early return

   The code appends all elements in buckets[i] before checking if res length reached k.

2. Step 2: Identify bug in early return condition placement

   Checking length after the inner loop causes returning more than k elements if multiple share frequency i.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Moving length check inside inner loop fixes the bug [OK]

Hint: Check length after each append, not after bucket loop [OK]

Common Mistakes:

• Checking length only after bucket loop
• Misplacing early return
• Assuming unique frequencies per bucket