Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 3 (medium)

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

.....

.....

.....

Like the course? Get enrolled and start learning!
J

J

· 4 years ago

Curious if anyone has found a way to solve this problem with the iterative BFS approach without using an extra matrix or map or set (for tracking visited cells) to reduce the space complexity to O(min(M, N)) .

Show 3 replies