Is the time complexity of BFS O((mn)^2)?


  • 0
    L

    This is my BFS solution. But some cases is TLE? So I want know what the time complexity is? Intuitively, the out loop is O(mn), the BFS is O(mn), so is it O((mn)^2)?

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if(grid.empty()) return 0;
            int m = grid.size(), n = grid[0].size();
            int count = 0;
            queue<pair<int, int> > q;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(grid[i][j] == '1'){
                        count++;
                        q.push(make_pair(i, j));
                        //BFS
                        while(!q.empty()){
                            int cur_i = q.front().first;
                            int cur_j = q.front().second;
                            q.pop();
                            //up
                            if(cur_i != 0 && grid[cur_i - 1][cur_j] == '1')
                                q.push(make_pair(cur_i - 1, cur_j));
                            //down
                            if(cur_i != m - 1 && grid[cur_i + 1][cur_j] == '1')
                                q.push(make_pair(cur_i + 1, cur_j));
                            //left
                            if(cur_j != 0 && grid[cur_i][cur_j - 1] == '1')
                                q.push(make_pair(cur_i, cur_j - 1));
                            //right
                            if(cur_j != n - 1 && grid[cur_i][cur_j + 1] == '1')
                                q.push(make_pair(cur_i, cur_j + 1));
                            grid[cur_i][cur_j] = '2';
                        }
                    }
                }
            }
            return count;
        }
    };
    

Log in to reply
 

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