Count Sub Islands

MediumGraphsdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two binary grids grid1 and grid2 of the same m x n size, where 1 is land and 0 is water. An island is a maximal group of land cells connected horizontally or vertically. An island in grid2 is a **sub-island** if every one of its cells is also land in grid1. (The matching land in grid1 may extend beyond the grid2 island; that is fine.) Return the number of islands in grid2 that are sub-islands.

Examples

Input: grid1 = [[1,1,1,0],[0,1,1,0],[1,0,0,1]], grid2 = [[1,1,0,0],[0,1,0,0],[1,0,0,1]]
Output: 3
`grid2` has three islands: `{(0,0),(0,1),(1,1)}`, `{(2,0)}`, and `{(2,3)}`. Every one of their cells is land in `grid1`, so all three count.
Input: grid1 = [[1,0,1],[1,0,1]], grid2 = [[1,1,1],[0,0,0]]
Output: 0
The single island in `grid2` covers `(0,1)`, which is water in `grid1`, so it is not a sub-island.

Constraints

  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1 <= m, n <= 500
  • `grid1[i][j]` and `grid2[i][j]` are `0` or `1`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems