AC Java DP solution v.s. TLE Dijstra solution


  • 11
    Y

    When I looked at this question, the first thought was the Dijkstra solution, which is a very fast algorithm to calculate the shortest path. But this solution got TLE in this question, while DP solution worked fine.

    I will talk about the Dijkstra solution first, as it's the first though came into my mind, and there is already discussions on the DP solution. If you are not interested in the Dijkstra solution, you can jump to the latter part of this post, which is about the DP solution, which is accepted.

    Dijkstra
    The idea of Dijkstra algorithm is to divide the graph into 2 parts, visited and unvisited.
    For every node in the visited part has a dist value. Then we need to exam every edges across the visited part and the unvisited parts, which are edges that its start node is in the visited part, while its end node is in the unvisited part. What we are looking for is one edge, which has the minimum value of (dist(start node) + the edge's value). Then we put this node into the visited part and exam the edges again.

    Following is the code. It uses a Java Heap, PriorityQueue to keep track of the minimum (dist(start node) + the edge's value), but in this question, the edge value is in the node itself, which is the same for every edges ending to it, so actually the heap just keeps track of the mimimum dist(start node) of every unvisited nodes around the boarder between visited and unvisited.

    public class Solution_dijkstra {
    
    class PointComparator implements Comparator<int[]>{
    	int[][] dist;
    	public PointComparator(int[][] dist){
    		this.dist = dist;
    	}
    	@Override
    	public int compare(int[] o1, int[] o2) {
    		int[] point1 = (int[])o1;
            int[] point2 = (int[])o2;
            return Integer.valueOf(dist[point1[0]][point1[1]])
                .compareTo(Integer.valueOf(dist[point2[0]][point2[1]]));
        }
    }
    	
    public int minPathSum(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][] visited = new boolean[m][n];
        int[][] dist = new int[m][n];
        
        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                dist[x][y] = Integer.MAX_VALUE;
            }
        }
        
        dist[0][0] = grid[0][0];
        
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>( m*n, new PointComparator(dist));
        
        pq.add(new int[]{0, 0});
        
        while(!pq.isEmpty()){
            
            int[] point = pq.poll();
            int x = point[0];
            int y = point[1];
            int d = dist[x][y];
            
            if(x == n-1 && y == m-1){
                return d;
            }
            
            visited[x][y] = true;
            
            if((y+1 < n) && !visited[x][y+1]){
                dist[x][y+1] = min(
                    dist[x][y+1],
                    d + grid[x][y+1]);
                pq.add(new int[]{x, y+1});
            }
            
            if((x+1 < m ) && !visited[x+1][y]){
                dist[x+1][y] = min(
                    dist[x+1][y],
                    d + grid[x+1][y]);
                pq.add(new int[]{x+1, y});
            }
        }
        return 0;
        
    }
    
    private int min(int i1, int i2){
    	return i1 < i2 ? i1 : i2;
    }
    

    }

    This solution got LTE error, mostly because of the priority queue and doesn't consider the special condition here that it's a grid and directed, which means a node can only be accessed from it's left and upper nodes. Put all these into consideration, we have the DP solution. It's essentially formula is

    dist(node) = min( dist(upper node), dist(left node)) + node's value

    DP
    here is the code:

    public class Solution_dp {
    
    private int getDist(int[][] dist, int x, int y){
    	if(x < 0 || y < 0){
    		return Integer.MAX_VALUE;
    	}
    	
    	return dist[x][y];		
    }
    
    private int min(int i1, int i2){
    	return i1 < i2 ? i1 : i2;
    }
    
    
    public int minPathSum(int[][] grid) {
    
    	if(grid == null || grid.length == 0) return 0;
    	
    	int m = grid.length;
    	int n = grid[0].length;
    	
    	int[][] dist = new int[m][n];
    	
    			
    	
    	for(int x = 0; x < m; x++){
    		for(int y = 0; y < n; y++){
    			
    			if(x == 0 && y == 0){
    				dist[0][0] = grid[0][0];
    			}else{
    				dist[x][y] = min(getDist(dist, x-1, y), getDist(dist, x, y-1))  + grid[x][y];					
    			}
    		}			
    	}
    
    	return dist[m-1][n-1];
    			
    }
    

    }


  • 0
    W

    Well. Dijkstra is also the first thing came to my mind. But for a question in short interview(30- min), I will write the DP solution first. And even optimize it a little bit.
    For onsite and 30+ min interview, I will still spend 10 mins writing down the DP solution and show the concise coding style. and discuss the Dijkstra solution.


  • 0

    For this particular problem, Dijkstra is simply an overkill, because of the grid and the fact that we can only move down and right.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.