Print the kth row of a Pascal Triangle

Print the kth row of a Pascal Triangle

Pascal Triangle is an arrangement of numbers in rows resembling a triangle. Here, our task is to print the k^th row for which the integer k is provided. 

Remember that in a Pascal Triangle the indexing of rows starts from 0. Let's see how the output should look like:

Here, we are going to see two methods for this algorithm:

1. Recursion Method
   
2. Using the nCk formula but in a modified way(Time Complexity: O(n) and Auxiliary Space: O(1))
   

It is recommended to have a page and pen ready to understand the working of the algorithm.

Approach 1: Recursion Method

Pascal Triangle has a property that elements of a current row can be found with the help of the elements of the previous row. The value at each position of the Pascal Triangle is the direct sum of the above two values. Still didn't get it? Look at the image below:

The formula to find the value of the current row from the previous row is:

curr_row = prev_row[i - 1] + prev_row[I]

Example:

Now, we can use this property to find elements of any row, If we are given the value of k that is the row number, we will find the elements of its previous row that (k-1)^th row using the recursion method. Once we get the values of the previous row, we can use the above property and find the values of the k^th row. Let's see how we can achieve this using recursion. It is suggested to learn how recursion works before moving ahead here.

Suppose k = 3, values of row 3 are to be printed(remember that row number starts from 0). Recursion will happen k number of times. Let's see how: 

We will stop the recursion when we reach the value of k == 0. Now, at each stage, we will return the value of each row calculated with the formula discussed above. For your understanding the pictorial representation will look like this:

Now let's see the actual implementation of the Recursion approach in Python:

def find_row(k):
    my_row = []

    my_row.append(1)      # since every row has its first value as 1

    if k == 0:
        return my_row

    prev_row = find_row(k - 1)       # recursively calling the previous row

    for i in range(1, len(prev_row)):

        curr_row = prev_row[i - 1] + prev_row[i]      # formula to calculate the value of current row from previous row
        my_row.append(curr_row)

    my_row.append(1)            # since every row has its last value as 1

    return my_row


k = 6
arr = find_row(k)

for i in arr:
    print(i, end="  ")<br/>

1. We can see in the above code, the function find_row() is recursively called until k == 0 which is our base condition to stop the recursion.

2. We are storing the list in the array my_row[] and every time we need to do my_row.append(1) since the first and the last value of each row is 1.

3. Note that after every recursion step, we are storing the array in prev_row for calculating the values in the further steps.

Approach 2: Using ⁿC_k formula in a modified way (Time Complexity: O(n) and Auxiliary Space: O(1))

We should know in a Pascal Triangle, every single element of each row is calculated by a formula of Combinations which is commonly known as "n choose k" or the number of combinations of k elements from n elements. The formula is:

Note: "n choose k" can also be written C(n,k), nCk or even nCk. 

The value at each position of Pascal Triangle using the nCk formula is shown below where

n = current row number

k = current column number 

We can use this formula in our algorithm and find the values of the given row. But calculating nCk each time increases the time complexity. Also, n! may overflow for larger values of n. So, we can modify the nCk formula and come up with an efficient solution. Let's see how:

For a detailed explanation of this formula please click here.

So basically for this approach, we are going to generate the values only for the particular row and not for the previous rows as we did in the earlier approach. Let's see how to achieve it:

def find_row(n):

	prev_val = 1            # first value is always 1
	print(prev_val, end = '  ')

	for k in range(1, n + 1):

		curr_val = (prev_val * (n - k + 1)) // k     # using the formula nCk = (nCk-1 * (n - k + 1))/k
		print(curr_val, end='  ')
		prev_val = curr_val

# Driver code
n = 0
find_row(n)

So, we have a function find_row() to generate the values of the given row.

1. prev_value is initialized to 1 as every row has its first value as 1. 

2. Note that the prev_value will always store the preceding value of the same row which will be helpful to calculate the current value. That is prev_value stores C(n, k-1)

3. We will use the for loop to generate each value of the row. So it ranges from 1 to n+1.

4. In the for loop, we use the formula discussed above to generate the values. 

For better understanding, first, use the original nCk formula and try to get the values, and then go for the modified formula.