{"id":10859,"date":"2019-01-09T02:13:44","date_gmt":"2019-01-09T02:13:44","guid":{"rendered":"http:\/\/www.softwareeverydayblog.com\/?p=10859"},"modified":"2019-01-09T02:14:09","modified_gmt":"2019-01-09T02:14:09","slug":"leetcode-unique-paths-ii","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=10859","title":{"rendered":"[Leetcode] Unique Paths II"},"content":{"rendered":"<p>[<a href=\"https:\/\/leetcode.com\/problems\/unique-paths-ii\/description\/\" rel=\"noopener\" target=\"_blank\">Problem Link<\/a>]<\/p>\n<ul>\n<li>\n<pre lang=\"text\">\r\nTotal paths ending at [i, j] are \r\n  Total paths ending at [i+1, j]  +  Total paths ending at [i, j+1]\r\n<\/pre>\n<\/li>\n<li>Typically we would keep track of the path we&#8217;re on (so as to not go around in circles). However, in this case since we can only move down or right, there is no way we can circle back to a visited cell.<\/li>\n<li>Make sure you check for obstacle (and return 0) before checking for end of grid. That way you&#8217;ll correctly return 0 for test-case [[1]].<\/li>\n<\/ul>\n<pre lang=\"java\">\r\nclass Solution {\r\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\r\n        return uniquePathsWithObstacles(obstacleGrid, 0, 0, new HashMap<String,Integer>());\r\n    }\r\n    \r\n    public int uniquePathsWithObstacles(int[][] obstacleGrid, int i, int j, Map<String,Integer> memoized) {\r\n        \r\n        if ( i >= obstacleGrid.length || j >= obstacleGrid[0].length )\r\n            return 0;\r\n        \r\n        if ( obstacleGrid[i][j] == 1 )\r\n            return 0;\r\n        \r\n        if ( i == obstacleGrid.length-1 && j == obstacleGrid[0].length-1 )\r\n            return 1;\r\n        \r\n        String key = String.valueOf(i) + \",\" + String.valueOf(j);\r\n        if (memoized.containsKey(key))\r\n            return memoized.get(key);\r\n        \r\n        int totalPaths = uniquePathsWithObstacles(obstacleGrid, i+1, j, memoized) + \r\n                    uniquePathsWithObstacles(obstacleGrid, i, j+1, memoized);\r\n        memoized.put(key, totalPaths);\r\n        \r\n        return totalPaths;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>[Problem Link] Total paths ending at [i, j] are Total paths ending at [i+1, j] + Total paths ending at [i, j+1] Typically we would keep track of the path we&#8217;re on (so as to not go around in circles). However, in this case since we can only move down or right, there is no [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-10859","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/10859","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10859"}],"version-history":[{"count":3,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/10859\/revisions"}],"predecessor-version":[{"id":10861,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/10859\/revisions\/10861"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10859"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10859"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10859"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}