I came across this implementation of Number of Islands using DFS.
At first glance, the logic seems correct and it passes many test cases. However, there's a subtle issue that can significantly impact performance on larger inputs.
Can you spot it? 👇
class Solution {
public:
int m, n;
bool isValid(int i, int j) {
return i >= 0 && j >= 0 && i < m && j < n;
}
void dfs(vector<vector<char>> &visited,
vector<vector<char>> grid,
int i, int j) {
visited[i][j] = '1';
vector<pair<int, int>> dirs = {
{-1, 0}, {1, 0}, {0, 1}, {0, -1}
};
for (int r = 0; r < 4; r++) {
int x = i + dirs[r].first;
int y = j + dirs[r].second;
if (isValid(x, y) &&
visited[x][y] == '0' &&
grid[x][y] == '1') {
dfs(visited, grid, x, y);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int totalIslands = 0;
m = grid.size();
n = grid[0].size();
vector<vector<char>> visited(
m, vector<char>(n, '0'));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == '0' &&
grid[i][j] == '1') {
dfs(visited, grid, i, j);
totalIslands++;
}
}
}
return totalIslands;
}
};
💡 Question:
What is the issue in this code?
A. DFS traversal logic is incorrect
B. Boundary checking is wrong
C. Unnecessary memory/time overhead due to parameter passing
D. There is no issue
Bonus: What would be the time complexity impact of the bug?
Drop your answer and reasoning in the comments 👇
Top comments (0)