Grokking the Engineering Manager Coding Interview
Vote

0% completed

​

Introduction to Island Pattern

You are given a grid of land and water. Count the separate islands.

An island is a group of land cells connected up, down, left, or right.

1 1 0 0
1 0 0 1        three islands
0 0 1 0

A grid can be treated as a graph:

  • Every cell is a node.
  • Each cell connects to nearby cells.
  • The row and column numbers tell us where the neighbours are.

We do not need to build an adjacency list.

Scan every cell. When you find unvisited land, you have found a new island. Start a traversal and mark every connected land cell.

.....

.....

.....

Like the course? Get enrolled and start learning!
Z

zaid

· 3 years ago

title

Show 1 reply

Reading Progress

0%

Vote for new content