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 kth 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:
Output: 1 3 3 1
Output: 1 4 6 4 1
Output: 1 2 1
Here, we are going to see two methods for this algorithm:
- Recursion Method
- Using the
nCkformula 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]
prev_row = [1, 2, 1]
curr_row --------- initially storing 1
for loop from
1 to len(prev_row)
curr_row = prev_row[1 - 1] + prev_row = [1, 3]
curr_row = prev_row[2 - 1] + prev_row = [1, 3, 3]
curr_row = [1, 3, 3, 1]--------------manually appending 1 at end of for loop
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
kth 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 3 3 1
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 nCk 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
nCk or even
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.
prev_value is initialized to
1 as every row has its first value as
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
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.