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

• 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;
}
};
``````

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