Pascal's Triangle Editorial

Practice Problem Link: Pascal's Triangle | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a number n, find the nth row of pascal’s triangle.

Naive Approach

The naive approach for this problem is to use recursion. We find the row of the previous index using recursion and using the previous row’s values, calculate the values in the current row. Repeat till we have calculated the value of the n^th row.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Implementation

C++

vector<int> getNthRow(int rowNo) {
   vector<int> currentRow, prevRow;
   currentRow.push_back(1);
   if (rowNo == 0) {
       return currentRow;
   }
   prevRow = getNthRow(rowNo - 1);
   for (int i = 1; i < prevRow.size(); i++) {
       currentRow.push_back(prevRow[i - 1] + prevRow[i]);
   }
   currentRow.push_back(1);
   return currentRow;
}
vector<int> pascalTriangleRow(int rowNo) {
   vector<int> pascalRow;
   pascalRow = getNthRow(rowNo - 1);
   return pascalRow;
}

Java

class Solution {
   int[] getNthRow(int rowNo){
       int[] currentRow = new int[rowNo + 1];
       int[] prevRow = new int[rowNo + 1];
       currentRow[0] = 1;
       if (rowNo == 0) {
           return currentRow;
       }
       prevRow = getNthRow(rowNo - 1);
       int i = 0;
       for (i = 1; i < rowNo; i++) {
           currentRow[i] = (prevRow[i - 1] + prevRow[i]);
       }
       currentRow[i] = 1;
       return currentRow;
   }
   int[] pascalTriangleRow(int rowNo) {
       int pascalRow[] = new int[rowNo + 1];
       pascalRow = getNthRow(rowNo - 1);
       int pascalNthRow[] = new int[rowNo];
       for (int i = 0; i < rowNo; i++) {
           pascalNthRow[i] = pascalRow[i];
       }
       return pascalNthRow;
   }
}

Optimal Approach

Here, we will directly calculate the n^th row of pascal’s triangle. The key thing to know here is that the terms in the n^th row of the pascal’s triangle are the n^th binomial coefficients, from Nc0 to NcN.

We can use the following recurrence to calculate the values of the binomial coefficients efficiently, ^Nc_R = ^Nc_{(R - 1)} * (N - R + 1) / R;

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

vector<int> pascalTriangleRow(int rowNo) {
   vector<int> pascalRow;
   pascalRow.push_back(1);
   rowNo--;
   for (int i = 1; i <= rowNo; i++) {
       int rowElement = pascalRow.back() * (rowNo - i + 1) / i;
       pascalRow.push_back(rowElement);
   }
   return pascalRow;
}

Java

class Solution {
   int[] pascalTriangleRow(int rowNo) {
       int pascalRow[] = new int[rowNo];
       pascalRow[0] = 1;
       rowNo--;
       for (int i = 1; i <= rowNo; i++) {
           int rowElement = pascalRow[i - 1] * (rowNo - i + 1) / i;
           pascalRow[i] = rowElement;
       }
       return pascalRow;
   }
}