Pascal's Triangle

You are given an integer n, your task is to generate the first n rows of Pascal's Triangle and return it as a list of lists.
Pascal's triangle is a triangular array of numbers where each number is the sum of the two numbers above it. The first few rows of Pascal's triangle are:
1
1 1
1 2 1
1 3 3 1

Example:

Input: n = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Algorithm:

1. Initialize an empty list of lists ans to store the rows of Pascal's Triangle.
2. Create two lists ls and prev. prev will be used to store the previous row of Pascal's Triangle, and ls will be used to generate the current row.
3. Iterate from i equals 0 to n - 1 to generate each row of Pascal's Triangle:
   • Create a new empty list ls to represent the current row.
   • Iterate from j equals 0 to i to generate the elements of the current row:
     • If j is 0 or j is equal to i, add 1 to the ls list because the first and last elements of each row are always 1.
     • Otherwise, add the sum of the corresponding elements from the previous row (prev) to the ls list.
   • Set prev to ls to prepare for the next iteration.
   • Add the ls list (representing the current row) to the ans list.
4. Return the ans list containing all the rows of Pascal's Triangle up to n.

Code Implementation:

• JAVA

import java.util.ArrayList;

import java.util.List;

public class PascalTriangle {

public static List<List<Integer>> generate(int n) {

List<List<Integer>> ans = new ArrayList<>();

List<Integer> ls, prev = new ArrayList<>();

for (int i = 0; i < n; i++) {

ls = new ArrayList<>();

for (int j = 0; j <= i; j++) {

if (j == 0 || j == i) {

ls.add(1);

} else {

ls.add(prev.get(j - 1) + prev.get(j));

}

}

prev = ls;

ans.add(ls);

}

return ans;

}

// driver method

public static void main(String[] args) {

int n = 5;

System.out.println(generate(n));

}

}

Output:

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Complexity Analysis:

Time Complexity: O(n²), where n is the number of rows.

Space Complexity: O(n²)

---

If you want to contribute such articles to solutions2coding.com please click here. Thank you!