bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium2-D Dynamic ProgrammingLC 62

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to 2 109.

Asked at 14 companies
AdobeAlibabaAmazon
Hints
  • 1.Think about what data structure fits Unique Paths
  • 2.Consider the brute force complexity and how to optimize
  • 3.Can you trade space for time?
LeetCodeNeetCode