Number of ways you can always stay either above or below the main diagonal

Introduction:

We are given an integer ‘N’. We need to consider a N * N grid. We are currently at the top left corner of the grid. We need to find the number of ways by which we can reach the bottom right corner if we can make the right(i, j+1) or down(i+1, j) move. There is one condition that we cannot cross the diagonal while making any move.

Let us see a few examples:

Input 1: 3

Output 1: 2

Explanation 1:

We can see the 2 paths in the red and green lines.

Input 2: 6

Output 2: 42

Input 3: 4

Output 3: 5

Approach:

The number of downwards movements will always be greater than or equal to the rightward movements because we can not cross the main diagonal. It is a similar pattern to the Catalan’s number.

Based on the above observation we just need to find the Nth Catalan Number.

Also, let us find the answer for a few of the ‘N’ values.

N = 1 -> 1

N = 2 -> 1

N = 3 -> 2

N = 4 -> 5

N = 5 -> 14

N = 6 -> 42

Answer for N = (1 to 6) is following the Catalan Number Series

Nth Catalan Number (K_N) = (2NCN ) / (N + 1), where 2NCN is a binomial coefficient.

Total number of ways = K_N

Refer to the below implementation of the above approach to find the number of ways you can always stay either above or below the main diagonal

import java.util.*;
class Main {

  static int binaryCoefficient(int n, int r)
{
  int coeff = 1;
  int i;

  if (r > (n - r)) {

  // C(n, r) = C(n, n-r)
r = (n - r);
}

  for (i = 0; i < r; i++) {

  // [n * (n - 1) *---* (n - r + 1)] / [r * (r - 1) *----* 1]
coeff *= (n - i);
coeff /= (i + 1);
}
  return coeff;
}

  /*
Function to calculate
the total possible paths
without crossing the diagonal
*/
  static int totalWays(int n)
{

  /*
Update n to n - 1 as (N - 1)
catalan number is the result
*/
n--;

  int fir, sec, res;

  // Stores 2nCn
fir = binaryCoefficient(2 * n, n);

  // Stores Nth Catalan number
sec = fir / (n + 1);

  // Stores the required answer
res = sec;

  return res;
}

  // Driver Code
  public static void main(String[] args)
{
  int n = 5;

  /*
Printing the total possible paths
without crossing the diagonal
*/
System.out.print(totalWays(n));
}
}

Time Complexity: The time complexity for the above approach is O(N) (where ‘N’ is the input we are given for the matrix dimension) because we are only running an O(N) for loop for finding the Binomial Coefficient.

Space Complexity: The space complexity for the above approach is O(1) as we are using constant space for this solution

FAQs:

How do we get to know that to find the number of ways you can always stay either above or below the main diagonal can be solved using Catalan numbers?
- The number of downwards movements will always be greater than or equal to the rightward movements because we can not cross the main diagonal. It is a similar pattern to the Catalan’s number.

Based on the above observation we just need to find the Nth Catalan Number.

What is the time complexity for the approach we used to find the number of ways you can always stay either above or below the main diagonal?
- The time complexity for the above approach is O(N) (where ‘N’ is the input we are given for the matrix dimension) because we are only running an O(N) for loop for finding the Binomial Coefficient.

Key Takeaways:

In this blog, we have covered the following things:

We first discussed how we can find how you can always stay above or below the main diagonal using Catalan numbers.
Then we saw how we could implement the Catalan Number.

If you want to learn more about Arrays and want to practice some questions which require you to take your basic knowledge on Arrays a notch higher, then you can visit our Guided Path for Arrays.

Until then, All the best for your future endeavors, and Keep Coding.