Biggest Connected Component
Learn this problemProblem statement
Alice has a grid represented as a 2D integer array grid with h rows and w columns.
A cell is considered "filled" if its value is 1, and "empty" if its value is 0. A group of filled cells is connected if you can reach any cell from any other cell by moving horizontally or vertically. The size of a connected group is the number of cells in it.
Alice can perform one operation: choose a row or column and fill all its cells with 1.
Help Alice find the maximum possible size of the largest connected group of filled cells after performing the operation at most once.
Function
getBiggestConnectedComponent(h: int, w: int, grid: int[][]) → intExamples
Example 1
h = 3w = 5grid = [[1, 0, 1, 0, 0], [0, 1, 0, 0, 0], [1, 0, 1, 0, 0]]return = 9In this example, Alice should set the 2nd row to all 1s.
This connects all 5 cells in the 2nd row with the four originally filled cells in columns 1 and 3, so the largest connected group has 9 cells.
Source note: The screenshot cuts off the final output, but the grid, explanation, and stated rules make this one clear. FastPrep worked out the answer strictly from those details. If we come across a fuller version later, we'll come back and update this.
Constraints
- The product of
handwis less than1,000,000. - Your solution should work in a reasonable amount of time regardless of the contents of the grid. There are test cases checking that on a roughly
999 x 999grid, your solution finishes in less than 1 second.