Pascal Triangle Solution

In this page, we will solve the Pascal Triangle Row problem using different approaches: dynamic programming and mathematical. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

Given a positive integer N, return the Nth row of Pascal's triangle. Pascal's triangle is a triangular array of the binomial coefficients formed by summing up the elements of the previous row. The elements can be large so return it modulo $(10^9 + 7)$.

Examples

Example 1:

Input: N = 4
Output: 1 3 3 1
Explanation: 4th row of Pascal's triangle is 1 3 3 1.

Example 2:

Input: N = 5
Output: 1 4 6 4 1
Explanation: 5th row of Pascal's triangle is 1 4 6 4 1.

Constraints

• 1 <= N <= 10^3

---

Solution for Pascal Triangle Row Problem

Intuition and Approach

The problem can be solved using dynamic programming or a mathematical approach. The dynamic programming approach is more intuitive and builds the entire triangle row by row. The mathematical approach leverages the properties of binomial coefficients.

• Dynamic Programming
• Mathematical

Approach 1: Dynamic Programming

The dynamic programming approach involves building the Pascal's triangle row by row until the desired row is reached.

Implementation

Live Editor

function nthRowOfPascalTriangle() {
  const N = 4;
  const MOD = 1000000007;

  const generate = function(N) {
    const row = [1];
    for (let i = 1; i < N; i++) {
      row[i] = (row[i - 1] * (N - i) / i) % MOD;
    }
    return row;
  };

  const result = generate(N);
  return (
    <div>
      <p>
        <b>Input:</b> N = {N}
      </p>
      <p>
        <b>Output:</b> {JSON.stringify(result)}
      </p>
    </div>
  );
}

Result

Loading...

Codes in Different Languages

JavaScript

Written by @manishh12

 function nthRowOfPascalTriangle(N) {
   const MOD = 1000000007;
   const row = [1];
   for (let i = 1; i < N; i++) {
     row[i] = (row[i - 1] * (N - i) / i) % MOD;
   }
   return row;
 }

TypeScript

Written by @manishh12

 function nthRowOfPascalTriangle(N: number): number[] {
   const MOD = 1000000007;
   const row: number[] = [1];
   for (let i = 1; i < N; i++) {
     row[i] = (row[i - 1] * (N - i) / i) % MOD;
   }
   return row;
 }

Python

Written by @manishh12

 class Solution:
     def nthRowOfPascalTriangle(self, N: int) -> List[int]:
         MOD = 1000000007
         row = [1]
         for i in range(1, N):
             row.append((row[-1] * (N - i) // i) % MOD)
         return row

Java

Written by @manishh12

 import java.util.ArrayList;
 import java.util.List;

 class Solution {
     public List<Integer> nthRowOfPascalTriangle(int N) {
         final int MOD = 1000000007;
         List<Integer> row = new ArrayList<>();
         row.add(1);
         for (int i = 1; i < N; i++) {
             row.add((int)((long)row.get(i - 1) * (N - i) / i % MOD));
         }
         return row;
     }
 }

C++

Written by @manishh12

 #include <vector>

 using namespace std;

 class Solution {
 public:
     vector<int> nthRowOfPascalTriangle(int N) {
         const int MOD = 1000000007;
         vector<int> row(1, 1);
         for (int i = 1; i < N; i++) {
             row.push_back((long long)row[i - 1] * (N - i) / i % MOD);
         }
         return row;
     }
 };

Complexity Analysis

• Time Complexity: $O(N^2)$
• Space Complexity: $O(N)$

---

These are the two approaches to solve the Pascal's Triangle Row problem. Each approach has its own advantages and trade-offs in terms of time and space complexity. You can choose the one that best fits your requirements.

References

• GeeksforGeeks Problem: GeeksforGeeks Problem
• Solution Link: Pascal's Triangle Solution on GeeksforGeeks
• Authors GeeksforGeeks Profile: Manish Kumar Gupta

---