PayPal Coding Question: Count Islands in 2D Grid with DFS

Overview

You are asked to implement num_islands(grid) to count distinct islands in a rectangular 2D grid composed of '1' (land) and '0' (water). An island is a group of adjacent '1' cells connected horizontally or vertically. The input is an m × n matrix (list of lists) and you should return the integer count of connected land components.

What you'll be asked to do

First, write a correct implementation (commonly using DFS or BFS to mark visited land). Typical flows: scan the matrix, when you find an unvisited '1' increment the island count and flood-fill that component (recursive DFS, iterative stack, or BFS queue) to avoid double counting. After the implementation stage, explain the time and space complexity in terms of m (rows) and n (columns).

Interview flow & expectations

• Clarify input mutability (can you modify grid in-place?) and constraints (m, n size).
• Propose DFS and BFS options and trade-offs (recursion depth vs iterative stack/queue).
• Implement a clean solution (mark visited or overwrite cells).
• Provide time/space analysis and mention edge cases (all water, all land, thin long grids).

Skills signaled

You should demonstrate matrix traversal, graph connected-components thinking, mastery of DFS/BFS variants, iterative vs recursive trade-offs, and clear time/space complexity reasoning.