1
// Swap Tail Element Solution
2
// 1. Get a random number between [0, size-1]
3
// 2. size - 1
4
// 3. Get the index in map by the random map
5
// 4. Update the flipped element with the tail element.
6
// Time complexity: O(1) to init, flip, and reset
7
// Space complexity: O(K), where K is the times of flip calls.
8
class Solution {
9
  private final int M, N, CAPACITY;
10
  private int size;
11
  private Random random;
12
  private Map<Integer, Integer> map;
13

14
  public Solution(int m, int n) {
15
    M = m;
16
    N = n;
17
    CAPACITY = m * n;
18
    size = CAPACITY;
19
    random = new Random();
20
    map = new HashMap<>();
21
  }
22

23
  public int[] flip() {
24
    if (size <= 0) return new int[] {-1, -1}; // or throw exception.
25
    Integer rand = random.nextInt(size);
26
    size--;
27
    int idx = map.getOrDefault(rand, rand);
28
    Integer tail = map.getOrDefault(size, size);
29
    map.put(rand, tail);
30
    return new int[] {idx / N, idx % N};
31
  }
32

33
  public void reset() {
34
    map = new HashMap();
35
    size = CAPACITY;
36
  }
37
}
38

39
/**
40
 * Your Solution object will be instantiated and called as such: Solution obj = new Solution(m, n);
41
 * int[] param_1 = obj.flip(); obj.reset();
42
 */