Islands Inside the Old Map

Medium

You get two maps of the same area, both m × n: old_map and new_map. In each, 1 is land and 0 is water. An island is a group of land cells joined through their sides (up, down, left, right); everything beyond the edge is water. An island of the new map is nested if every one of its cells is land on the old map as well. Return the number of nested islands on new_map.

Example 1

old_map=[[1, 1, 0], [0, 1, 0], [1, 0, 1]], new_map=[[1, 1, 0], [0, 0, 0], [1, 1, 1]] → 1

The new map has two islands. The top one, {(0, 0), (0, 1)}, lies entirely on old land. The bottom one, {(2, 0), (2, 1), (2, 2)}, touches (2, 1), which is water on the old map. The answer is 1.

Example 2

old_map=[[1, 1], [1, 1]], new_map=[[1, 0], [0, 1]] → 2

Two diagonal cells are two separate islands, and both sit on old land.

Example 3

old_map=[[0, 1]], new_map=[[1, 1]] → 0

Constraints

1 ≤ m, n ≤ 500
both maps are m × n
every cell is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Largest Forest Patch Medium A Board Cut by Slashes Medium Landlocked Land Cells Medium

Input

old_map=[[1, 1, 0], [0, 1, 0], [1, 0, 1]], new_map=[[1, 1, 0], [0, 0, 0], [1, 1, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.