[Interview purpose] What are time & Space complexity for this code?

Правка en1, от Gajanana, 2023-12-04 08:17:56

This is DIjkstra implementation on 2D matrix, each time checking for 4 directions (Up, down, left, right)

What are the time and space complexities for this code? Why?

Problem link : https://www.geeksforgeeks.org/problems/minimum-cost-path3833/1

Problem title "Minimum Cost Path" from gfg

Code link : https://ideone.com/behL3F

int minimumCostPath(vector<vector<int>>& grid) 
    {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> cost(n,vector<int>(m,1e9));
        cost[0][0] = grid[0][0];
        
        priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, 
            greater<pair<int,pair<int,int>>>> pq;
        
        pq.push({cost[0][0],{0,0}});
        
        int row[] = {0,-1,0,1};
        int col[] = {1,0,-1,0};
        
        while(!pq.empty()){
            int cst = pq.top().first;
            int i = pq.top().second.first;
            int j = pq.top().second.second;
            pq.pop();
            
            for(int k=0;k<4;k++){
                int nr = i+row[k];
                int nc = j+col[k];
                
                if(nr<0 || nc<0 || nr>=n || nc>=m) continue;
                
                if(cost[nr][nc] > cst+grid[nr][nc]){
                    cost[nr][nc] = cst+grid[nr][nc];
                    pq.push({cost[nr][nc],{nr,nc}});
                }
            }
        }
        return cost[n-1][m-1];
    }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Gajanana 2023-12-04 08:17:56 1551 Initial revision (published)