Both examples hand you a count of islands, which tempts you into labelling components first and summing them second. There is no need for two phases: a flood fill that adds a cell's value at the moment it consumes the cell produces the component sum and the component boundary in the same sweep, and the answer is a counter incremented whenever `sum % k == 0`. The alternative I rejected was union-find with a parallel `sum[root]` array. On paper it fits — components, merging, roots — but it costs a DSU, a second pass to collect sums per root, and it buys nothing, because this grid is static. Nothing merges after the fact. One sweep with an explicit stack is both shorter and, at `m * n <= 1e5`, faster. The other instinct worth naming out loud is recursive DFS. A thousand-cell snake of land is a legal input, and a 100000-deep recursion on the judge's stack is a crash waiting for the right test case. My stack is a `vector` of flattened indices `r * n + c`, so depth is a heap problem, not a stack problem. ### Worked example Take `grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]]` and `k = 5`. Scanning row-major, the first land cell is `(0,1) = 2`. The flood pulls in `(0,2) = 1` and `(1,1) = 5`, zeroing each as it goes, and ends with `sum = 8`. `8 % 5 != 0`, no count. Next survivor in scan order is `(1,4) = 5`, isolated by water on all four sides, so `sum = 5` and the counter goes to 1. Then `(2,2) = 1` opens the big one: down to `(3,2) = 4`, left to `(3,1) = 1`, right to `(3,3) = 7`, down again to `(4,1) = 2`. `sum = 15`, divisible, counter is 2. The last land left is `(4,4) = 8`, alone, `8 % 5 != 0`. Four islands visited, answer 2. ### Complexity - **Time** O(m*n) — each cell is pushed at most once, because it is zeroed before any neighbour can look at it. - **Space** O(m*n) — a snake-shaped island can sit on the stack all at once; the visited marks cost nothing extra, they live in `grid`. ### Code (C++) ```cpp class Solution { public: int countIslands(vector>& grid, int k) { int m = grid.size(), n = grid[0].size(); vector stack; int ans = 0; const int dr[4] = {1, -1, 0, 0}; const int dc[4] = {0, 0, 1, -1}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] <= 0) continue; long long sum = 0; stack.clear(); stack.push_back(i * n + j); sum += grid[i][j]; grid[i][j] = 0; // mark visited by erasing the land while (!stack.empty()) { int cur = stack.back(); stack.pop_back(); int r = cur / n, c = cur % n; for (int d = 0; d < 4; ++d) { int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue; if (grid[nr][nc] <= 0) continue; sum += grid[nr][nc]; grid[nr][nc] = 0; stack.push_back(nr * n + nc); } } if (sum % k == 0) ++ans; } } return ans; } }; ``` ### One note `sum` has to be `long long`. The constraints allow `1e5` cells at `1e6` each, so a single island can total `1e11` and an `int` accumulator wraps — and a wrapped sum still passes `% k == 0` often enough to look like a plausible wrong answer rather than an overflow. The visited trick is only legal because of how the statement defines land: islands are groups of *positive* integers, so `0` is never land. That makes writing `0` into a visited cell a safe, allocation-free marker, and it is why the guard reads `grid[i][j] <= 0` instead of `!= 0`. If the problem ever admitted negative or zero-valued land, this shortcut would silently split islands in two, and I would owe the grid a separate `visited` array. Takeaway worth carrying: when "visited" can be encoded in a value the input can never hold, say it out loud in a comment, because the next reader cannot tell a clever marker from a bug. And size the accumulator from the constraints before writing the loop, not after the wrong answer.