DEV Community

loading...

Discussion on: A Google Interview Question

Collapse
vidit1999 profile image
Vidit Sarkar

I think the expected answer of first additional example should be 3 and for third it should be 1.
Here is why.
I have shown the holes with indices (0-based indexing is used).

matrix_first = [
    "01111"
    "01101"
    "00011"
    "11110"
]
First Hole : (0, 0), (1, 0), (2, 0), (2, 1), (2, 2)
Second Hole : (1, 3)
Third Hole : (3, 4)
Enter fullscreen mode Exit fullscreen mode
matrix_second = [
    "110",
    "000",
    "111"
]
First and Only Hole : (0, 2), (1, 2), (1, 1), (1, 0)
Enter fullscreen mode Exit fullscreen mode

We need to keep in mind that,

A contiguous region is one where there is a connected group of 0's going in one or more of four directions: up, down, left, or right.

This is why for the first case (1, 3) is a separate hole.