algoadvance

Leetcode 118. Pascal’s Triangle

Problem Statement

Given an integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Here is an example of the first 5 rows of Pascal’s triangle:

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

Clarifying Questions

1. What should be returned if numRows is zero?
   • An empty list [].
2. Is there a maximum constraint for numRows?
   • Typically, constraints will be reasonable for performance, but implementing in a scalable way for competitive programming is advantageous.
3. Are negative values for numRows considered valid input?
   • No. We can assume numRows will always be a non-negative integer.

Strategy

1. Initialize a list result to store the rows of Pascal’s triangle.
2. Append the first row [1] and iterate from the second row up to numRows.
3. For each row, create a new list that starts with 1.
4. Use the previous row to calculate the intermediate values and append them to the current row.
5. End the row with 1 and append it to the result.
6. Return the result list.

Time Complexity

• Constructing each row involves iterating over the elements of the previous row, leading to a time complexity for the n-th row as O(n).
• Summing the time complexities for all rows results in an overall time complexity of O(numRows^2).

Code

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

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (numRows == 0) {
            return result;
        }

        // First base row
        List<Integer> row = new ArrayList<>();
        row.add(1);
        result.add(new ArrayList<>(row));

        for (int i = 1; i < numRows; i++) {
            List<Integer> prevRow = result.get(result.size() - 1);
            row = new ArrayList<>();
            row.add(1); // first element

            // middle elements
            for (int j = 1; j < prevRow.size(); j++) {
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }

            row.add(1); // last element
            result.add(row);
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.generate(5));
    }
}

Explanation

• Line by Line:
  • result is the final list of lists that will hold all the rows.
  • If numRows is 0, we return an empty list.
  • Start with the first row [1].
  • For each row from 2 to numRows:
    • Retrieve the last row from result.
    • Start each new row with [1].
    • Calculate the intermediate values by summing adjacent values from the previous row.
    • End each row with [1].
    • Add the constructed row to result.
  • Return the resulting triangle.

This code ensures that the Pascal’s Triangle is built row by row with each element dependent on the values directly above it, conforming to the defined properties.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?