Making A Large Island LeetCode solution in JavaScript

1
var largestIsland = function (grid) {
2
  const n = grid.length;
3
  /**
4
   *  Create the merge find (union find) structure --> https://www.youtube.com/watch?v=ibjEGG7ylHk
5
   *  For this case, we will form the sets at once, already assigning the same representative to all members.
6
   *  Thus, we can use this simplistic implementation without path compression and find(i) = mf[i]
7
   */
8
  const mf = [];
9
  for (let i = 0; i < n * n; i++) {
10
    mf.push(i);
11
  }
12
  // Helper that converts coordinates to array position
13
  const toPos = (r, c) => r * n + c;
14
  // Recursively set the merge find structure to represent the islands' map
15
  const merge = (r, c, repr) => {
16
    mf[toPos(r, c)] = repr; // Merge coordinate
17
    /**
18
     *  Visit neighbors. To visit a neighboring coordinate we first check for:
19
     *  Boundaries (coordinates stay within matrix limits)
20
     *  Neighbor is land (contains a 1)
21
     *  We didn't visit it already (has different representative)
22
     */
23
    if (r > 0 && grid[r - 1][c] === 1 && mf[toPos(r - 1, c)] !== repr) {
24
      // Top
25
      merge(r - 1, c, repr);
26
    }
27
    if (c < n - 1 && grid[r][c + 1] === 1 && mf[toPos(r, c + 1)] !== repr) {
28
      // Right
29
      merge(r, c + 1, repr);
30
    }
31
    if (r < n - 1 && grid[r + 1][c] === 1 && mf[toPos(r + 1, c)] !== repr) {
32
      // Bottom
33
      merge(r + 1, c, repr);
34
    }
35
    if (c > 0 && grid[r][c - 1] === 1 && mf[toPos(r, c - 1)] !== repr) {
36
      // Left
37
      merge(r, c - 1, repr);
38
    }
39
  };
40
  /**
41
   *  For each land (1) position that wasn't already merged into a set,
42
   *  we define a new set with its neighbors.
43
   */
44
  for (let i = 0; i < n; i++) {
45
    for (let j = 0; j < n; j++) {
46
      const pos = toPos(i, j);
47
      if (grid[i][j] === 1 && mf[pos] === pos) {
48
        merge(i, j, pos);
49
      }
50
    }
51
  }
52
  /**
53
   *  We can now calculate the surface of every island by counting the number of cells
54
   *  with the same representative.
55
   */
56
  const count = Array(n * n).fill(0);
57
  mf.forEach((el) => count[el]++);
58
  /**
59
   *  Now we have to decide on which sea (0) should be toggled into land (1).
60
   *  For this we save, for each zero, which sets it is contact with. Once this is done,
61
   *  we can calculate the entire surface by suming 1 + the surface of all touching sets.
62
   *  Again, to add the neighbor set to the store, we need to check that it is a one, that we
63
   *  are within the boundaries, and that it was not already marked as neighbor.
64
   *  We store the maximum surface found, which is the final solution.
65
   */
66
  let maxSurface = 0;
67
  for (let r = 0; r < n; r++) {
68
    for (let c = 0; c < n; c++) {
69
      if (grid[r][c] === 0) {
70
        const touching = [];
71
        let currentSurface = 1;
72
        if (
73
          r > 0 &&
74
          grid[r - 1][c] === 1 &&
75
          !touching.includes(mf[toPos(r - 1, c)])
76
        ) {
77
          // Top
78
          touching.push(mf[toPos(r - 1, c)]);
79
        }
80
        if (
81
          c < n - 1 &&
82
          grid[r][c + 1] === 1 &&
83
          !touching.includes(mf[toPos(r, c + 1)])
84
        ) {
85
          // Right
86
          touching.push(mf[toPos(r, c + 1)]);
87
        }
88
        if (
89
          r < n - 1 &&
90
          grid[r + 1][c] === 1 &&
91
          !touching.includes(mf[toPos(r + 1, c)])
92
        ) {
93
          // Bottom
94
          touching.push(mf[toPos(r + 1, c)]);
95
        }
96
        if (
97
          c > 0 &&
98
          grid[r][c - 1] === 1 &&
99
          !touching.includes(mf[toPos(r, c - 1)])
100
        ) {
101
          // Left
102
          touching.push(mf[toPos(r, c - 1)]);
103
        }
104
        touching.forEach((set) => (currentSurface += count[set]));
105
        if (currentSurface > maxSurface) {
106
          maxSurface = currentSurface;
107
        }
108
      }
109
    }
110
  }
111
  /**
112
   * If maxSurface remained at zero, it means the input is a matrix of ones.
113
   */
114
  if (maxSurface > 0) {
115
    return maxSurface;
116
  }
117
  return n * n;
118
};