Problem

You are given an n x n grid. A driverless car starts at the bottom-left corner (0, 0) and must reach the top-right corner (n-1, n-1). The car can only move either one step East (right, increasing i) or one step North (up, increasing j) at each move. However, the car is not allowed to cross the main diagonal, i.e., it can only visit cells where i >= j at all times.

Task: Write a function numOfPathsToDest(n) that returns the number of unique valid paths from (0, 0) to (n-1, n-1) under these constraints.

Grid Representation:

  • Each cell is represented as (i, j) where i is the column (East-West) and j is the row (South-North).
  • The car may only move in the white squares (where i >= j).

Examples

Example 1

$$ \begin{array}{|c|c|c|c|} \colorbox{red} & \colorbox{red} & \colorbox{red} \phantom{000} & \colorbox{green} (4,4) \\ \hline \colorbox{red} & \colorbox{red} & \colorbox{white} & \colorbox{white} \\ \hline \colorbox{red} & \colorbox{white} & \colorbox{white} & \colorbox{white} \\ \hline

\colorbox{blue} (0,0) & \colorbox{white} (1,0) & \colorbox{white} & \colorbox{white} \end{array} $$

1
2
3
4
5

Input:  n = 4
Output:  5
Explanation:
There are 5 valid paths: [EEENNN, EENENN, ENEENN, ENENEN, EENNEN]
Where 'E' = East, 'N' = North. The car can only move in white squares (i >= j).

Example 2

$$ \begin{array}{|c|c|c|c|c|} \colorbox{red} & \colorbox{red} & \colorbox{red} \phantom{000} & \colorbox{red} \phantom{000} & \colorbox{green} (5,5) \\ \hline \colorbox{red} & \colorbox{red} & \colorbox{red} & \colorbox{white} & \colorbox{white} \\ \hline \colorbox{red} & \colorbox{red} & \colorbox{white} & \colorbox{white} & \colorbox{white} \\ \hline \colorbox{red} & \colorbox{white} & \colorbox{white} & \colorbox{white} & \colorbox{white} \\ \hline \colorbox{blue} (0,0) & \colorbox{white} (0,1) & \colorbox{white} & \colorbox{white} & \colorbox{white} \end{array} $$

1
2
3
4
5
6
7

Input:
  n = 5
Output:
  14
Explanation:
  There are 14 valid paths from (0,0) to (4,4) without crossing the main diagonal (i >= j).
  Paths are not listed for brevity.

Constraints

  • [time limit] 5000ms
  • [input] integer n
    • 1 ≤ n ≤ 100
  • [output] integer

Solution

Method 1: Recursion (Brute Force)

Intuition

Try all possible paths from the start cell to the end cell, moving only East or North, and only visiting cells where i >= j. At each step, branch into two recursive calls: one moving East, one moving North, if allowed.

Approach

  • Define a recursive function count(i, j, n) that returns the number of valid paths from cell (i, j) to (n-1, n-1).
  • Base case: If (i, j) is out of bounds or i < j, return 0 (invalid path).
  • If (i, j) is the destination, return 1.
  • Otherwise, recursively sum the number of paths by moving East (i+1, j) and North (i, j+1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
	int numOfPathsToDest(int n) {
		return count(0, 0, n);
	}
private:
	int count(int i, int j, int n) {
		if (i >= n || j >= n || i < j) return 0;
		if (i == n-1 && j == n-1) return 1;
		return count(i+1, j, n) + count(i, j+1, n);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func numOfPathsToDest(n int) int {
	var count func(i, j int) int
	count = func(i, j int) int {
		if i >= n || j >= n || i < j {
			return 0
		}
		if i == n-1 && j == n-1 {
			return 1
		}
		return count(i+1, j) + count(i, j+1)
	}
	return count(0, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	public int numOfPathsToDest(int n) {
		return count(0, 0, n);
	}
	private int count(int i, int j, int n) {
		if (i >= n || j >= n || i < j) return 0;
		if (i == n-1 && j == n-1) return 1;
		return count(i+1, j, n) + count(i, j+1, n);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	fun numOfPathsToDest(n: Int): Int {
		fun count(i: Int, j: Int): Int {
			if (i >= n || j >= n || i < j) return 0
			if (i == n-1 && j == n-1) return 1
			return count(i+1, j) + count(i, j+1)
		}
		return count(0, 0)
	}
}
1
2
3
4
5
6
7
8
9

class Solution:
	def numOfPathsToDest(self, n: int) -> int:
		def count(i: int, j: int) -> int:
			if i >= n or j >= n or i < j:
				return 0
			if i == n-1 and j == n-1:
				return 1
			return count(i+1, j) + count(i, j+1)
		return count(0, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
	pub fn num_of_paths_to_dest(n: i32) -> i32 {
		fn count(i: i32, j: i32, n: i32) -> i32 {
			if i >= n || j >= n || i < j {
				return 0;
			}
			if i == n-1 && j == n-1 {
				return 1;
			}
			count(i+1, j, n) + count(i, j+1, n)
		}
		count(0, 0, n)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	numOfPathsToDest(n: number): number {
		function count(i: number, j: number): number {
			if (i >= n || j >= n || i < j) return 0;
			if (i === n-1 && j === n-1) return 1;
			return count(i+1, j) + count(i, j+1);
		}
		return count(0, 0);
	}
}

Method 2: Recursion with Memoization (Top-Down DP)

Intuition

The brute-force recursion repeats the same subproblems many times. By storing the result of each subproblem (i, j) in a memoization table, we avoid redundant work and make the solution efficient.

Approach

  • Use a 2D memoization table (array or map) to cache the number of paths from each cell (i, j).
  • If the result for (i, j) is already computed, return it directly.
  • Otherwise, compute recursively as in Method 1, and store the result before returning.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
class Solution {
public:
	int numOfPathsToDest(int n) {
		std::vector<std::vector<int>> memo(n, std::vector<int>(n, -1));
		return count(0, 0, n, memo);
	}
private:
	int count(int i, int j, int n, std::vector<std::vector<int>>& memo) {
		if (i >= n || j >= n || i < j) return 0;
		if (i == n-1 && j == n-1) return 1;
		if (memo[i][j] != -1) return memo[i][j];
		return memo[i][j] = count(i+1, j, n, memo) + count(i, j+1, n, memo);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func numOfPathsToDest(n int) int {
	memo := make([][]int, n)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var count func(i, j int) int
	count = func(i, j int) int {
		if i >= n || j >= n || i < j {
			return 0
		}
		if i == n-1 && j == n-1 {
			return 1
		}
		if memo[i][j] != -1 {
			return memo[i][j]
		}
		memo[i][j] = count(i+1, j) + count(i, j+1)
		return memo[i][j]
	}
	return count(0, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public int numOfPathsToDest(int n) {
		int[][] memo = new int[n][n];
		for (int[] row : memo) java.util.Arrays.fill(row, -1);
		return count(0, 0, n, memo);
	}
	private int count(int i, int j, int n, int[][] memo) {
		if (i >= n || j >= n || i < j) return 0;
		if (i == n-1 && j == n-1) return 1;
		if (memo[i][j] != -1) return memo[i][j];
		return memo[i][j] = count(i+1, j, n, memo) + count(i, j+1, n, memo);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun numOfPathsToDest(n: Int): Int {
		val memo = Array(n) { IntArray(n) { -1 } }
		fun count(i: Int, j: Int): Int {
			if (i >= n || j >= n || i < j) return 0
			if (i == n-1 && j == n-1) return 1
			if (memo[i][j] != -1) return memo[i][j]
			memo[i][j] = count(i+1, j) + count(i, j+1)
			return memo[i][j]
		}
		return count(0, 0)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
	def numOfPathsToDest(self, n: int) -> int:
		memo = [[-1]*n for _ in range(n)]
		def count(i: int, j: int) -> int:
			if i >= n or j >= n or i < j:
				return 0
			if i == n-1 and j == n-1:
				return 1
			if memo[i][j] != -1:
				return memo[i][j]
			memo[i][j] = count(i+1, j) + count(i, j+1)
			return memo[i][j]
		return count(0, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
	pub fn num_of_paths_to_dest(n: i32) -> i32 {
		fn count(i: i32, j: i32, n: i32, memo: &mut Vec<Vec<i32>>) -> i32 {
			if i >= n || j >= n || i < j {
				return 0;
			}
			if i == n-1 && j == n-1 {
				return 1;
			}
			if memo[i as usize][j as usize] != -1 {
				return memo[i as usize][j as usize];
			}
			memo[i as usize][j as usize] = count(i+1, j, n, memo) + count(i, j+1, n, memo);
			memo[i as usize][j as usize]
		}
		let mut memo = vec![vec![-1; n as usize]; n as usize];
		count(0, 0, n, &mut memo)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	numOfPathsToDest(n: number): number {
		const memo: number[][] = Array.from({length: n}, () => Array(n).fill(-1));
		function count(i: number, j: number): number {
			if (i >= n || j >= n || i < j) return 0;
			if (i === n-1 && j === n-1) return 1;
			if (memo[i][j] !== -1) return memo[i][j];
			memo[i][j] = count(i+1, j) + count(i, j+1);
			return memo[i][j];
		}
		return count(0, 0);
	}
}

Method 3: Bottom-Up Dynamic Programming (Tabulation)

Intuition

Instead of solving subproblems recursively, we can fill a DP table iteratively from the base cases up, using the allowed moves and diagonal constraint.

Approach

  • Create a 2D DP table dp[i][j] where each cell stores the number of ways to reach (i, j) from (0, 0).
  • Only fill cells where i >= j (below or on the main diagonal).
  • The start cell (0, 0) is initialized to 1.
  • For each cell (i, j), the number of ways to reach it is the sum of ways to reach from the left (i-1, j) and from below (i, j-1), if those cells are valid and satisfy the diagonal constraint.
  • The answer is in dp[n-1][n-1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
class Solution {
public:
	int numOfPathsToDest(int n) {
		std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
		dp[0][0] = 1;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= i; ++j) {
				if (i > 0) dp[i][j] += dp[i-1][j];
				if (j > 0) dp[i][j] += dp[i][j-1];
			}
		}
		return dp[n-1][n-1];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func numOfPathsToDest(n int) int {
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	dp[0][0] = 1
	for i := 0; i < n; i++ {
		for j := 0; j <= i; j++ {
			if i > 0 {
				dp[i][j] += dp[i-1][j]
			}
			if j > 0 {
				dp[i][j] += dp[i][j-1]
			}
		}
	}
	return dp[n-1][n-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public int numOfPathsToDest(int n) {
		int[][] dp = new int[n][n];
		dp[0][0] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (i > 0) dp[i][j] += dp[i-1][j];
				if (j > 0) dp[i][j] += dp[i][j-1];
			}
		}
		return dp[n-1][n-1];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun numOfPathsToDest(n: Int): Int {
		val dp = Array(n) { IntArray(n) }
		dp[0][0] = 1
		for (i in 0 until n) {
			for (j in 0..i) {
				if (i > 0) dp[i][j] += dp[i-1][j]
				if (j > 0) dp[i][j] += dp[i][j-1]
			}
		}
		return dp[n-1][n-1]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
	def numOfPathsToDest(self, n: int) -> int:
		dp = [[0]*n for _ in range(n)]
		dp[0][0] = 1
		for i in range(n):
			for j in range(i+1):
				if i > 0:
					dp[i][j] += dp[i-1][j]
				if j > 0:
					dp[i][j] += dp[i][j-1]
		return dp[n-1][n-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
	pub fn num_of_paths_to_dest(n: i32) -> i32 {
		let n = n as usize;
		let mut dp = vec![vec![0; n]; n];
		dp[0][0] = 1;
		for i in 0..n {
			for j in 0..=i {
				if i > 0 {
					dp[i][j] += dp[i-1][j];
				}
				if j > 0 {
					dp[i][j] += dp[i][j-1];
				}
			}
		}
		dp[n-1][n-1]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	numOfPathsToDest(n: number): number {
		const dp: number[][] = Array.from({length: n}, () => Array(n).fill(0));
		dp[0][0] = 1;
		for (let i = 0; i < n; i++) {
			for (let j = 0; j <= i; j++) {
				if (i > 0) dp[i][j] += dp[i-1][j];
				if (j > 0) dp[i][j] += dp[i][j-1];
			}
		}
		return dp[n-1][n-1];
	}
}

Complexity

  • ⏰ Time complexity: O(n^2) — We fill an n x n DP table, but only the lower triangle (i >= j), so O(n^2) operations.
  • 🧺 Space complexity: O(n^2) — For the DP table.