In this guide, you will get 1615. Maximal Network Rank LeetCode Solution with the best time and space complexity. The solution to Maximal Network Rank problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.
The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.
Example 1:
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.
Example 2:
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.
Example 3:
Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
Constraints:
2 <= n <= 100
0 <= roads.length <= n * (n – 1) / 2
roads[i].length == 2
0 <= ai, bi <= n-1
ai != bi
Each pair of cities has at most one road connecting them.
Complexity Analysis
Time Complexity: O(n + |\texttt{roads}|)
Space Complexity: O(n)
1615. Maximal Network Rank LeetCode Solution in C++
class Solution {
public:
int maximalNetworkRank(int n, vector<vector<int>>& roads) {
vector<int> degrees(n);
for (const vector<int>& road : roads) {
const int u = road[0];
const int v = road[1];
++degrees[u];
++degrees[v];
}
// Find the first maximum and the second maximum degrees.
int maxDegree1 = 0;
int maxDegree2 = 0;
for (const int degree : degrees) {
if (degree > maxDegree1) {
maxDegree2 = maxDegree1;
maxDegree1 = degree;
} else if (degree > maxDegree2) {
maxDegree2 = degree;
}
}
// There can be multiple nodes with `maxDegree1` or `maxDegree2`.
// Find the counts of such nodes.
int countMaxDegree1 = 0;
int countMaxDegree2 = 0;
for (const int degree : degrees)
if (degree == maxDegree1)
++countMaxDegree1;
else if (degree == maxDegree2)
++countMaxDegree2;
if (countMaxDegree1 == 1) {
// 1. If there is only one node with degree = `maxDegree1`, then we'll
// need to use the node with degree = `maxDegree2`. The answer in general
// will be (maxDegree1 + maxDegree2), but if the two nodes that we're
// considering are connected, then we'll have to subtract 1.
const int edgeCount =
getEdgeCount(roads, degrees, maxDegree1, maxDegree2) +
getEdgeCount(roads, degrees, maxDegree2, maxDegree1);
return maxDegree1 + maxDegree2 - (countMaxDegree2 == edgeCount ? 1 : 0);
} else {
// 2. If there are more than one node with degree = `maxDegree1`, then we
// can consider `maxDegree1` twice, and we don't need to use `maxDegree2`.
// The answer in general will be 2 * maxDegree1, but if the two nodes that
// we're considering are connected, then we'll have to subtract 1.
const int edgeCount =
getEdgeCount(roads, degrees, maxDegree1, maxDegree1);
const int maxPossibleEdgeCount =
countMaxDegree1 * (countMaxDegree1 - 1) / 2;
return 2 * maxDegree1 - (maxPossibleEdgeCount == edgeCount ? 1 : 0);
}
}
private:
// Returns the number of edges (u, v) where degress[u] == degreeU and
// degrees[v] == degreeV.
int getEdgeCount(const vector<vector<int>>& roads, const vector<int>& degrees,
int degreeU, int degreeV) {
int edgeCount = 0;
for (const vector<int>& road : roads) {
const int u = road[0];
const int v = road[1];
if (degrees[u] == degreeU && degrees[v] == degreeV)
++edgeCount;
}
return edgeCount;
}
}; /* code provided by PROGIEZ */
1615. Maximal Network Rank LeetCode Solution in Java
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[] degrees = new int[n];
for (int[] road : roads) {
final int u = road[0];
final int v = road[1];
++degrees[u];
++degrees[v];
}
// Find the first maximum and the second maximum degrees.
int maxDegree1 = 0;
int maxDegree2 = 0;
for (final int degree : degrees)
if (degree > maxDegree1) {
maxDegree2 = maxDegree1;
maxDegree1 = degree;
} else if (degree > maxDegree2) {
maxDegree2 = degree;
}
// There can be multiple nodes with `maxDegree1` or `maxDegree2`.
// Find the counts of such nodes.
int countMaxDegree1 = 0;
int countMaxDegree2 = 0;
for (final int degree : degrees)
if (degree == maxDegree1)
++countMaxDegree1;
else if (degree == maxDegree2)
++countMaxDegree2;
if (countMaxDegree1 == 1) {
// 1. If there is only one node with degree = `maxDegree1`, then we'll
// need to use the node with degree = `maxDegree2`. The answer in general
// will be (maxDegree1 + maxDegree2), but if the two nodes that we're
// considering are connected, then we'll have to subtract 1.
final int edgeCount = getEdgeCount(roads, degrees, maxDegree1, maxDegree2) +
getEdgeCount(roads, degrees, maxDegree2, maxDegree1);
return maxDegree1 + maxDegree2 - (countMaxDegree2 == edgeCount ? 1 : 0);
} else {
// 2. If there are more than one node with degree = `maxDegree1`, then we
// can consider `maxDegree1` twice, and we don't need to use `maxDegree2`.
// The answer in general will be 2 * maxDegree1, but if the two nodes that
// we're considering are connected, then we'll have to subtract 1.
final int edgeCount = getEdgeCount(roads, degrees, maxDegree1, maxDegree1);
final int maxPossibleEdgeCount = countMaxDegree1 * (countMaxDegree1 - 1) / 2;
return 2 * maxDegree1 - (maxPossibleEdgeCount == edgeCount ? 1 : 0);
}
}
// Returns the number of edges (u, v) where degress[u] == degreeU and
// degrees[v] == degreeV.
private int getEdgeCount(int[][] roads, int[] degrees, int degreeU, int degreeV) {
int edgeCount = 0;
for (int[] road : roads) {
final int u = road[0];
final int v = road[1];
if (degrees[u] == degreeU && degrees[v] == degreeV)
++edgeCount;
}
return edgeCount;
}
} // code provided by PROGIEZ
1615. Maximal Network Rank LeetCode Solution in Python
class Solution:
def maximalNetworkRank(self, n: int, roads: list[list[int]]) -> int:
degrees = [0] * n
for u, v in roads:
degrees[u] += 1
degrees[v] += 1
# Find the first maximum and the second maximum degrees.
maxDegree1 = 0
maxDegree2 = 0
for degree in degrees:
if degree > maxDegree1:
maxDegree2 = maxDegree1
maxDegree1 = degree
elif degree > maxDegree2:
maxDegree2 = degree
# There can be multiple nodes with `maxDegree1` or `maxDegree2`.
# Find the counts of such nodes.
countMaxDegree1 = 0
countMaxDegree2 = 0
for degree in degrees:
if degree == maxDegree1:
countMaxDegree1 += 1
elif degree == maxDegree2:
countMaxDegree2 += 1
if countMaxDegree1 == 1:
# 1. If there is only one node with degree = `maxDegree1`, then we'll
# need to use the node with degree = `maxDegree2`. The answer in general
# will be (maxDegree1 + maxDegree2), but if the two nodes that we're
# considering are connected, then we'll have to subtract 1.
edgeCount = (self._getEdgeCount(roads, degrees, maxDegree1, maxDegree2) +
self._getEdgeCount(roads, degrees, maxDegree2, maxDegree1))
return maxDegree1 + maxDegree2 - (countMaxDegree2 == edgeCount)
else:
# 2. If there are more than one node with degree = `maxDegree1`, then we
# can consider `maxDegree1` twice, and we don't need to use `maxDegree2`.
# The answer in general will be 2 * maxDegree1, but if the two nodes that
# we're considering are connected, then we'll have to subtract 1.
edgeCount = self._getEdgeCount(roads, degrees, maxDegree1, maxDegree1)
maxPossibleEdgeCount = countMaxDegree1 * (countMaxDegree1 - 1) // 2
return 2 * maxDegree1 - (maxPossibleEdgeCount == edgeCount)
def _getEdgeCount(
self,
roads: list[list[int]],
degrees: list[int],
degreeU: int, degreeV: int,
) -> int:
"""
Returns the number of edges (u, v) where degress[u] == degreeU and
degrees[v] == degreeV.
"""
edgeCount = 0
for u, v in roads:
if degrees[u] == degreeU and degrees[v] == degreeV:
edgeCount += 1
return edgeCount # code by PROGIEZ
