Given an R x C grid of 1s and 0s (or
False values), I need a function that can find the size of the largest connected component of 1s. For example, for the following grid,
grid = [[0, 1, 0, 1], [1, 1, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]]
The answer is 5.
Here is my implementation:
def largest_connected_component(nrows, ncols, grid): """Find largest connected component of 1s on a grid.""" def traverse_component(i, j): """Returns no. of unseen elements connected to (i,j).""" seen[i][j] = True result = 1 # Check all four neighbours if i > 0 and grid[i-1][j] and not seen[i-1][j]: result += traverse_component(i-1, j) if j > 0 and grid[i][j-1] and not seen[i][j-1]: result += traverse_component(i, j-1) if i < len(grid)-1 and grid[i+1][j] and not seen[i+1][j]: result += traverse_component(i+1, j) if j < len(grid)-1 and grid[i][j+1] and not seen[i][j+1]: result += traverse_component(i, j+1) return result seen = [[False] * ncols for _ in range(nrows)] # Tracks size of largest connected component found component_size = 0 for i in range(nrows): for j in range(ncols): if grid[i][j] and not seen[i][j]: temp = traverse_component(i, j) if temp > component_size: component_size = temp return component_size
Feel free to use the following code to generate random grids to test the function,
from random import randint N = 20 grid = [[randint(0,1) for _ in range(N)] for _ in range(N)]
Problem: My implementation runs too slow (by about a factor of 3). Since I wrote this as a naive approach by myself, I am guessing there are clever optimizations that can be made.
Context: This is for solving the Gridception problem from Round 2 of Google Codejam 2018. My goal is to solve the problem in Python 3. As a result, there is a hard constraint of using only the Python 3 standard library.
I have figured out that this particular portion of the full solution is my performance bottleneck and thus, my solution fails to clear the Large Input due to being too slow.
Thank you so much!
Edit: Adding some
For a randomly generated 20 x 20 grid, my implementation takes 219 +/- 41 μs (a grid of 0s takes 30 μs, and a grid of 1s takes 380 μs).