beingsde
Sign In
Back to all DSA patterns
Graph / DFS•Pattern: DFS / Flood Fill•Medium

Number of islands (connected components in grid)

Problem Intuition & Objective

Count the number of islands ('1's connected 4-directionally) in a 2D grid.

Time ComplexityO(m×n)
Optimal
Space ComplexityO(m×n) worst-case recursion
Memory Bounds
Optimal Algorithmic Approach

DFS flood fill: sink visited land cells to '0'.

Core Invariants & Edge Cases

  • DFS/BFS from every unvisited '1', marking connected cells as visited
  • Each DFS invocation represents one island
  • Can mark cells '0' in-place to avoid separate visited array
Previous ProblemTask scheduler — minimum CPU intervals with cooldownNext Problem Course schedule — detect cycle in directed graph

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.