Practice/Meta/Leetcode 62. Unique Paths

Leetcode 62. Unique Paths

CodingMust

Problem

A robot is positioned at the top-left corner of an m × n grid. The robot needs to navigate to the bottom-right corner. At each step, the robot can only move either downward or rightward.

Your task is to determine how many unique paths exist for the robot to reach its destination.

Requirements

1. Calculate the total number of distinct paths from the starting position to the ending position
2. The robot must stay within the grid boundaries at all times
3. Each move must be either one cell down or one cell right
4. Return the count as an integer

Constraints

• 1 ≤ m, n ≤ 100
• The result will fit in a 32-bit signed integer (≤ 2 × 10^9)
• Time complexity: O(m × n) or better
• Space complexity: O(min(m, n)) or better preferred

Examples

Example 1:

` Input: m = 3, n = 2 Output: 3 Explanation: The robot starts at position (0,0) and must reach (2,1). The three unique paths are:

1. Right → Right → Down
2. Right → Down → Right
3. Down → Right → Right `

Example 2:

Input: m = 3, n = 7 Output: 28 Explanation: A 3×7 grid has 28 distinct monotonic paths from top-left to bottom-right.

Example 3:

Input: m = 1, n = 1 Output: 1 Explanation: When the grid is just a single cell, there is exactly 1 path (staying in place).