Random Flip Matrix

Problem

You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system’s Math.random() and optimize the time and space complexity.

Note:

1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows and 0 <= col.id < n_cols
flip will not be called when the matrix has no 0 values left.
the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input:
[“Solution”,”flip”,”flip”,”flip”,”flip”]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]

Example 2:

Input:
[“Solution”,”flip”,”flip”,”reset”,”flip”]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution’s constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Constraints etc

  • minimize calls to random function
  • optimize the time and space complexity
    -

Approaches

We can use a reservoir sampling approach.

Mapping a 2D matrix to an array.

Given an index from an array we can compute the row and column of the original matrix as long as we know the number of rows and columns.

[TODO] add example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
private:

  int n_samples,n_rows,n_cols;
  unordered_map<int,int> indices;

  vector<int> mapToMatrix(int i) {
    vector<int> v;
    // row
    v[0] = i / n_cols;
    // column
    v[1] = i % n_cols;

    return v;
  }

public:
  Solution(int n_rows, int n_cols) {
    this.n_rows = n_rows;
    this.n_cols = n_cols;
    n_samples = n_rows * n_cols;
    srand(time(0));
  }

  /*
    pick a number between 0 and n_samples - 1
  */
  vector<int> flip() {
    int selected;
    int last = n_samples;
    // pick random number from 0 to n_samples - 1
    int r = rand() % n_samples;

    if (indices.find(r) != indices.end()) {
      // if index already selected before then pick
      // the next available one from map
      selected = indices[r];
    } else {
      selected = r;
    }
    // store it for when we hit the same index again
    indices[r] = n_samples;
    //reduce sample size for next run
    n_samples--;

    return mapToMatrix(selected);

  }

  void reset() {
    srand(time(0));
    indices.clear();
    n_samples = n_rows * n_rows;
  }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n_rows, n_cols);
 * vector<int> param_1 = obj.flip();
 * obj.reset();
 */

Argg 😞

I cannot do

1
2
3
4
5
vector<int> v;
// row
v[0] = i / n_cols;
// column
v[1] = i % n_cols;

We should do push_back().

There is also a division by zero problem here.

1
2
// pick random number from 0 to n_samples - 1
int r = rand() % n_samples;

Updated but not yet accepted 😵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private:

  int n_samples, n_rows, n_cols;
  unordered_map<int, int> indices;

  vector<int> mapToMatrix(int i) {
    vector<int> v;
    // row
    v.push_back(i / n_cols);
    // column
    v.push_back(i % n_cols);

    return v;
  }

public:
  Solution(int n_rows, int n_cols) {
    this->n_rows = n_rows;
    this->n_cols = n_cols;
    n_samples = n_rows * n_cols;
    srand(time(0));
  }

  /*
    pick a number between 0 and n_samples - 1
  */
  vector<int> flip() {
    int selected;
    int last = n_samples;
    int r = 0;
    if (n_samples) r = rand() % n_samples;

    if (indices.find(r) != indices.end()) {
      // if index already selected before then pick
      // the next available one from map
      selected = indices[r];
    }
    else {
      selected = r;
    }

    //reduce sample size for next run
    n_samples--;

    // store it for when we hit the same index again,
    // we want to store it after decrement so we pick the right one
    indices[r] = n_samples;


    return mapToMatrix(selected);

  }

  void reset() {
    srand(time(0));
    indices.clear();
    n_samples = n_rows * n_rows;
  }
};

The issue seems to be this logic

1
2
3
// store it for when we hit the same index again,
// we want to store it after decrement so we pick the right one
indices[r] = n_samples;

We need to lookup indices[n_samples]. If that does not exist then we store n_samples into indices[r].

Updated and cleaned up but still fails

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
private:

  int n_samples, n_rows, n_cols;
  unordered_map<int, int> indices;

public:
  Solution(int n_rows, int n_cols):n_rows(n_rows), n_cols(n_cols),
    n_samples(n_rows*n_cols) {
    srand(time(0));
  }

   vector<int> flip() {
    int r = 0;
    if (n_samples) r = rand() % n_samples;

    // if index already selected before then pick
    // the next available one from map
    int selected = indices.count(r) ? indices[r] : r;

    //reduce sample size for next run
    n_samples--;

    // store it for when we hit the same index again,
    // we want to store it after decrement so we pick the right one
    // if the last element
    indices[r] = indices.count(n_samples) ? indices[n_samples] : n_samples;

    return { selected / n_cols, selected % n_cols };
    }

  void reset() {
    indices.clear();
    n_samples = n_rows * n_rows;
  }
};

Looks like a typo 😵. Can you see it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:

  int n_samples, n_rows, n_cols;
  unordered_map<int, int> indices;

public:
  Solution(int n_rows, int n_cols):n_rows(n_rows), n_cols(n_cols),
    n_samples(n_rows*n_cols) {
    srand(time(0));
  }

   vector<int> flip() {
    int r = 0;
    if (n_samples) r = rand() % n_samples;

    // if index already selected before then pick
    // the next available one from map
    int selected = indices.count(r) ? indices[r] : r;

    //reduce sample size for next run
    n_samples--;

    // store it for when we hit the same index again,
    // we want to store it after decrement so we pick the right one
    // if the tail element is the map then we pick from map
    // otherwise we can just store the index
    indices[r] = indices.count(n_samples) ? indices[n_samples] : n_samples;

    return { selected / n_cols, selected % n_cols };
    }

  void reset() {
    indices.clear();
    n_samples = n_rows * n_cols;
  }
};