DEV Community

Ark code
Ark code

Posted on

🚨 DFS Debugging Challenge for DSA Enthusiasts 🚨

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

💡 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)