Quick Overview

Count the islands in a grid of land and water cells, where land cells connect horizontally or vertically but not diagonally. An onsite coding problem that tests grid traversal, connected components, and correct handling of enclosed water and of large grids that are entirely land.

Count Islands of Horizontally or Vertically Connected Land in a Grid

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a rectangular grid in which `1` marks land and `0` marks water. An island is a maximal group of land cells connected horizontally or vertically. Return the number of islands in the grid. ### Function Signature ```python def count_islands(grid: list[list[int]]) -> int: ``` ### Rules - Two land cells belong to the same island when a path of land cells joins them, each step moving one cell up, down, left or right. - Cells that touch only at a corner are not connected. - Every cell outside the grid is water. - Coordinates in the examples are written `(row, column)`, counted from 0. ### Constraints - `1 <= len(grid) <= 300` and `1 <= len(grid[i]) <= 300`, with all rows the same length - every `grid[i][j]` is `0` or `1` ### Examples **Example 1** ```text Input: grid = [[1, 1, 0, 1], [0, 1, 0, 1], [1, 0, 0, 0], [1, 0, 1, 1]] Output: 4 ``` The islands are {(0, 0), (0, 1), (1, 1)}, {(0, 3), (1, 3)}, {(2, 0), (3, 0)} and {(3, 2), (3, 3)}. The cells (1, 1) and (2, 0) touch only at a corner, so they belong to different islands. **Example 2** ```text Input: grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]] Output: 1 ``` The ring of land is one island; the water cell it encloses does not split it. **Example 3** ```text Input: grid = [[0, 0], [0, 0]] Output: 0 ```

Overview: Count the islands in a grid of land and water cells, where land cells connect horizontally or vertically but not diagonally. An onsite coding problem that tests grid traversal, connected components, and correct handling of enclosed water and of large grids that are entirely land.

Read the full Oracle Software Engineer interview experience this question came from

You are given a rectangular grid `grid` in which `1` marks land and `0` marks water. An island is a maximal group of land cells connected horizontally or vertically. Implement `count_islands(grid)` and return the number of islands in the grid as a single integer. ### Rules - Two land cells belong to the same island when a path of land cells joins them, each step moving one cell up, down, left or right. - Cells that touch only at a corner are not connected. - Every cell outside the grid is water. - A grid with no land cells has 0 islands. - Coordinates in the examples are written `(row, column)`, counted from 0. ### Constraints - `1 <= len(grid) <= 300` and `1 <= len(grid[i]) <= 300`, with all rows the same length - every `grid[i][j]` is `0` or `1` The answer is between 0 and 90,000 (300 x 300 cells), so it never exceeds 2^31 - 1 and fits a 32-bit `int` in every language. ### Example 1 ```text Input: grid = [[1, 1, 0, 1], [0, 1, 0, 1], [1, 0, 0, 0], [1, 0, 1, 1]] Output: 4 ``` The islands are {(0, 0), (0, 1), (1, 1)}, {(0, 3), (1, 3)}, {(2, 0), (3, 0)} and {(3, 2), (3, 3)}. The cells (1, 1) and (2, 0) touch only at a corner, so they belong to different islands. ### Example 2 ```text Input: grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]] Output: 1 ``` The ring of land is one island; the water cell it encloses does not split it.

Constraints

  • 1 <= len(grid) <= 300 and 1 <= len(grid[i]) <= 300, with all rows the same length
  • every grid[i][j] is 0 or 1

Examples

Input: ([[0]],)

Expected Output: 0

Explanation: Smallest grid, a single water cell: no islands.

Input: ([[1]],)

Expected Output: 1

Explanation: Smallest grid, a single land cell surrounded by outside water: one island.

Hints

  1. Each land cell belongs to exactly one island. Think about how to count an island once, no matter which of its cells you reach first.
  2. An island can bend back up or to the left, as in a U shape or a spiral, so the cells directly above and to the left of a land cell cannot decide on their own whether it starts a new island.
  3. In a 300 x 300 grid a single island can wind through tens of thousands of cells, so check how deep your exploration of one island can go.

Loading coding console...

Show the approach

Approach

Scan the cells in row-major order while keeping one visited marker per cell. When the scan meets a land cell that is not yet marked, it has found an island that has not been counted yet: add 1 to the count and flood-fill from that cell with an explicit stack, marking each land neighbour (up, down, left or right, inside the grid) as visited at the moment it is pushed. Invariant: after each fill, every cell of every island counted so far is marked, and no other cell is. The fill only steps between edge-adjacent land cells, so it never crosses water, never follows a corner-only contact and never leaves the grid (outside cells are water); and it reaches every land cell joined to the start by such a path, so one fill marks exactly one whole island. Therefore each island is counted exactly once, at its first cell in row-major order, and the final count is the number of islands. Edge cases: an all-water grid returns 0, a single land cell returns 1, a ring of land around water stays one island while land inside the enclosed water is a separate island, and islands that bend back up or to the left (U shapes, spirals) are still filled completely because the fill moves in all four directions. Because the fill uses an explicit stack instead of recursion, a single island winding through up to 90,000 cells cannot overflow the call stack. Each cell is pushed at most once and checks four neighbours.

Time complexity:
O(R * C), where R is the number of rows and C the number of columns
Space complexity:
O(R * C) for the visited markers and the stack