Count cycle in grid

Question

Given a 2D grid consisting of '1's (land) and '0's (water), write a function to count the number of distinct cycles formed by connected '1's. A cycle is defined as a closed loop where each '1' is connected to its adjacent '1's horizontally or vertically. The function should return the total count of such cycles in the grid.

Codemia · Accepted Answer

To solve the problem of counting cycles in a 2D grid of '1's (land) and '0's (water), we can use a depth-first search (DFS) approach. The reason for using DFS here is that we need to explore the grid to find connected components of '1's and determine if they form a cycle. A cycle is defined as a series of '1's that connect back to themselves without any break. By traversing the grid and marking visited '1's, we can effectively check for cycles. Each time we initiate a DFS from an unvisited '1', we will explore all connected '1's and check if we return to the starting point of our search, indicating a cycle. 1. **Initialize** a visited set to keep track of all '1's we have already processed.
2. **Iterate** through each cell in the grid.
3. When encountering a '1' that hasn’t been visited, **initiate a DFS** from this point.
4. **During the DFS**, keep track of the number of '1's visited and the starting point. Each time we move to a new '1', check its neighbors. If we encounter a previously visited '1' that is not the parent of the current node, it indicates a cycle.
5. After finishing the DFS for that component, if a cycle was detected, increment the cycle count.
6. Continue until all cells in the grid have been processed. Here’s the Python implementation of the above approach: ```python def count_cycles(grid): if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) visited = set() cycle_count = 0 def dfs(x, y, parent_x, parent_y): visited.add((x, y)) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nx, ny = x + dx, y + dy if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1': if (nx, ny) not in visited: dfs(nx, ny, x, y) elif (nx, ny) != (parent_x, parent_y): return True return False for i in range(rows): for j in range(cols): if grid[i][j] == '1' and (i, j) not in visited: if dfs(i, j, -1, -1): cycle_count += 1 return cycle_count ``` The time complexity of this solution is O(R * C), where R is the number of rows and C is the number of columns in the grid. This is because in the worst case, we might visit every cell in the grid once during the DFS. The space complexity is O(R * C) as well due to the visited set storing references for each cell in the worst-case scenario where all cells are '1's. 1. **Empty Grid**: If the grid is empty (i.e., `grid = []`), the function should return 0.
2. **All Water**: If the grid contains only '0's, it should also return 0 as there are no cycles.
3. **Single Cell Cycle**: A grid with a single '1' surrounded by '0's should return 0 as it cannot form a cycle.
4. **Multiple Disconnected Cycles**: Ensure that the function counts multiple separate cycles correctly. For example, in a 3x3 grid with '1's forming distinct loops, it should accurately reflect the number of cycles.

Count cycle in grid

Dropbox

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Dropbox Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string