What isHow to prove the time complexity forof this modified BFS code?
Difference between en2 and en3, changed 38 character(s)
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values: 0 represents an empty cell, 1 represents an obstacle that may be removed. Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m &mdash; 1, n &mdash; 1). ↵
Constraints: 1 <= m, n <= 1e5 , 2 <= m * n <= 1e5↵

<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.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;↵
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?

#### History

Revisions Rev. Lang. By When Δ Comment
en3 _Satoru_ 2022-10-07 11:46:44 38
en2 _Satoru_ 2022-10-07 07:21:45 2311
en1 _Satoru_ 2022-10-06 23:22:10 466 Initial revision (published)