Pascal’s Triangle II In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Pascal’s Triangle II

Given an integer rowIndex, return the rowIndex-th row of Pascal’s Triangle. The rowIndex is 0-based, so the first row is row 0.

For example:

• Input: rowIndex = 3
• Output: [1, 3, 3, 1]

Approach

1. Understanding Pascal’s Triangle:
   • Each row is constructed using the previous row, where:
     • The first and last elements are always 1.
     • Any middle element triangle[r][c] is the sum of the two elements above it: triangle[r-1][c-1] + triangle[r-1][c].
2. Efficient Calculation:
   • Optimal Solution: Rather than generating the entire triangle up to rowIndex, we can directly compute the required row using a simple iterative approach:
     • We start with a row initialized to [1].
     • We iteratively update this row using the properties of Pascal’s Triangle, keeping only the current row at each step.
3. Mathematical Insight:
   • The elements of the row can be computed using the formula: C(r,c)=r!c!(r−c)!\text{C}(r, c) = \frac{r!}{c! (r – c)!}C(r,c)=c!(r−c)!r!​ However, instead of calculating the factorials directly, we can compute each element iteratively using: C(r,c)=C(r,c−1)×r−c+1c\text{C}(r, c) = \text{C}(r, c – 1) \times \frac{r – c + 1}{c}C(r,c)=C(r,c−1)×cr−c+1​ This avoids the computational overhead of calculating factorials.
4. Time Complexity:
   • O(n) where n is the rowIndex because we only iterate once to generate the required row.
5. Space Complexity:
   • O(n) because we store only the current row.

---

Code Implementations

---

C:

#include <stdio.h>
#include <stdlib.h>

void generateRow(int rowIndex) {
    int *row = (int *)malloc((rowIndex + 1) * sizeof(int));
    
    row[0] = 1;  // First element is always 1

    for (int i = 1; i <= rowIndex; i++) {
        // Update the row in reverse to avoid overwriting previous values
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }

    // Print the row
    for (int i = 0; i <= rowIndex; i++) {
        printf("%d ", row[i]);
    }
    printf("\n");

    free(row);
}

int main() {
    int rowIndex = 3;
    generateRow(rowIndex);  // Output: 1 3 3 1
    return 0;
}

---

C++:

#include <iostream>
#include <vector>
using namespace std;

vector<int> getRow(int rowIndex) {
    vector<int> row(rowIndex + 1, 1);  // Initialize the row with 1's
    
    for (int i = 1; i <= rowIndex; i++) {
        // Update the row in reverse order to prevent overwriting
        for (int j = i - 1; j > 0; j--) {
            row[j] += row[j - 1];
        }
    }

    return row;
}

int main() {
    int rowIndex = 3;
    vector<int> row = getRow(rowIndex);
    
    for (int num : row) {
        cout << num << " ";
    }
    cout << endl;  // Output: 1 3 3 1
    return 0;
}

---

Java:

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

public class PascalsTriangleII {
    public static List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1);  // First element is always 1

        for (int i = 1; i <= rowIndex; i++) {
            // Update the row in reverse order to avoid overwriting
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
            row.add(1);  // Add the last element of the row (which is always 1)
        }

        return row;
    }

    public static void main(String[] args) {
        int rowIndex = 3;
        List<Integer> row = getRow(rowIndex);
        
        for (int num : row) {
            System.out.print(num + " ");
        }
        System.out.println();  // Output: 1 3 3 1
    }
}

---

Python:

def getRow(rowIndex):
    row = [1]  # First element is always 1

    for i in range(1, rowIndex + 1):
        # Update the row in reverse order to avoid overwriting
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]
        row.append(1)  # Add the last element of the row (which is always 1)

    return row

# Example usage
rowIndex = 3
print(getRow(rowIndex))  # Output: [1, 3, 3, 1]

---

C#:

using System;
using System.Collections.Generic;

class PascalsTriangleII {
    public static List<int> GetRow(int rowIndex) {
        var row = new List<int> { 1 };  // First element is always 1

        for (int i = 1; i <= rowIndex; i++) {
            // Update the row in reverse order to prevent overwriting
            for (int j = i - 1; j > 0; j--) {
                row[j] += row[j - 1];
            }
            row.Add(1);  // Add the last element of the row (which is always 1)
        }

        return row;
    }

    static void Main() {
        int rowIndex = 3;
        var row = GetRow(rowIndex);
        
        foreach (var num in row) {
            Console.Write(num + " ");
        }
        Console.WriteLine();  // Output: 1 3 3 1
    }
}

---

JavaScript:

function getRow(rowIndex) {
    let row = [1];  // First element is always 1

    for (let i = 1; i <= rowIndex; i++) {
        // Update the row in reverse order to avoid overwriting
        for (let j = i - 1; j > 0; j--) {
            row[j] += row[j - 1];
        }
        row.push(1);  // Add the last element of the row (which is always 1)
    }

    return row;
}

// Example usage
let rowIndex = 3;
console.log(getRow(rowIndex));  // Output: [1, 3, 3, 1]

---

Explanation:

For rowIndex = 3, the steps to generate the row [1, 3, 3, 1] are:

1. Start with an initial row: [1].
2. For i = 1, update the row: [1, 1] (last element is 1).
3. For i = 2, update the row: [1, 2, 1].
4. For i = 3, update the row: [1, 3, 3, 1].

Time Complexity:

• O(n), where n is the row index (rowIndex), because we only need to loop through n iterations to compute the required row.

Space Complexity:

• O(n), where n is the row index, because we only store the current row.

---

Summary:

This solution computes the rowIndex-th row of Pascal’s Triangle directly using an efficient iterative approach, making it more space- and time-efficient than generating the entire triangle.