Skip to content
Katabench
Try free

Unique Paths

Easy About 10 min Free, no account needed

Count the robot's lattice paths across the grid.

The brief

A robot starts at the top-left of an m x n grid and moves only right or down. Return the number of distinct paths to the bottom-right corner (1 <= m, n <= 18, the answer fits a long).

The performance bar

The obvious approach recurses on both moves, 2^(m+n) calls. The hidden test is the 18 x 18 grid: about 2 billion paths, each walked separately by the recursion, so it's too slow. You need to reach O(m * n) by reusing subresults instead of recomputing them.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the number of right/down lattice paths across an m x n grid.
    public long UniquePaths(int m, int n)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Dynamic programming
Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.

Related katas