Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute island size in grid states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute island size in grid

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an m x n binary matrix grid of 0s (water) and 1s (land), where an island is a group of 1s connected 4-directionally, implement sizeOfIsland(grid, r, c) that returns the number of cells in the island containing cell (r, c); return 0 if (r, c) is water or out of bounds. You may either mutate grid (e.g., marking visited) or use an auxiliary visited structure—explain your choice. Describe the algorithm (DFS or BFS), clearly state the base cases, and analyze time and space complexity. Follow-up: adapt your solution to compute the size of the largest island in the entire grid.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute island size in grid states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute Island Size in Grid

Given an m x n binary matrix `grid` of 0s (water) and 1s (land), an island is a maximal group of 1s connected 4-directionally (up, down, left, right). Implement `sizeOfIsland(grid, r, c)` that returns the number of cells in the island that contains cell `(r, c)`. Return 0 if `(r, c)` is water or out of bounds. Use DFS (iterative stack) flood-fill from the starting cell, tracking visited cells with an auxiliary `visited` set so the input grid is not mutated. Base cases: return 0 immediately when the grid is empty, when `(r, c)` is outside the matrix, or when the starting cell is water. Otherwise expand to all 4-directionally connected land cells, counting each cell once.

Constraints

  • 1 <= m, n (grid may also be empty: [] or [[]])
  • grid[i][j] is 0 or 1
  • r and c may be any integer (out-of-bounds returns 0)
  • Islands are connected 4-directionally only (no diagonals)

Examples

Input: ([[1,1,0],[0,1,0],[0,0,1]], 0, 0)

Expected Output: 3

Explanation: Cells (0,0),(0,1),(1,1) form one connected island of size 3.

Input: ([[1,1,0],[0,1,0],[0,0,1]], 2, 2)

Expected Output: 1

Explanation: Cell (2,2) is an isolated land cell; its island has size 1.

Hints

  1. The base cases are the tricky part: handle empty grid, out-of-bounds (r, c), and water at the start before doing any traversal.
  2. Use an explicit stack (iterative DFS) or a queue (BFS) to flood-fill. Mark a cell visited the moment you push it, not when you pop it, to avoid double-counting.
  3. An auxiliary visited set keeps the input grid immutable; alternatively you could temporarily flip 1s to 0s, but state the trade-off.

Largest Island in the Grid (Follow-up)

Follow-up to the island-size problem. Given an m x n binary matrix `grid` of 0s (water) and 1s (land) where islands are groups of 1s connected 4-directionally, return the size of the largest island in the entire grid. Return 0 if there is no land. Scan every cell; whenever you reach an unvisited land cell, run a DFS/BFS flood-fill to measure that whole island, track the maximum size seen, and continue. A 2D `visited` matrix ensures each cell is counted exactly once across all islands, keeping the overall pass linear in the number of cells.

Constraints

  • 1 <= m, n (grid may also be empty: [] or [[]])
  • grid[i][j] is 0 or 1
  • Islands are connected 4-directionally only (no diagonals)
  • Return 0 when the grid contains no land

Examples

Input: ([[1,1,0],[0,1,0],[0,0,1]],)

Expected Output: 3

Explanation: Largest island is the size-3 cluster at the top-left; the lone (2,2) cell has size 1.

Input: ([[0,0],[0,0]],)

Expected Output: 0

Explanation: No land in the grid, so the largest island size is 0.

Hints

  1. Reuse the single-island flood-fill, but call it from a double loop over every cell, skipping cells you have already visited.
  2. A shared visited matrix across the whole scan guarantees O(m*n) total work — you never re-traverse a counted island.
  3. Track the running maximum island size; the answer is 0 if every cell is water.

Loading coding console...