How to prove the time complexity of this?

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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 — 1, n — 1). Constraints: 1 <= m, n <= 1e5 , 2 <= m * n <= 1e5

Problem Link: https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/

My Code

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];
    }
};

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?

Comments (5)

Write comment?

_Satoru_

18 months ago, # |

Auto comment: topic has been updated by _Satoru_ (previous revision, new revision, compare).

→ Reply

HiCode2009

You can try the worst case.The time complexity of your code is at least $$$O(nm)$$$

18 months ago, # ^ |

What will be the upper bound? It should be O(nm(n+m)) according to me but in that case the above code shouldn't be accepted but it does get accepted.

dorijanlendvaj

+11

The test cases are weak. If you try it on a test with n=2, m=4k+1 that looks like

0100

0001

repeated k times with a column of 2 0s at the end, your code would be very slow.

_Satoru_'s blog