Open In App

Dyck path

Last Updated : 11 Apr, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Consider a n x n grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (n-1, 0) to top right, i.e., (0, n-1) that lies above the diagonal cells (or cells on line from bottom left to top right).
The task is to count the number of Dyck Paths from (n-1, 0) to (0, n-1).
Examples : 

Input : n = 1
Output : 1

Input : n = 2
Output : 2

Input : n = 3
Output : 5

Input : n = 4
Output : 14


 

dyckpaths


The number of Dyck paths from (n-1, 0) to (0, n-1) can be given by the Catalan numberC(n).
C_n=\frac{(2n)!}{(n+1)!n1}=\prod_{k=2}^{n}\frac{n+k}{k} \ for\ n\geq 0
 

We strongly recommend that you click here and practice it, before moving on to the solution.


Below are the implementations to find count of Dyck Paths (or n’th Catalan number).

C++

// C++ program to count
// number of Dyck Paths
#include<iostream>
using namespace std;
 
// Returns count Dyck
// paths in n x n grid
int countDyckPaths(unsigned int n)
{
    // Compute value of 2nCn
    int res = 1;
    for (int i = 0; i < n; ++i)
    {
        res *= (2 * n - i);
        res /= (i + 1);
    }
 
    // return 2nCn/(n+1)
    return res / (n+1);
}
 
// Driver Code
int main()
{
    int n = 4;
    cout << "Number of Dyck Paths is "
         << countDyckPaths(n);
    return 0;
}

                    

Java

// Java program to count
// number of Dyck Paths
class GFG
{
    // Returns count Dyck
    // paths in n x n grid
    public static int countDyckPaths(int n)
    {
        // Compute value of 2nCn
        int res = 1;
        for (int i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
 
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 4;
        System.out.println("Number of Dyck Paths is " +
                                    countDyckPaths(n));
    }
}

                    

Python3

# Python3 program to count
# number of Dyck Paths
 
# Returns count Dyck
# paths in n x n grid
def countDyckPaths(n):
     
    # Compute value of 2nCn
    res = 1
    for i in range(0, n):
        res *= (2 * n - i)
        res /= (i + 1)
 
    # return 2nCn/(n+1)
    return res / (n+1)
 
# Driver Code
n = 4
print("Number of Dyck Paths is ",
    str(int(countDyckPaths(n))))
 
# This code is contributed by
# Prasad Kshirsagar

                    

Javascript

<script>
 
// JavaScript program to count
// number of Dyck Paths
 
    // Returns count Dyck
    // paths in n x n grid
    function countDyckPaths(n)
    {
     
        // Compute value of 2nCn
        let res = 1;
        for (let i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
   
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
// Driver Code
 
        let n = 4;
        document.write("Number of Dyck Paths is " +
                                    countDyckPaths(n));
     
    // This code is contributed by target_2.
</script>

                    

C#

// C# program to count
// number of Dyck Paths
using System;
 
class GFG {
     
    // Returns count Dyck
    // paths in n x n grid
    static int countDyckPaths(int n)
    {
         
        // Compute value of 2nCn
        int res = 1;
        for (int i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
 
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
    // Driver code
    public static void Main()
    {
        int n = 4;
        Console.WriteLine("Number of "
                  + "Dyck Paths is " +
                   countDyckPaths(n));
    }
}
 
// This code is contributed by anuj_67.

                    

PHP

<?php
// PHP program to count
// number of Dyck Paths
 
// Returns count Dyck
// paths in n x n grid
function countDyckPaths( $n)
{
    // Compute value of 2nCn
    $res = 1;
    for ( $i = 0; $i < $n; ++$i)
    {
        $res *= (2 * $n - $i);
        $res /= ($i + 1);
    }
 
    // return 2nCn/(n+1)
    return $res / ($n + 1);
}
 
// Driver Code
$n = 4;
echo "Number of Dyck Paths is " ,
              countDyckPaths($n);
 
// This code is contributed by anuj_67.
?>

                    

Output
Number of Dyck Paths is 14

Time complexity: O(n).
Auxiliary space: O(1).

Exercise :  

  1. Find number of sequences of 1 and -1 such that every sequence follows below constraints : 
    a) The length of a sequence is 2n 
    b) There are equal number of 1’s and -1’s, i.e., n 1’s, n -1s 
    c) Sum of prefix of every sequence is greater than or equal to 0. For example, 1, -1, 1, -1 and 1, 1, -1, -1 are valid, but -1, -1, 1, 1 is not valid.
  2. Number of paths of length m + n from (m-1, 0) to (0, n-1) that are restricted to east and north steps.

Approach 2:-approach to count the number of Dyck paths –In this implementation, we generate all possible Dyck paths of length n by generating all binary numbers with n bits. We then traverse through each bit in the binary representation of the number and update the depth accordingly. If at any point the depth becomes negative, then the path is not a Dyck path, so we break out of the loop. If we reach the end of the path and the depth is zero, then the path is a Dyck path, so we increment the count. Finally, we return the count of Dyck paths.

C++

#include <iostream>
 
using namespace std;
 
// Function to calculate the factorial of a given number
int factorial(int n) {
    int fact = 1;
    for (int i = 1; i <= n; i++) {
        fact *= i;
    }
    return fact;
}
 
// Function to calculate the number of Dyck paths of length n using the 2 approach
int dyck_paths_2(int n) {
    int numerator = factorial(2 * n);
    int denominator = factorial(n + 1) * factorial(n);
    return numerator / denominator;
}
 
int main() {
    int n = 4;
 
    cout << "Number of Dyck paths is " << n << ": " << dyck_paths_2(n) << endl;
 
    return 0;
}

                    

Java

import java.util.*;
 
public class DyckPaths
{
 
  // Function to calculate the factorial of a given number
  public static int factorial(int n)
  {
    int fact = 1;
    for (int i = 1; i <= n; i++) {
      fact *= i;
    }
    return fact;
  }
 
  // Function to calculate the number of Dyck paths of
  // length n using the 2 approach
  public static int dyck_paths_2(int n)
  {
    int numerator = factorial(2 * n);
    int denominator = factorial(n + 1) * factorial(n);
    return numerator / denominator;
  }
 
  public static void main(String[] args)
  {
    int n = 4;
 
    System.out.println("Number of Dyck paths is " + n
                       + ": " + dyck_paths_2(n));
  }
}
 
// This code is contributed by Prajwal Kandekar

                    

Python3

# Function to calculate the factorial of a given number
def factorial(n):
    fact = 1
    for i in range(1, n + 1):
        fact *= i
    return fact
 
# Function to calculate the number of Dyck paths of length n using the 2 approach
def dyck_paths_2(n):
    numerator = factorial(2 * n)
    denominator = factorial(n + 1) * factorial(n)
    return numerator // denominator
 
if __name__ == '__main__':
    n = 4
    print("Number of Dyck paths is {}: {}".format(n, dyck_paths_2(n)))

                    

Javascript

function factorial(n) {
  let fact = 1;
  for (let i = 1; i <= n; i++) {
    fact *= i;
  }
  return fact;
}
 
function dyckPaths2(n) {
  const numerator = factorial(2 * n);
  const denominator = factorial(n + 1) * factorial(n);
  return numerator / denominator;
}
 
const n = 4;
console.log(`Number of Dyck paths is ${n}: ${dyckPaths2(n)}`);

                    

C#

using System;
 
class Program {
    // Function to calculate the factorial of a given number
    static int Factorial(int n)
    {
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }
 
    // Function to calculate the number of Dyck paths of
    // length n using the 2 approach
    static int DyckPaths2(int n)
    {
        int numerator = Factorial(2 * n);
        int denominator = Factorial(n + 1) * Factorial(n);
        return numerator / denominator;
    }
 
    static void Main(string[] args)
    {
        int n = 4;
 
        Console.WriteLine("Number of Dyck paths is " + n
                          + ": " + DyckPaths2(n));
    }
}

                    

Output
Number of Dyck paths is 4: 14

Time complexity: O(n).
Auxiliary space: O(1).


 



Previous Article
Next Article

Similar Reads

Dyck Words of given length
Given an integer n, the task is to count Dyck words possible of length n. A DYCK word is a word containing only characters 'X' and 'Y' such that in every prefix of the word frequency('X') ? frequency('Y')Examples: Input: n = 2 Output: 2 "XY" and "XX" are the only possible DYCK words of length 2.Input: n = 5 Output: 42 Approach: Geometrical Interpre
5 min read
Construct a Tree whose sum of nodes of all the root to leaf path is not divisible by the count of nodes in that path
Given an N-ary tree consisting of N nodes numbered from 1 to N rooted at node 1, the task is to assign values to each node of the tree such that the sum of values from any root to the leaf path which contains at least two nodes is not divisible by the number of nodes along that path. Examples: Input: N = 11, edges[][] = {{1, 2}, {1, 3}, {1, 4}, {1,
11 min read
Find the path from root to a vertex such that all K vertices belongs to this path or 1 distance away
Given a tree consisting of N vertices numbered from 1 to N rooted at vertex 1. You are given Q queries. Each query consists of the set of K distinct vertices vi[1], vi[2],…, vi[K]. The task is to determine if there is a path from the root to some vertex X such that each of the given K vertices either belongs to this path or has the distance 1 to so
10 min read
Shortest path from source to destination such that edge weights along path are alternatively increasing and decreasing
Given a connected graph with N vertices and M edges. The task is to find the shortest path from source to the destination vertex such that the difference between adjacent edge weights in the shortest path change from positive to negative and vice versa ( Weight(E1) > Weight(E2) < Weight(E3) .... ). If no such path exists then print -1. Exampl
13 min read
Minimum cost such that path sum is at max K (Target Path Sum)
Given a rooted tree consisting of N vertices. The vertices are numbered from 0 to N-1, and the root is the vertex 0. You are also given a value array Arr: Arr0, Arr1,....., Arrn-1. You can do any of these moves any number of times: Pick any node that is not root cut the edge between it and its parent and connect an edge between this node to the roo
11 min read
Difference Between Hamiltonian Path and Eulerian Path
The Hamiltonian and Eulerian paths are two significant concepts used to the solve various problems related to the traversal and connectivity of the graphs. Understanding the differences between these two types of the paths is crucial for the designing efficient algorithms and solving the complex graph problems. What is a Hamiltonian Path?Hamiltonia
2 min read
Path with smallest difference between consecutive cells (Path with minimum effort)
Given a 2D array arr[] of size N x M, where arr[i][j] represents the value of cell (i, j). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (n-1, m-1). You can move up, down, left, or right, and you wish to find a path such that the maximum absolute difference in values between two consecutive cells of
14 min read
Find if there is a path between two vertices in a directed graph
Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Example: Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -> 2 -> 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 Approach: Either Bread
15 min read
Union By Rank and Path Compression in Union-Find Algorithm
In the previous post, we introduced union find algorithm and used it to detect cycles in a graph. We used the following union() and find() operations for subsets. C/C++ Code // Naive implementation of find int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // Naive implementation of union() void Union(i
15+ min read
Fleury's Algorithm for printing Eulerian Path or Circuit
Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex. We strongly recommend first reading the following post on Euler Path and Circuit. "https://www.cdn.geeksforgeeks.org/eulerian-path-and-circuit/" In the above-mentioned post, we discussed the problem o
15+ min read
Some interesting shortest path questions | Set 1
Question 1: Given a directed weighted graph. You are also given the shortest path from a source vertex 's' to a destination vertex 't'. If weight of every edge is increased by 10 units, does the shortest path remain same in the modified graph? The shortest path may change. The reason is, there may be different number of edges in different paths fro
3 min read
Shortest path with exactly k edges in a directed and weighted graph
Given a directed and two vertices ‘u’ and ‘v’ in it, find shortest path from ‘u’ to ‘v’ with exactly k edges on the path. The graph is given as adjacency matrix representation where value of graph[i][j] indicates the weight of an edge from vertex i to vertex j and a value INF(infinite) indicates no edge from i to j. For example, consider the follow
15+ min read
Find length of the longest consecutive path from a given starting character
Given a matrix of characters. Find length of the longest path from a given character, such that all characters in the path are consecutive to each other, i.e., every character in path is next to previous in alphabetical order. It is allowed to move in all 8 directions from a cell. Example: Input: mat[][] = { {a, c, d}, {h, b, e}, {i, g, f}} Startin
15 min read
Check if a path exists in a tree with K vertices present or are at most at a distance D
Given a tree with N vertices numbered [0, n - 1], K vertices, and a distance D, the task is to find whether there is a path from the root to some vertex such that each of the K vertices belongs to the path or are at most at a distance D from the path. Examples: Input: 0 / \ / \ 1 2 / \ / \ / \ / \ 3 4 5 8 / \ / \ 6 7 / / 9 K = {6, 7, 8, 5}, D = 1 O
12 min read
Counts Path in an Array
Given an array A consisting of positive integer, of size N. If the element in the array at index i is K then you can jump between index ranges (i + 1) to (i + K). The task is to find the number of possible ways to reach the end with module 109 + 7.The starting position is considered as index 0.Examples: Input: A = {5, 3, 1, 4, 3} Output: 6Input: A
8 min read
Union-Find Algorithm | (Union By Rank and Find by Optimized Path Compression)
Check whether a given graph contains a cycle or not. Example: Input: Output: Graph contains Cycle. Input: Output: Graph does not contain Cycle. Prerequisites: Disjoint Set (Or Union-Find), Union By Rank and Path CompressionWe have already discussed union-find to detect cycle. Here we discuss find by path compression, where it is slightly modified t
13 min read
Check for possible path in 2D matrix
Given a 2D array(m x n). The task is to check if there is any path from top left to bottom right. In the matrix, -1 is considered as blockage (can't go through this cell) and 0 is considered path cell (can go through it). Note: Top left cell always contains 0 Examples: Input : arr[][] = {{ 0, 0, 0, -1, 0}, {-1, 0, 0, -1, -1}, { 0, 0, 0, -1, 0}, {-1
15+ min read
Reverse a path in BST using queue
Given a binary search tree and a key, your task to reverse path of the binary tree. Prerequisite : Reverse path of Binary tree Examples : Input : 50 / \ 30 70 / \ / \ 20 40 60 80 k = 70 Output : Inorder before reversal : 20 30 40 50 60 70 80 Inorder after reversal : 20 30 40 70 60 50 80 Input : 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 k = 13 Output : I
12 min read
Path length having maximum number of bends
Given a binary tree, find the path length having maximum number of bends. Note: Here, bend indicates switching from left to right or vice versa while traversing in the tree. For example, consider below paths (L means moving leftwards, R means moving rightwards): LLRRRR - 1 Bend RLLLRR - 2 Bends LRLRLR - 5 BendsPrerequisite : Finding Max path length
11 min read
Longest Path with Same Values in a Binary Tree
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. The length of path between two nodes is represented by the number of edges between them. Examples: Input : 2 / \ 7 2 / \ \ 1 1 2 Output : 2 Input : 4 / \ 4 4 / \ \ 4 9 5 Output : 3 The idea is to r
9 min read
Probabilistic shortest path routing algorithm for optical networks
Data transfer operations is a crucial aspect in case of networking and routing. So efficient data transfer operations is a must need, with minimum hardware cost (Optical Cables, WDM Network components, Decoders, Multiplexers) and also in the minimum time possible. Thus, the need is to propose an algorithm that finds the shortest path between two no
5 min read
Reverse tree path
Given a tree and node data, the task to reverse the path to that particular Node. Examples: Input: 7 / \ 6 5 / \ / \ 4 3 2 1 Data = 4 Output: Inorder of tree 7 6 3 4 2 5 1 Input: 7 / \ 6 5 / \ / \ 4 3 2 1 Data = 2 Output : Inorder of tree 4 6 3 2 7 5 1 The idea is to use a map to store path level wise. Find the Node path as well as store it in the
15+ min read
Sort the path from root to a given node in a Binary Tree
Given a Binary tree, the task is to sort the particular path from to a given node of the binary tree. You are given a Key Node and Tree. The task is to sort the path till that particular node. Examples: Input : 3 / \ 4 5 / \ \ 1 2 6 key = 2 Output : 2 / \ 3 5 / \ \ 1 4 6 Inorder :- 1 3 4 2 5 6 Here the path from root to given key is sorted from 3(r
6 min read
Find if there is a path between two vertices in a directed graph | Set 2
Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Example: Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -> 2 -> 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 A BFS or DFS based sol
7 min read
Maximum cost path in an Undirected Graph such that no edge is visited twice in a row
Given an undirected graph having N vertices and M edges and each vertex is associated with a cost and a source vertex S is given. The task is to find the maximum cost path from source vertex S such that no edge is visited consecutively 2 or more times. Examples: Input: N = 5, M = 5, source = 1, cost[] = {2, 2, 8, 6, 9}, Below is the given graph: Ou
12 min read
Minimum cost path from source node to destination node via an intermediate node
Given an undirected weighted graph. The task is to find the minimum cost of the path from source node to the destination node via an intermediate node. Note: If an edge is traveled twice, only once weight is calculated as cost. Examples: Input: source = 0, destination = 2, intermediate = 3; Output: 6 The minimum cost path 0->1->3->1->2
12 min read
Root to leaf path sum equal to a given number in BST
Given a BST and a number. The task is to check whether the given number is equal to the sum of all the node from root leaf across any of the root to leaf paths in the given Binary Search Tree. Approach: The idea is to traverse from root to all leaves in top-down fashion maintaining a path[] array to store current root to leaf path. While traversing
8 min read
Minimum length of the shortest path of a triangle
Given N points on the plane, ( X1, Y1 ), ( X2, Y2 ), ( X3, Y3 ), ......, ( XN, YN ). The task is to calculate the minimum length of the shorter side of the triangle. and the path or points to place an isosceles triangle with any two sides of the triangle on the coordinate axis ( X axis and Y axis ) to cover all points.Note: A point is covered if it
7 min read
Lexicographically largest prime path from top-left to bottom-right in a matrix
Given a m x n matrix of positive integers. The task is to find the number of paths from the top left of the matrix to the bottom right of the matrix such that each integer in the path is prime. Also, print the lexicographical largest path among all the path. A cell (a, b) is lexicographical larger than cell (c, d) either a > b or if a == b then
15+ min read
Minimum sum falling path in a NxN grid
Given a square array A of integers of size NxN. The task is to find the minimum sum of a falling path through A.A falling path will start at any element in the first row and ends in last row. It chooses one element from each next row. The next row's choice must be in a column that is different from the previous row's column by at most one. Examples
15+ min read
Article Tags :
Practice Tags :
three90RightbarBannerImg