Constraints: 1 <= m, n <= 1e5 , 2 <= m * n <= 1e5↵
↵
Problem Link: https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/↵
↵
<spoiler summary="My Code">↵
```c++↵
class Solution {↵
public:↵
bool isValid(int x,int y,int n,int m){↵
return (x>=0 && x<n && y>=0 && y<m);↵
}↵
↵
int minimumObstacles(vector<vector<int>>& grid) {↵
queue<pair<int,int>>q;↵
q.push({0,0});↵
int n = grid.size();↵
int m = grid[0].size();↵
int dist[n][m];↵
for(int i=0;i<n;i++){↵
for(int j=0;j<m;j++){↵
dist[i][j] = INT_MAX/2;↵
}↵
}↵
dist[0][0] = 0;↵
while(q.size()){↵
pair<int,int>p = q.front();↵
q.pop();↵
for(int i=-1;i<=1;i++){↵
for(int j=-1;j<=1;j++){↵
if(abs(i)+abs(j)==1){↵
if(isValid(p.first+i,p.second+j,n,m)){↵
if(grid[p.first+i][p.second+j]==0){↵
if(dist[p.first][p.second]<dist[p.first+i][p.second+j]){↵
q.push({p.first+i,p.second+j});↵
dist[p.first+i][p.second+j] = dist[p.first][p.second];↵
}↵
}else{↵
if(dist[p.first][p.second]+1<dist[p.first+i][p.second+j]){↵
q.push({p.first+i,p.second+j});↵
dist[p.first+i][p.second+j] = dist[p.first][p.second]+1;↵
} ↵
}↵
}↵
}↵
}↵
}↵
↵
}↵
return dist[n-1][m-1];↵
}↵
};↵
```↵
</spoiler>↵
↵
The solution is just a BFS where you push a neighbor of the current cell being processed if it can be reached after removal of lesser number of obstacles. Due to this a cell maybe pushed multiple times to the queue. I am not able to convince myself that the time complexity is O(nm) which it should be as per the constraints of the problem. How can we prove that each cell will be updated constant times?
