Posted on by Kalkicode
Code Dynamic Programming

Catalan's triangle

The concept of Catalan's Triangle is an interesting area of combinatorics that offers insights into a variety of counting problems. This pattern generates a triangular array of numbers, where each entry represents a particular counting sequence or problem. In this article, we will explore the creation of Catalan's Triangle using a C program and provide a comprehensive explanation of its significance.

Problem Statement and Description

Catalan's Triangle is a triangular array of numbers that contains binomial coefficients and is widely applicable in various combinatorial problems. Each entry in the triangle is calculated based on a specific recurrence relation, making it an excellent tool for solving problems involving well-formed parentheses expressions, polygon triangulations, and more.

Example

Let's take a look at the initial rows of Catalan's Triangle:

  1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
...

Idea to Solve the Problem

To create Catalan's Triangle, we can utilize dynamic programming techniques. The idea is to construct the triangle row by row, where each entry is calculated using a recurrence relation involving previous row entries.

Standard Pseudocode

function catalansTriangle(n):
      create a 2D array dp of size 2 x (n+1)
      initialize dp[0][0] and dp[1][0] to 1
      
      initialize row as 1
      
      for i from 1 to n:
          initialize dp[0][i] and dp[1][i] to 0
          
          for j from 0 to i:
              calculate dp[row][j] based on recurrence relation
              
              print dp[row][j] followed by a space
          
          print a new line
          
          update row to 1 - row

Algorithm Explanation

  1. Initialize a 2D array dp of size 2 x (n+1) to store the entries of Catalan's Triangle.
  2. Set the initial values of dp[0][0] and dp[1][0] to 1, as the first column consists of all ones.
  3. Initialize the variable row to 1, which helps in alternating between two rows.
  4. Iterate through i from 1 to n, representing the row number.
    • Initialize dp[0][i] and dp[1][i] to 0 for the current row.
    • Iterate through j from 0 to i, representing the column number.
      • Calculate the value of dp[row][j] based on the recurrence relation, using previous row entries.
      • Print the value of dp[row][j] followed by a space.
    • Print a new line to move to the next row.
    • Update the row variable to toggle between 0 and 1.

Code Solution

// C Program for
// Catalan's triangle
#include <stdio.h>

void catalansTriangle(int n)
{
	if (n <= 0)
	{
		return;
	}
	// Optimize N *N space by using 2 rows
	int dp[2][n + 1];
	// Set initial value of first column
	dp[0][0] = 1;
	dp[1][0] = 1;
	// We can solve this problem only use two rows
	// So initial select second row which position is 1
	int row = 1;
	for (int i = 1; i <= n; ++i)
	{
		// Set initial value in current column
		dp[0][i] = 0;
		dp[1][i] = 0;
		for (int j = 0; j < i; ++j)
		{
			if (j > 0)
			{
				if (j + 1 == i)
				{
					// When last element
					dp[row][j] = dp[row][j - 1];
				}
				else if (row == 1)
				{
					// Change second row 'j' column value
					dp[row][j] = dp[0][j] + dp[row][j - 1];
				}
				else
				{
					// Change first row 'j' column value
					dp[row][j] = dp[1][j] + dp[row][j - 1];
				}
			}
			// Print element value
			printf("  %d", dp[row][j]);
		}
		// Include new line
		printf("\n");
		// Change the row
		if (row == 1)
		{
			row = 0;
		}
		else
		{
			row = 1;
		}
	}
}
int main()
{
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	catalansTriangle(9);
	return 0;
}

Output

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9  14  14
  1  5  14  28  42  42
  1  6  20  48  90  132  132
  1  7  27  75  165  297  429  429
  1  8  35  110  275  572  1001  1430  1430
// Java program for
// Catalan's triangle
public class Triangle
{
	public void catalansTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		int[][] dp = new int[2][n + 1];
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		int row = 1;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0][i] = 0;
			dp[1][i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				System.out.print(" " + dp[row][j]);
			}
			// Include new line
			System.out.print("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
	public static void main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		  1
		  1  1
		  1  2  2
		  1  3  5  5
		  1  4  9  14  14
		  1  5  14  28  42  42
		  1  6  20  48  90  132  132
		  1  7  27  75  165  297  429  429
		  1  8  35  110  275  572  1001  1430  1430
		  --------------------------------------------
		  Catalan's triangle when row = 9
		*/
		task.catalansTriangle(9);
	}
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Catalan's triangle
class Triangle
{
	public: void catalansTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		int dp[2][n + 1];
      
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
      
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		int row = 1;
      
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0][i] = 0;
			dp[1][i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				cout << " " << dp[row][j];
			}
			// Include new line
			cout << "\n";
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
};
int main()
{
	Triangle *task = new Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task->catalansTriangle(9);
	return 0;
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Include namespace system
using System;
// Csharp program for
// Catalan's triangle
public class Triangle
{
	public void catalansTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		int[,] dp = new int[2,n + 1];
		// Set initial value of first column
		dp[0,0] = 1;
		dp[1,0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		int row = 1;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0,i] = 0;
			dp[1,i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row,j] = dp[row,j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row,j] = dp[0,j] + dp[row,j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row,j] = dp[1,j] + dp[row,j - 1];
					}
				}
				// Print element value
				Console.Write(" " + dp[row,j]);
			}
			// Include new line
			Console.Write("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
	public static void Main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		  1
		  1  1
		  1  2  2
		  1  3  5  5
		  1  4  9  14  14
		  1  5  14  28  42  42
		  1  6  20  48  90  132  132
		  1  7  27  75  165  297  429  429
		  1  8  35  110  275  572  1001  1430  1430
		  --------------------------------------------
		  Catalan's triangle when row = 9
		*/
		task.catalansTriangle(9);
	}
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
package main
import "fmt"
// Go program for
// Catalan's triangle

func catalansTriangle(n int) {
	if n <= 0 {
		return
	}
	// Optimize N *N space by using 2 rows
	var dp = make([][] int, 2)
	for i:= 0; i < 2; i++{
		dp[i] = make([]int,n+1)
	}
	// Set initial value of first column
	dp[0][0] = 1
	dp[1][0] = 1
	// We can solve this problem only use two rows
	// So initial select second row which position is 1
	var row int = 1
	for i := 1 ; i <= n ; i++ {
		for j := 0 ; j < i ; j++ {
			if j > 0 {
				if j + 1 == i {
					// When last element
					dp[row][j] = dp[row][j - 1]
				} else if row == 1 {
					// Change second row 'j' column value
					dp[row][j] = dp[0][j] + dp[row][j - 1]
				} else {
					// Change first row 'j' column value
					dp[row][j] = dp[1][j] + dp[row][j - 1]
				}
			}
			// Print element value
			fmt.Print(" ", dp[row][j])
		}
		// Include new line
		fmt.Print("\n")
		// Change the row
		if row == 1 {
			row = 0
		} else {
			row = 1
		}
	}
}
func main() {

	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	catalansTriangle(9)
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
<?php
// Php program for
// Catalan's triangle
class Triangle
{
	public	function catalansTriangle($n)
	{
		if ($n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		$dp = array_fill(0, 2, array_fill(0, $n + 1, 0));
		// Set initial value of first column
		$dp[0][0] = 1;
		$dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		$row = 1;
		for ($i = 1; $i <= $n; ++$i)
		{
			for ($j = 0; $j < $i; ++$j)
			{
				if ($j > 0)
				{
					if ($j + 1 == $i)
					{
						// When last element
						$dp[$row][$j] = $dp[$row][$j - 1];
					}
					else if ($row == 1)
					{
						// Change second row 'j' column value
						$dp[$row][$j] = $dp[0][$j] + $dp[$row][$j - 1];
					}
					else
					{
						// Change first row 'j' column value
						$dp[$row][$j] = $dp[1][$j] + $dp[$row][$j - 1];
					}
				}
				// Print element value
				echo(" ".$dp[$row][$j]);
			}
			// Include new line
			echo("\n");
			// Change the row
			if ($row == 1)
			{
				$row = 0;
			}
			else
			{
				$row = 1;
			}
		}
	}
}

function main()
{
	$task = new Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	$task->catalansTriangle(9);
}
main();

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Node JS program for
// Catalan's triangle
class Triangle
{
	catalansTriangle(n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp = Array(2).fill(0).map(() => new Array(n + 1).fill(0));
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row = 1;
		for (var i = 1; i <= n; ++i)
		{
			for (var j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				process.stdout.write(" " + dp[row][j]);
			}
			// Include new line
			process.stdout.write("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
}

function main()
{
	var task = new Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task.catalansTriangle(9);
}
main();

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
#  Python 3 program for
#  Catalan's triangle
class Triangle :
	def catalansTriangle(self, n) :
		if (n <= 0) :
			return
		
		#  Optimize N *N space by using 2 rows
		dp = [[0] * (n + 1) for _ in range(2) ]
		#  Set initial value of first column
		dp[0][0] = 1
		dp[1][0] = 1
		#  We can solve this problem only use two rows
		#  So initial select second row which position is 1
		row = 1
		i = 1
		while (i <= n) :
			j = 0
			while (j < i) :
				if (j > 0) :
					if (j + 1 == i) :
						#  When last element
						dp[row][j] = dp[row][j - 1]
					elif (row == 1) :
						#  Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1]
					else :
						#  Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1]
					
				
				#  Print element value
				print(" ", dp[row][j], end = "")
				j += 1
			
			#  Include new line
			print(end = "\n")
			#  Change the row
			if (row == 1) :
				row = 0
			else :
				row = 1
			
			i += 1
		
	

def main() :
	task = Triangle()
	#  1
	#  1  1
	#  1  2  2
	#  1  3  5  5
	#  1  4  9  14  14
	#  1  5  14  28  42  42
	#  1  6  20  48  90  132  132
	#  1  7  27  75  165  297  429  429
	#  1  8  35  110  275  572  1001  1430  1430
	#  --------------------------------------------
	#  Catalan's triangle when row = 9
	task.catalansTriangle(9)

if __name__ == "__main__": main()

Output

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9  14  14
  1  5  14  28  42  42
  1  6  20  48  90  132  132
  1  7  27  75  165  297  429  429
  1  8  35  110  275  572  1001  1430  1430
#  Ruby program for
#  Catalan's triangle
class Triangle 
	def catalansTriangle(n) 
		if (n <= 0) 
			return
		end

		#  Optimize N *N space by using 2 rows
		dp = Array.new(2) {Array.new(n + 1) {0}}
		#  Set initial value of first column
		dp[0][0] = 1
		dp[1][0] = 1
		#  We can solve this problem only use two rows
		#  So initial select second row which position is 1
		row = 1
		i = 1
		while (i <= n) 
			j = 0
			while (j < i) 
				if (j > 0) 
					if (j + 1 == i) 
						#  When last element
						dp[row][j] = dp[row][j - 1]
					elsif (row == 1) 
						#  Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1]
					else
 
						#  Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1]
					end

				end

				#  Print element value
				print(" ", dp[row][j])
				j += 1
			end

			#  Include new line
			print("\n")
			#  Change the row
			if (row == 1) 
				row = 0
			else
 
				row = 1
			end

			i += 1
		end

	end

end

def main() 
	task = Triangle.new()
	#  1
	#  1  1
	#  1  2  2
	#  1  3  5  5
	#  1  4  9  14  14
	#  1  5  14  28  42  42
	#  1  6  20  48  90  132  132
	#  1  7  27  75  165  297  429  429
	#  1  8  35  110  275  572  1001  1430  1430
	#  --------------------------------------------
	#  Catalan's triangle when row = 9
	task.catalansTriangle(9)
end

main()

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Scala program for
// Catalan's triangle
class Triangle()
{
	def catalansTriangle(n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp: Array[Array[Int]] = Array.fill[Int](2, n + 1)(0);
		// Set initial value of first column
		dp(0)(0) = 1;
		dp(1)(0) = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row: Int = 1;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp(row)(j) = dp(row)(j - 1);
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp(row)(j) = dp(0)(j) + dp(row)(j - 1);
					}
					else
					{
						// Change first row 'j' column value
						dp(row)(j) = dp(1)(j) + dp(row)(j - 1);
					}
				}
				// Print element value
				print(" " + dp(row)(j));
				j += 1;
			}
			// Include new line
			print("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Triangle = new Triangle();
		/*
		  1
		  1  1
		  1  2  2
		  1  3  5  5
		  1  4  9  14  14
		  1  5  14  28  42  42
		  1  6  20  48  90  132  132
		  1  7  27  75  165  297  429  429
		  1  8  35  110  275  572  1001  1430  1430
		  --------------------------------------------
		  Catalan's triangle when row = 9
		*/
		task.catalansTriangle(9);
	}
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Swift 4 program for
// Catalan's triangle
class Triangle
{
	func catalansTriangle(_ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: n + 1), count: 2);
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row: Int = 1;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				print(" ", dp[row][j], terminator: "");
				j += 1;
			}
			// Include new line
			print(terminator: "\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
func main()
{
	let task: Triangle = Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task.catalansTriangle(9);
}
main();

Output

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9  14  14
  1  5  14  28  42  42
  1  6  20  48  90  132  132
  1  7  27  75  165  297  429  429
  1  8  35  110  275  572  1001  1430  1430
// Kotlin program for
// Catalan's triangle
class Triangle
{
	fun catalansTriangle(n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp: Array < Array < Int >> = Array(2)
		{
			Array(n + 1)
			{
				0
			}
		};
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row: Int = 1;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				print(" " + dp[row][j]);
				j += 1;
			}
			// Include new line
			print("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Triangle = Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task.catalansTriangle(9);
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430

Time Complexity:

The time complexity of the provided algorithm is O(n^2) due to the nested loops that iterate through the rows and columns of the triangle. The space complexity is O(n) since the program uses a 2D array of size 2 x (n+1) to store the triangle rows.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment