Counting Grid Routes

Medium

A district is laid out in square blocks: its streets form a grid of rows rows and cols columns of intersections. A courier stands at the top-left intersection and has to deliver an order to the bottom-right one. To save time, the courier only ever moves down or right to a neighbouring intersection. Return the number of distinct routes from the start to the delivery point. The answer is guaranteed not to exceed 2·10⁹.

Example 1

rows=2, cols=4 → 4

The courier makes 1 move down and 3 moves right; the down move can come first, second, third or fourth, so there are 4 routes.

Example 2

rows=3, cols=3 → 6

Out of 4 moves, two go down and two go right: C(4, 2) = 6 ways to arrange them.

Example 3

rows=1, cols=9 → 1

Constraints

1 ≤ rows, cols ≤ 100
The answer does not exceed 2·10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming Combinatorics

Similar problems

Nobody Gets Their Own Gift Medium Segments on a Dotted Line Medium Sorted Vowel Words Medium Vowels Across All Pieces Medium Walks of Exactly k Steps Medium

Input

rows=2, cols=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 27 tests on the server, hidden ones included.