Frontend School

Maximize Network Component Strength

DSA
medium

Maximize Network Component Strength

Medium
Matrix
Graph
BFS
DFS
Connected Components

Overview

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.

What you need to do / Task

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.

Input & output

  • Input: 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.
  • Output: number The maximum total strength of a connected component achievable after making at most one strategic change.

Clarifications

  • Connected Component: Cells with positive strength are considered connected if they are horizontally or vertically adjacent.
  • Changing a 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.
  • Empty Grid: The input grid will always be non-empty.
  • All Zeros: If the grid initially consists entirely of 0s, and you choose to change one 0 to 1, the maximum strength will be 1.

Examples

1

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.

2

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].

3

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

Constraints & assumptions

  • 1 <= grid.length, grid[0].length <= 50
  • 0 <= grid[r][c] <= 100
  • All grid[r][c] values are integers.

Out of scope

  • Optimizing for multiple strategic connection changes.
  • Handling negative connection strengths.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies and sums connected components and accurately calculates the merged strength after a potential change.
  • Systematic Exploration: The approach systematically evaluates all valid opportunities for a single strategic connection change.
  • Efficiency: The solution demonstrates an efficient time and space complexity, suitable for the given constraints.
  • Code Quality: The code is well-structured, readable, and handles edge cases gracefully.

Loading editor...