Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
A

arya.javadi80

· 3 years ago

Why is there a return True after each recursive call, isn't it impossible to have a cycle let's say after 1 movement?

S

Sharafat Ali

· 4 years ago

can you please guide me how to solve this problem with iterative approach?

Show 1 reply
M

Mike Xu

· 4 years ago

class Solution: def containsCycle(self, grid: List[List[str]]) -> bool:

BFS

row_num = len(grid) col_num = len(grid[0]) visited = set()

def findCycleBFS(i, j, value): neighbors = deque() neighbors.append((i, j, None, None))

while neighbors: (i, j, i_prev, j_prev) = neighbors.popleft() grid[i][j] = "1" # original value is a letter, setting a number to signify visited for row_increment, col_increment in [(1, 0), (-1, 0), (0, 1), (0, -1)]: i_next, j_next = i + row_increment, j + col_increment

if i_next == i_prev and j_next == j_prev: continue # do not go back to previous cell, skipping this path if i_next < 0 or i_next >= row_num or j_next < 0 or j_next >= col_num: continue if grid[i_next][j_next] != value: continue if (i_next, j_next) in visited: #cell with the same value visited bef

A

Alfonso Vieyra

· 4 years ago

Can you explain the process of input for -1 for both prevX and prevY? x = -1 and y = -1?

Show 1 reply
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
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

'''
A00|A01|A02|V03
---|---|---|---
A10|V11|A12|A13
---|---|---|---
A20|A21|A22|V23

NULL -> 00 -> 01 -> 02 -> 12 -> 13 
         ^             -> 22 -> 22 -> 21 -> 20 -> 20 -> 10
         |                                               |
         |-----------<-------------------<-------------<-|                 

if N is the curren node and: 
   1- has been seen already and
   2- has a parent NULL
      we found the cycle 

if N is the curren and: 
   1- Has been seen already and
   2- Has a parent that is not NULL 
     Exit = "it has been visted in the previouse step"

if N is the curren node and: 
    1- Has not been seen
       - mark the neighbor as seen and set the paren to prviouse node
       - go deeper in the matrix and repeat the process
'''
class Solution:

  def
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from collections import deque

class Solution:
    def get_neighbors(self, matrix, i, j):
        neighbors = []
        rows = [-1, 0, 1, 0]
        cols = [0, 1, 0, -1]
        for k in range(len(rows)):
            x = rows[k] + i
            y = cols[k] + j
            if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix[0]):
                neighbors.append((x, y))
        return neighbors
   
    def bfs(self, matrix, row, col, ch):
        q = deque([(row, col)])
        visited = {(row, col): (None, None)} # we store the visted x,y : to parent x, y
        while q:
            x, y = q.popleft()
            for nx, ny in self.get_neighbors(matrix, x, y):
                if matrix[nx][ny] == ch:
                    # if the current cell was not visited by its ne
Pranshu Upadhaya

Pranshu Upadhaya

· 3 months ago

in the constraints , then why am i getting characters in question [["a", "b", "e", "b"], ["b", "b", "b", "b"], ["b", "c", "c", "d"], ["c", "c", "d", "d"]]

Constraints:

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