Clean BFS method but getting Time Limit Exceeded? Any ideas?


  • 0
    R

    The code seems clean but gets TLE. Anyone have an idea why?

    class Solution {
        void bfs(vector<vector<int>>& grid, unordered_set<string> &islands, int i, int j) {
            int m = grid.size(), n = grid[0].size();
            queue<pair<int, int>> q; // BFS queue
            q.push({i, j});
            string island = ""; // Current island
            while(!q.empty()) {
                pair<int, int> curr = q.front(); // Add the current pair to the island string
                island = island + to_string(curr.first-i) + to_string(curr.second-j);
                grid[curr.first][curr.second] = 0; // Mark the node wuth zero since it should not be visited again in the future
                q.pop();
                // Visit all the neighbors
                if(curr.first > 0    && grid[curr.first-1][curr.second]) q.push({curr.first-1, curr.second});
                if(curr.first < m-1  && grid[curr.first+1][curr.second]) q.push({curr.first+1, curr.second});
                if(curr.second > 0   && grid[curr.first][curr.second-1]) q.push({curr.first, curr.second-1});
                if(curr.second < n-1 && grid[curr.first][curr.second+1]) q.push({curr.first, curr.second+1});
            }
            islands.insert(island);
        }
    public:
        int numDistinctIslands(vector<vector<int>>& grid) {
            if(grid.empty()) return 0;
            int m = grid.size(), n = grid[0].size();
            unordered_set<string> islands; // hash set of islands
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == 1) bfs(grid, islands, i, j); // if the current entry is 1, run bfs                 
                }
            }
            return islands.size();
        }
    };```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.