Failure in test case 59.


  • 0
    C

    [[5,1,0,4,0,1,1,6,7,3,9,9,4,6,8,1],[9,1,0,6,4,2,8,0,1,6,0,2,7,9,0,4],[3,2,0,3,3,3,1,3,7,3,2,1,1,2,2,0],[5,2,8,2,7,6,2,0,5,3,2,4,4,4,8,9],[7,0,5,2,4,6,7,1,1,1,2,2,6,6,4,1],[0,3,5,9,1,8,0,6,3,4,0,9,9,0,9,8],[3,4,0,7,2,8,0,4,9,4,8,5,2,5,9,4],[0,4,4,1,4,6,0,7,0,2,7,1,3,8,9,8],[2,0,7,4,0,7,0,1,1,1,9,5,6,8,9,6],[4,3,9,9,1,9,8,4,2,7,5,7,5,5,5,9],[7,4,6,9,1,8,0,4,9,9,9,7,9,8,3,4],[4,3,5,7,4,5,1,8,3,7,7,0,4,4,2,3],[8,0,2,9,8,2,5,8,4,4,7,3,5,1,9,1],[6,4,8,2,2,2,1,7,1,8,7,5,5,1,0,3],[1,2,5,0,6,0,0,0,7,7,6,4,0,5,5,8],[2,5,1,4,9,4,1,0,2,0,5,7,4,7,3,5],[9,8,7,8,8,9,8,5,9,6,9,9,2,6,0,6],[4,1,2,3,5,5,4,9,5,1,9,9,9,2,7,0],[0,6,8,0,6,9,8,7,5,7,8,9,6,8,5,0]]

    expected 71.
    My code gives 72 as output, I am passing all 58 test cases before this.
    I am using Hashmap to save result of paths calculated previously.

    import java.util.*;
    public class Solution {
        public int minPathSum(int[][] grid) {
            HashMap<String,Integer> hm=new HashMap<String,Integer>();
            return recursePath(grid,grid.length-1,grid[0].length-1,hm);
        }
        
        int recursePath(int[][] grid, int r, int c, HashMap<String,Integer> hm){
            StringBuilder sb=new StringBuilder();
            sb.append(r).append(c);
            String str=sb.toString();
            if(hm.containsKey(str)){
                return hm.get(str);
            }
           
            if(r==0&&c==0){
                hm.put(str,grid[0][0]);
                return grid[0][0];
                
            }
            if(r<0||c<0){
                return Integer.MAX_VALUE;
            }
            int value1= recursePath(grid,r-1,c,hm);
            int value2= recursePath(grid,r,c-1,hm);
            int result=Math.min(value1,value2)+grid[r][c];
            hm.put(str,result);
            return result;
        }
    }
    

Log in to reply
 

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