1
var matrixRankTransform = function (matrix) {
2
  const n = matrix.length;
3
  const m = matrix[0].length;
4
  //max rank found in x/y lists where yMax[4] would represent the max value found in row index 4;
5
  const yMax = [];
6
  const xMax = [];
7
  const valueToCoords = {};
8

9
  for (let y = 0; y < n; ++y) {
10
    for (let x = 0; x < m; ++x) {
11
      const value = matrix[y][x];
12
      if (!valueToCoords[value]) valueToCoords[value] = [];
13
      valueToCoords[value].push([x, y]);
14
    }
15
  }
16

17
  const sortedKeys = Object.keys(valueToCoords).sort((x, y) => x - y);
18

19
  let parent;
20

21
  function find(target) {
22
    if (parent[target] == null) parent[target] = target;
23
    parent[target] = parent[parent[target]];
24
    return parent[target] === target ? target : find(parent[target]);
25
  }
26

27
  for (const value of sortedKeys) {
28
    const list = valueToCoords[value];
29
    //find cycles
30
    if (list.length > 1) {
31
      parent = {};
32
      let ranks = {};
33
      for (const [x, y] of list) {
34
        let px = find(x);
35
        let py = find(y + n); //have to avoid collisions between y and x keys when they are being used to identify the row/col
36
        parent[px] = py; //bind all the rows and columns together into union by always making the parent of x as y
37
        ranks[py] = Math.max(
38
          xMax[x] ?? 0,
39
          yMax[y] ?? 0,
40
          ranks[py] ?? 0,
41
          ranks[px] ?? 0
42
        );
43
      }
44
      for (const [px, py] of list) {
45
        const rank = Math.max(ranks[find(px)]) + 1; //since we always bind x to y, we can just find x
46
        xMax[px] = yMax[py] = matrix[py][px] = rank;
47
      }
48
    } else {
49
      for (const [px, py] of list) {
50
        const rank = Math.max(yMax[py] ?? 0, xMax[px] ?? 0) + 1;
51
        xMax[px] = yMax[py] = matrix[py][px] = rank;
52
      }
53
    }
54
  }
55

56
  return matrix;
57
};