200. Number of Islands
Number of Islands (LeetCode 200) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.
How to solve Number of Islands
Number of Islands is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.
Work towards the solution in these steps:
- Consider modeling the grid as a graph where each cell is a node, and land cells ('1') are potential connected components.
- Think about how you can traverse the grid to identify connected components — what graph traversal algorithms can help explore all connected land cells?
- When you find a land cell that hasn't been visited, use DFS or BFS to explore all adjacent land cells (up, down, left, right) and mark them as visited to avoid counting them multiple times.
The reference solution runs in O(m * n) time and O(m * n) space.
The Number of Islands solution and editorial walks through the full approach with reference code.
Problem statement
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'.
Topics and companies
Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix.
Reported in interviews at Amazon, Bloomberg, Microsoft, Oracle, Facebook, Apple, Uber, Google, Yandex, DoorDash, Qualtrics, Snapchat and others.
How to practise Number of Islands on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.
Open Number of Islands in the code editor, or read the Number of Islands editorial for a worked solution with its approach and complexity analysis.
Where Number of Islands sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph DFS - Connected Components / Island Counting subpattern
- The full DSA patterns sheet
Problems related to Number of Islands
Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:
- Count Sub Islands — Medium, same subpattern
- Detonate the Maximum Bombs — Medium, same subpattern
- Evaluate Division — Medium, same subpattern
- Flood Fill — Easy, same subpattern
- Island Perimeter — Easy, same subpattern
- Keys and Rooms — Medium, same subpattern
Number of Islands FAQ
What is the LeetCode number of Number of Islands?
Number of Islands is LeetCode problem 200, rated Medium.
What pattern is used to solve Number of Islands?
Number of Islands is a DFS Connected Components problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.
What is the time complexity of Number of Islands?
The reference solution runs in O(m * n) time and O(m * n) space.
Which companies ask Number of Islands?
Number of Islands has been reported in interviews at Amazon, Bloomberg, Microsoft, Oracle, Facebook, Apple, Uber, Google, Yandex, DoorDash, Qualtrics, Snapchat and others.