I did LeetCode 200 number of Islands
There are 2 codes one is working fine and the other passed 38 testcases out of 47 and showed tle thereafter can you help me figure out why it happened.
https://ide.codingblocks.com/s/350432-TLE ONE
https://ide.codingblocks.com/s/350433-CORRECT ONE
Okay I am attaching the code here.
TLE ONE-
class Solution {
public:
int n,m;
bool isvalid(int r,int c)
{
if(r<0 or c<0 or r>n-1 or c>m-1)
return false;
return true;
}
int numIslands(vector<vector<char>>& grid)
{
if(grid.empty() or grid[0].empty())
return 0;
n=grid.size();
m=grid[0].size();
int islands=0;
pair<int,int> moves[4]={{0,1},{1,0},{-1,0},{0,-1}};
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++){
if(grid[i][j]=='1')
{
islands++;
queue<pair<int,int>> q;
q.push({i,j});
while(!q.empty())
{
pair<int,int> p=q.front();
grid[p.first][p.second]='0';
q.pop();
for(auto x:moves)
{
if(isvalid(p.first+x.first,p.second+x.second) and grid[p.first+x.first][p.second+x.second]=='1'){
q.push({p.first+x.first,p.second+x.second});
}
}
}
}
}
}
return islands;
}
};
CORRECT ONE-
class Solution {
public:
int n,m;
bool isvalid(int r,int c)
{
if(r<0 or c<0 or r>n-1 or c>m-1)
return false;
return true;
}
int numIslands(vector<vector<char>>& grid)
{
if(grid.empty() or grid[0].empty())
return 0;
n=grid.size();
m=grid[0].size();
int islands=0;
pair<int,int> moves[4]={{0,1},{1,0},{-1,0},{0,-1}};
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++){
if(grid[i][j]=='1')
{
islands++;
queue<pair<int,int>> q;
q.push({i,j});
grid[i][j]='0';
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
for(auto x:moves)
{
if(isvalid(p.first+x.first,p.second+x.second) and grid[p.first+x.first][p.second+x.second]=='1'){
q.push({p.first+x.first,p.second+x.second});
grid[p.first+x.first][p.second+x.second]='0';
}
}
}
}
}
}
return islands;
}
};
Here do this
if(isvalid(p.first+x.first,p.second+x.second) and grid[p.first+x.first][p.second+x.second]==‘1’){
q.push({p.first+x.first,p.second+x.second});
grid[p.first+x.first][p.second+x.second]=‘0’;
}
otherwise same node will be added multiple times to queue
Yes in the correct solution I did the same thing which you did .
And in the TLE one also ,I did the same check but at the beginning of while loop using this statement please check and can you explain why that was wrong
I did this inside whille
grid[p.first][p.second]=‘0’;
Hey this is not wrong but time inefficient because
say we have a matrix
a b c
d e f
g h i
Assume all values are 1’s
So we push a as it contains 1
we pop a and make it 0 then we push b and d
we pop b and make it 0 then we push c and e
we pop d and make it 0 then we push g and again push c(because its still 1)
and so on ,so many i,j pair value is getting pushed multiple times.
Thankyou Sir, you made my idea clear thankyou very much.