Solution: Problem Challenge 3

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 3

Table of Contents

Contents are not accessible

Problem Statement

You are given a 2D matrix containing different characters, you need to find if there exists any cycle consisting of the same character in the matrix.

A cycle is a path in the matrix that starts and ends at the same cell and has four or more cells. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same character value of the current cell.

Write a function to find if the matrix has a cycle.

Example 1

Input: matrix =

Output: true

Explanation: The given matrix has a cycle as shown below:

Example 2

Input: matrix =

Output: true

Explanation: The given matrix has one cycle as shown below:

Example 3

Input: matrix =

Output: false

Explanation: The given matrix has no cycle.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
matrix[i][j] is '0' or '1'.

Solution

The question follows the Island pattern and is quite similar to Number of Islands problem.

We will traverse the matrix linearly to find any cycle. Each cycle is like an island having cells containing same values. Hence, we can use the Depth First Search (DFS) or Breadth First Search (BFS) to traverse a cycle i.e., to find all of its connected cells with the same value.

Our approach for traversing the matrix will be similar to the one we used when searching for islands. We will keep another matrix to remember the cells that we have visited. From any given cell, we can perform DFS to traverse all the neighboring cells having the same character value.

Whenever we reach a cell that have already been visited, we can conclude that we have found a cycle. This also means that we need to be careful to not start traversing the parent cell and wrongly finding a cycle. That is, while traversing, when initiating DFS recursive calls to all the neighboring cell, we should not start a DFS call to the pervious cell, Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

Python3

. . . .

Time Complexity

Time complexity of the above algorithm will be $O(M*N)$ , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix. This is due to the fact that we have to traverse the whole matrix to find cycles.

Space Complexity

DFS recursion stack can go $M*N$ deep when the whole matrix is filled with the same character. Hence, the space complexity will be $O(M*N)$ , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible