Maximal Network Rank LeetCode solution in Java

1
class Solution {
2
  public int maximalNetworkRank(int n, int[][] roads) {
3

4
    // number of road connected to city
5
    int[] numRoadsConnectedCity = new int[100 + 1];
6

7
    // road exist between two two cities
8
    boolean[][] raadExist = new boolean[n][n];
9

10
    for (int[] cities : roads) {
11

12
      // increment the count of numbers of connected city
13
      numRoadsConnectedCity[cities[0]]++;
14
      numRoadsConnectedCity[cities[1]]++;
15

16
      // mark road exist, between two cities
17
      raadExist[cities[0]][cities[1]] = true;
18
      raadExist[cities[1]][cities[0]] = true;
19
    }
20

21
    int maxRank = 0;
22
    for (int city1 = 0; city1 < n - 1; city1++) {
23
      for (int city2 = city1 + 1; city2 < n; city2++) {
24

25
        // count total number of road connected to both city
26
        int rank = numRoadsConnectedCity[city1] + numRoadsConnectedCity[city2];
27

28
        // just decrement the rank, if both city connected
29
        if (raadExist[city1][city2]) rank--;
30

31
        maxRank = Math.max(maxRank, rank);
32
      }
33
    }
34

35
    return maxRank;
36
  }
37
}