Start learning free

LESSON 337 OF 347 · GRAPHS

Size of Islands in C#: Depth-First Search on a Grid

Practice O(n * m) Read the full explanation

Given a 2d grid map of '1's (land) and '0's (water), find the islands and return an array containg their sizes. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Example 1:

Input:
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

Output: [9]
Explanation:  There is only one island with size 9

Example 2:

Input:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: [1, 4, 2]
Explanation There are three islands with sizes of 1, 4 and 2

Note: The islands' sizes can be returned in any order

STEP 1 OF 17
    Ctrl + Enter to check

    C# · GRAPHS

    Size Of Islands in C#, explained

    Problem overview

    The grid is a two-dimensional int[,] in which 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically. Diagonal neighbours do not connect. SizeOfIslands returns a List<int> holding the size of each island, in any order. The edges of the grid are assumed to be water, but the code below doesn't depend on that.

    In the first example, all nine land cells are linked, so the result is [9]. In the second example the grid has a block of four cells, a single cell, and a pair of cells, so the sizes are 4, 1 and 2. This lesson's code scans the grid row by row, so it reports them as [4, 1, 2].

    Approach: scan, flood, count

    Scan every cell in row order. When you meet a land cell that you haven't seen, you have found a new island. Then run a depth-first search from that cell that visits every land cell connected to it and counts them. The count is the island's size.

    To avoid visiting a cell twice, and to avoid counting the same island again later in the scan, the search turns each land cell it visits into water. The scan then skips those cells automatically. This "sink as you go" trick means no separate visited array is needed, at the price of changing the grid you were given.

    The search is recursive. From a land cell it calls itself on the four neighbours. A neighbour that is outside the grid or already water returns at once, so the recursion stops at the island's border.

    Step by step

    1. Declare an int field noOfCells on the class. The recursive search adds to it at every level, so it lives outside the method.
    2. In SizeOfIslands, create result, an empty List<int>.
    3. Write two nested for loops. The outer one runs i from 0 to grid.GetLength(0) (rows) and the inner one runs j up to grid.GetLength(1) (columns).
    4. If grid[i, j] == 1, you have found an unvisited island.
    5. Reset noOfCells to 0, so it counts only this island.
    6. Call Dfs(grid, i, j). On return, every cell of the island is water and noOfCells holds its size.
    7. Add noOfCells to result.
    8. After both loops, return result.
    9. Write Dfs(int[,] grid, int row, int col) as a void method. First, if IsValidCell says the cell isn't a usable land cell, return immediately.
    10. Otherwise count the cell with noOfCells++ and set grid[row, col] = 0. Doing the second part before recursing is what stops two adjacent land cells from calling each other forever.
    11. Define directions as four offsets: up, down, left and right. Loop over them and call Dfs on (row + d[0], col + d[1]). Out-of-range and water neighbours are rejected by the check at the top.
    12. Write IsValidCell as one boolean expression: the row is in range, the column is in range, and the cell holds 1. The range checks come first, and && stops evaluating at the first false part, so grid[row, col] is never read with a bad index.

    The solution in C#

    class Solution {

    public bool IsValidCell(int[,] grid, int row, int col) {
        return row >= 0 && row < grid.GetLength(0) &&
        col >= 0 && col < grid.GetLength(1) &&
        grid[row, col] == 1;
    }

    public void Dfs(int[,] grid, int row, int col) {
        if (!IsValidCell(grid, row, col)) {
            return;
        }
        noOfCells++;
        grid[row, col] = 0;
        int[][] directions = new int[][] { new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1} };
        foreach (int[] d in directions) {
            Dfs(grid, row + d[0], col + d[1]);
        }
    }

    int noOfCells;

    public List<int> SizeOfIslands(int[,] grid) {
        List<int> result = new List<int>();
        for (int i = 0; i < grid.GetLength(0); ++i) {
            for (int j = 0; j < grid.GetLength(1); ++j) {
                if (grid[i, j] == 1) {
                    noOfCells = 0;
                    Dfs(grid, i, j);
                    result.Add(noOfCells);
                }
            }
        }
        return result;
    }
}

    Trace the second example. The scan finds land at (0, 0). Dfs counts it, sinks it, and spreads to (1, 0), (0, 1) and (1, 1), so the first island has 4 cells. Later the scan reaches (2, 2), a lone land cell: all four neighbours are water or out of range, so the size is 1. Finally it reaches (3, 3), whose right neighbour (3, 4) is land, and the size is 2.

    Some C# details:

    • int[,] is a rectangular array. You read a cell with grid[i, j], not grid[i][j]. It has no .Length per row. GetLength(0) is the number of rows and GetLength(1) the number of columns. (grid.Length would be the total cell count.)
    • Jagged versus rectangular. directions is a jagged array, int[][], where each element is its own int[]. It is created with new int[][] { new int[]{-1, 0}, ... }.
    • The grid is modified. Arrays are reference types, so Dfs changes the caller's array, not a copy. After SizeOfIslands runs, the grid is all water. Copy it first with (int[,])grid.Clone() if you need the original.
    • A field as a counter. noOfCells is an instance field, which C# initialises to 0 and which every call shares. An alternative is to make Dfs return a count: 1 + the sum of the four recursive calls.
    • Method order. C# lets a method call another that is declared later in the class, so IsValidCell and Dfs can sit above or below their callers.

    Complexity

    Time: O(R * C) for a grid with R rows and C columns. The scan touches each cell once. Each land cell is entered by the search once and turned to water, and every call does a constant amount of work, with four neighbour checks.

    Space: O(R * C) in the worst case, for the recursion depth. A grid that is all land can make the search go as deep as the number of cells. The result list is smaller than that.

    Edge cases and common mistakes

    • No land. An all-water grid returns an empty list.
    • Diagonal cells. In {{1,0},{0,1}} the two land cells touch only at a corner, so they are two islands of size 1: the result is [1, 1].
    • Forgetting to sink the cell. If Dfs doesn't set the cell to 0, the recursion never ends: each cell calls its neighbour, which calls it back.
    • Not resetting the counter. Without noOfCells = 0 before each search, each size includes the previous islands' cells.
    • Swapping the bounds checks. Reading grid[row, col] before checking the range throws IndexOutOfRangeException at the edges.
    • Mixing up rows and columns. GetLength(0) bounds the row index and GetLength(1) the column index. On a non-square grid, swapping them goes out of range.

    Testing

    • Rows 11110 / 11010 / 11000 / 00000 give [9].
    • Rows 11000 / 11000 / 00100 / 00011 give [4, 1, 2].
    • Rows 00 / 00 give [].
    • Rows 10 / 01 give [1, 1].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free