Insert Delete GetRandom O(1)
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of operations ≤ 10 - ◆
Each operation is "insert", "remove", or "getRandom" - ◆
0 ≤ val ≤ 200 - ◆
getRandom's randomIndex is always a valid index into the current set at that point (0 ≤ randomIndex < current size) - ◆
insert and remove use val (randomIndex is unused/0); getRandom uses randomIndex (val is unused/0)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Plain List, Linear Search
GoodKeep every element in a plain list. insert: scan the list for val; if absent, append it. remove: scan for val's index; if found, swap it with the last element and drop the last slot (the same O(1) removal trick the optimal solution uses, once the index is known). getRandom: return the element at the given index directly — that part is already O(1). Correct, but both insert and remove pay for a full linear scan just to find val in the first place, so they cost O(n) instead of O(1).
O(n) per operationO(n)1class Solution {
2 public int[] insertDeleteGetRandom(String[] ops, int[][] args) {
3 List<Integer> values = new ArrayList<>();
4 List<Integer> results = new ArrayList<>();
5 for (int i = 0; i < ops.length; i++) {
6 if (ops[i].equals("insert")) {
7 int val = args[i][0];
8 boolean exists = values.contains(val);
9 if (!exists) values.add(val);
10 results.add(exists ? 0 : 1);
11 } else if (ops[i].equals("remove")) {
12 int val = args[i][0];
13 int idx = values.indexOf(val);
14 if (idx == -1) {
15 results.add(0);
16 } else {
17 int lastVal = values.get(values.size() - 1);
18 values.set(idx, lastVal);
19 values.remove(values.size() - 1);
20 results.add(1);
21 }
22 } else {
23 int randomIndex = args[i][1];
24 results.add(values.get(randomIndex));
25 }
26 }
27 int[] output = new int[results.size()];
28 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
29 return output;
30 }
31}Optimal — HashMap + Swap-and-Pop Array
OptimalKeep the elements in an array plus a hash map from value to its index in that array. insert: if the value's already in the map, fail; otherwise append it and record its index — O(1). remove: look up the value's index in the map; instead of shifting everything after it, swap it with the LAST element in the array, update the swapped element's index in the map, then shrink the array by one — no shifting needed, so O(1). getRandom: index straight into the array — already O(1), unchanged. Every operation avoids ever scanning or shifting the whole structure.
O(1) per operationO(n)1class Solution {
2 public int[] insertDeleteGetRandom(String[] ops, int[][] args) {
3 List<Integer> values = new ArrayList<>();
4 Map<Integer, Integer> indexOf = new HashMap<>();
5 List<Integer> results = new ArrayList<>();
6 for (int i = 0; i < ops.length; i++) {
7 if (ops[i].equals("insert")) {
8 int val = args[i][0];
9 if (indexOf.containsKey(val)) {
10 results.add(0);
11 } else {
12 indexOf.put(val, values.size());
13 values.add(val);
14 results.add(1);
15 }
16 } else if (ops[i].equals("remove")) {
17 int val = args[i][0];
18 if (!indexOf.containsKey(val)) {
19 results.add(0);
20 } else {
21 int idx = indexOf.get(val);
22 int lastVal = values.get(values.size() - 1);
23 values.set(idx, lastVal);
24 indexOf.put(lastVal, idx);
25 values.remove(values.size() - 1);
26 indexOf.remove(val);
27 results.add(1);
28 }
29 } else {
30 int randomIndex = args[i][1];
31 results.add(values.get(randomIndex));
32 }
33 }
34 int[] output = new int[results.size()];
35 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
36 return output;
37 }
38}