Problem overview
The method sizeOfIslands receives a grid as a vector<vector<int>>. A cell holding 1 is land and a cell holding 0 is water. An island is a group of land cells connected horizontally or vertically. Diagonal neighbours are not connected. The method returns a vector<int> with the size of every island, in any order.
In the first example the grid has 4 rows and 5 columns, and all nine land cells touch each other through their sides, so the result is [9]. In the second example the 2x2 block at the top left is one island of size 4, the lone 1 in the third row is a second island of size 1, and the two 1s at the bottom right form an island of size 2. The result can be written as [1, 4, 2], but the solution below finds the islands in the order the scan meets them and returns [4, 1, 2]. Both are correct, because the order is free.
Approach: scan the grid, and flood each island once
Scan the grid cell by cell. When the scan reaches a land cell, it has found an island that it has not counted yet. The problem is that the island has many cells, and the scan will keep meeting them one after another.
The fix is to measure the island at once and then erase it:
- Run a depth-first search (DFS) from the land cell. It visits every land cell connected to it.
- Each visited cell is counted and then turned into water by setting it to 0.
- When the search returns, the counter holds the size of the whole island, and that island no longer contains land, so the scan will not find it again.
Every island is therefore found exactly once, at its first cell in scan order (top to bottom, left to right), and every cell is processed a constant number of times.
The turning of visited cells into water also acts as the "visited" marker. Without it, two neighbouring land cells would call the search on each other forever. The solution changes the input grid for this reason, and after the call every cell of the grid is 0.
Step by step
The lesson builds the main method first and assumes the helpers exist, then writes the helpers.
- Add an
intmembernoOfCellsto the class. It counts the cells of the island being explored. The recursive search adds to the same counter in every call, so it lives on the object instead of inside the search function. - Declare
result, an emptyvector<int>, to collect the island sizes. - Loop over the rows and columns with two nested
forloops. The number of rows isgrid.size(), and the number of columns isgrid[0].size(). - Test
grid[i][j]directly as the condition. In C++ a nonzerointcounts as true, so 1 passes and 0 does not. - Reset
noOfCellsto 0 before exploring the new island, so it counts only that island. - Call
dfs(grid, i, j)to flood the island, then appendnoOfCellstoresultwithpush_back. After both loops, returnresult. - Write
dfsas avoidfunction that takes the grid by reference (&), plus a row and a column. The reference matters: the cells it turns into water must change the caller's grid, not a copy. - Stop at invalid cells. At the start of
dfs, askisValidCell, and return at once if the answer is no. Neighbours outside the grid and neighbours that are water both end the recursion here. - Count and erase. Increment
noOfCellsand set the cell to 0. - Describe the four moves as a
vector<pair<int, int>>of (row change, column change): up{-1, 0}, down{1, 0}, left{0, -1}and right{0, 1}. - Recurse on each neighbour with a range-based
forthat unpacks each pair intoauto [i, j]and callsdfs(grid, row + i, col + j). Neighbours do not need to be checked before the call, because the check at the top ofdfsrejects the bad ones. - Write
isValidCellas a single condition joined with&&: the row is between 0 and the last row, the column is between 0 and the last column, and the cell holds 1. The bounds checks come first, so an out-of-range index is never read.
The solution in C++
class Solution {
public:
bool isValidCell(vector<vector<int>> &grid, int row, int col) {
return row >= 0 && row < grid.size() &&
col >= 0 && col < grid[0].size() &&
grid[row][col] == 1;
}
void dfs(vector<vector<int>> &grid, int row, int col) {
if (!isValidCell(grid, row, col)) {
return;
}
noOfCells++;
grid[row][col] = 0;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto [i, j] : directions) {
dfs(grid, row + i, col + j);
}
}
int noOfCells;
vector<int> sizeOfIslands(vector<vector<int>>& grid) {
vector<int>result;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j]) {
noOfCells = 0;
dfs(grid, i, j);
result.push_back(noOfCells);
}
}
}
return result;
}
};
The C++ details that matter here:
- Members can be declared after use. Inside a class, a member function body can use
noOfCellsand calldfseven though they are declared further down. The compiler reads the bodies after it has seen the whole class. - Signed and unsigned comparison.
grid.size()is unsigned, whilerowis anint. Comparing them convertsrowto unsigned, so a negative row would turn into a huge number. That is whyrow >= 0is tested first, and why&&stops before the second comparison can go wrong. The same applies to columns. auto [i, j]is a structured binding (C++17). It copies each pair ofdirectionsand gives its two members names. Insidedfsthese names are local to the loop and do not conflict with the scan'siandj, which belong to a different function.- The uninitialised member is safe.
noOfCellshas no initial value, butsizeOfIslandssets it to 0 before every search, and nothing reads it earlier. - The grid is changed. Passing it by reference is what lets the search erase cells. A caller that still needs the original grid has to pass a copy.
Complexity
Let the grid have m rows and n columns.
Time: O(m * n). The scan visits every cell once. The searches together visit each land cell once, because a visited cell becomes water. Each visit makes four neighbour calls, a constant amount of work, so the total is proportional to the number of cells.
Space: O(m * n) in the worst case. The recursion depth equals the length of the longest path that the search follows, and in a grid that is one big island it can reach the number of cells. Every call also builds a small directions vector. With this code, a 300 by 300 grid made only of 1s, one island of 90,000 cells, can overflow the usual 8 MB stack. For very large islands, an iterative version with an explicit stack or a queue (breadth-first search) avoids this limit, and it keeps the same time complexity.
Edge cases and common mistakes
- No land. A grid of only 0s returns an empty vector.
- Empty grid. With no rows, the outer loop does not run, so
grid[0]is never read and the result is empty. - Diagonal cells. The grid
{{1, 0}, {0, 1}}holds two islands of size 1, because the search never looks at diagonal neighbours. - Land on the edge. Neighbours outside the grid are rejected by the bounds check in
isValidCell, so border cells need no special case. - Forgetting to reset the counter. Without
noOfCells = 0before each search, every island would be reported with the sizes of all earlier islands added to it. - Forgetting to erase the cell. Setting the cell to 0 is what stops infinite recursion. Without it, two adjacent land cells recurse into each other until the stack overflows.
- Taking the grid by value. If
dfstookvector<vector<int>> gridwithout the&, it would erase cells in its own copy, and the scan would count the same island again.
Testing
{{1,1,1,1,0},{1,1,0,1,0},{1,1,0,0,0},{0,0,0,0,0}}gives[9].{{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}}gives[4, 1, 2].{{0,0},{0,0}}gives[].{{1,0},{0,1}}gives[1, 1].{{1,1,1},{1,1,1},{1,1,1}}gives[9].
