Pascal's Triangle - LeetCode

Intuition

The code generates Pascal's Triangle up to the specified number of rows (numRows). Each row is constructed based on the elements of the previous row, with the first and last elements always being 1.

Approach

1. Initialize a list of lists (ans) to store the generated triangle.

2. Generate the first two rows separately and add them to the result.

3. Use a nested loop to generate subsequent rows based on the sum of two elements from the previous row.

4. Add each row to the result (ans).

Complexity

• Time complexity: O(*numRows^*2), where numRows is the number of rows in the generated triangle. The nested loops iterate over each element in each row, and the number of rows is proportional to the square of numRows.

• Space complexity: O(*numRows^*2), as the space required for storing the triangle is proportional to the square of numRows.

class Solution {
    public List<List<Integer>> generate(int numRows) {
        // Initialize variables
        int counter = 0;
        List<List<Integer>> ans = new ArrayList<>();

        // Generate the first row
        List<Integer> innerList1 = new ArrayList<>();
        innerList1.add(1);
        ans.add(innerList1);

        // Check for special case: numRows <= 1
        if (numRows <= 1) {
            return ans;
        }

        // Generate the second row
        List<Integer> innerList2 = new ArrayList<>();
        innerList2.add(1);
        innerList2.add(1);
        ans.add(innerList2);

        // Generate subsequent rows
        for (int i = 3; i <= numRows; i++) {
            List<Integer> innerList3 = new ArrayList<>();

            // Populate the current row based on the previous row
            for (int j = 0; j < i; j++) {
                if (j == 0) {
                    innerList3.add(1);
                } else if (j == i - 1) {
                    innerList3.add(1);
                } else {
                    // Calculate the current element based on the sum of two elements in the previous row
                    int num2 = ans.get(i - 2).get(j - 1);
                    int num1 = ans.get(i - 2).get(j);
                    innerList3.add((num1 + num2));
                }
            }

            // Add the current row to the result
            ans.add(innerList3);
        }

        // Return the final result
        return ans;
    }
}