Maximize Network Component Strength
LinkedIn users often want to understand and optimize their network's impact. Imagine a simplified representation of a user's local professional network as a grid, where each cell (r, c) contains a non-negative integer representing the "connection strength" of a person at that position. A strength of 0 indicates no active connection, while a positive value signifies an active connection. The goal is to identify the strongest connected component of active connections within this network. To strategically boost their network's reach, a user can make one new basic connection (changing a 0-strength cell to a 1-strength cell) to potentially merge existing clusters or create a new impactful one.
Given a 2D array grid representing a user's network connection strengths, determine the maximum possible total strength of any single connected component after potentially changing at most one 0-strength cell to 1.
grid: number[][]
A 2D array where grid[r][c] denotes the connection strength at row r and column c. 0 indicates no connection, and positive integers indicate active connections.number
The maximum total strength of a connected component achievable after making at most one strategic change.0: You have the option to change at most one cell with strength 0 to a cell with strength 1. If no 0 cells exist, or if making such a change does not improve the maximum component strength, the result should reflect the largest existing component without any changes.grid will always be non-empty.0s, and you choose to change one 0 to 1, the maximum strength will be 1.Examples
Example 1
Input:
grid = [[1,0,1],[0,0,0],[1,0,1]]
Output:
3
Note:
Initially, there are four separate components, each with strength 1. The maximum initial strength is 1. If we change grid[0][1] (or any other 0 cell that connects two existing components) to 1, it connects grid[0][0] and grid[0][2]. The new component formed at grid[0][1] would have a strength of 1 (for itself) + 1 (from grid[0][0]) + 1 (from grid[0][2]) = 3. This is the maximum achievable.
Example 2
Input:
grid = [[1,1,0],[1,0,1],[0,1,1]]
Output:
7
Note:
Initially, there are two components: one at top-left (strength 3) and one at bottom-right (strength 3). The maximum initial strength is 3. If we change grid[0][2] to 1, it connects the top-left component (strength 3) and the top-right part of the bottom-right component (strength 1 from grid[1][2]). The total strength would be 1 (for grid[0][2]) + 3 (from top-left) + 3 (from bottom-right) = 7. The same result can be achieved by changing grid[1][1] or grid[2][0].
Example 3
Input:
grid = [[0,0],[0,0]]
Output:
1
Note:
The grid consists entirely of 0s. The maximum initial strength is 0. By changing any single 0 cell to 1 (e.g., grid[0][0]), a new component of strength 1 is formed. This is the maximum possible.
Constraints
1 <= grid.length, grid[0].length <= 500 <= grid[r][c] <= 100grid[r][c] values are integers.Loading editor...