Biggest Connected Component
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.
Input
- h and w: number of rows and columns in the grid
- grid: a 2D integer array of size h × w representing the grid
Returns
- Maximum possible size of the largest connected group of filled cells
Constraints
- The product of h and w is less than 1 million.
- 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 ~999 × 999 grid, your solution finishes in less than 1 second.
Example
Input:
h = 3
w = 5
grid = [
[1, 0, 1, 0, 0],
[0, 1, 0, 0, 0],
[1, 0, 1, 0, 0],
]
Output:
9
Explanation:
Alice should set the 2nd row to all 1s. This results in a connected component of size 9.
Notes about tests
There are both visible and hidden test cases.
- The hidden test cases are larger and test a wider set of cases.
- The visible test cases are in
coderbyte-tests/main_test.py.- It is OK to modify them for debugging purposes.
- Leave them in a passing state when you submit your assessment.
- If you modify the visible tests and they no longer work, it is OK to delete them as well.
- You do not need to add your own unit tests.
Hidden test cases
- SKIP_HIDDEN_TESTS can be set to True in
solution.py. - If you cannot see the output of print statements, set SKIP_HIDDEN_TESTS = True to debug.
- The hidden test cases are too large to debug with printing.
- Before submitting, set SKIP_HIDDEN_TESTS = False to ensure the hidden tests run.
- There is a test case that checks if
SKIP_HIDDEN_TESTS = False.
Performance
- Your solution must pass in 10 seconds.
- Use an efficient algorithm.
- An O(n²) algorithm with n = 100,000 is too slow.
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
