algoadvance

Leetcode 119. Pascals Triangle II

Problem Statement

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

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

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

Input: rowIndex = 0
Output: [1]

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

Clarifying Questions

  1. Minimum and Maximum Value of rowIndex: What is the expected range for rowIndex? Typically it will be non-negative.
  2. Handling Large Inputs: Do we need to consider integer overflow for large values?
  3. Constraints and Performance: Are there any specific constraints or performance expectations?

For now, we will assume rowIndex is a non-negative integer and not extraordinarily large for normal computational purposes.

Strategy

  1. Initialization: Start with the first row [1].
  2. Iteration: For each subsequent row, compute each element as the sum of the two elements directly above it from the previous row.
  3. Return the Desired Row: Stop once we reach the rowIndex row and return it.

We will use a single list and update it in place to maintain constant space complexity for this iterative approach.

Code

import java.util.*;

public class PascalTriangleII {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1); // First row is always [1]
        
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = row.size() - 1; j >= 1; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
            row.add(1); // Add the ending '1' for each row
        }
        
        return row;
    }

    public static void main(String[] args) {
        PascalTriangleII solution = new PascalTriangleII();
        System.out.println(solution.getRow(3)); // Output: [1, 3, 3, 1]
        System.out.println(solution.getRow(0)); // Output: [1]
        System.out.println(solution.getRow(1)); // Output: [1, 1]
    }
}

Time Complexity

The time complexity of this solution is O(rowIndex^2), where rowIndex is the given input. This is due to the nested loop structure where we have to update the list for each row up to rowIndex.

Space Complexity

The space complexity is O(rowIndex) because we use a single list to store the current row of Pascal’s triangle, and its size grows linearly with rowIndex.

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