# 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.

Comments

## No comments yet

## Be the first to share what you think