Gajanana's blog

By Gajanana, history, 3 months ago, In English

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 :

Problem title "Minimum Cost Path" from gfg

Code link :

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;
        int row[] = {0,-1,0,1};
        int col[] = {1,0,-1,0};
            int cst =;
            int i =;
            int j =;
            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];
        return cost[n-1][m-1];
  • Vote: I like it
  • 0
  • Vote: I do not like it

3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well Djikstra with priority queue is $$$O(m log n)$$$, so in your case it must be $$$O(mn log(mn))$$$

Because number of edges is $$$O(mn)$$$ (4 per cell and 3 for sides, 2 for corners) and number of nodes are $$$mn$$$