Pascal's Triangle II

1. Create an empty list result to store the row.
2. Loop with an index k from 0 to rowIndex.
3. In each iteration, call a recursive helper function, pascalValue(rowIndex, k), to compute the element at that position.
4. Add the value returned by the helper function to the result list.
5. The pascalValue(row, col) helper function is defined as follows:
   • Base Case: If col is 0 or col is equal to row, return 1.
   • Recursive Step: Otherwise, return the sum of pascalValue(row - 1, col - 1) and pascalValue(row - 1, col).

We define a recursive function, say pascalValue(row, col), which computes the value at a specific position in the triangle. The base cases for the recursion are when col == 0 or col == row, in which case the value is 1. For any other position (row, col), the value is the sum of pascalValue(row - 1, col - 1) and pascalValue(row - 1, col). To generate the final result, we create a list and iterate from k = 0 to rowIndex, populating the list with the results of pascalValue(rowIndex, k). This method is highly inefficient because it recomputes the same values multiple times. For example, calculating the value at (5, 2) and (5, 3) both require computing the value at (4, 2), leading to an exponential number of overlapping subproblems.

1class Solution {2    public List<Integer> getRow(int rowIndex) {3        List<Integer> row = new ArrayList<>();4        for (int k = 0; k <= rowIndex; k++) {5            row.add(pascalValue(rowIndex, k));6        }7        return row;8    }9 10    private int pascalValue(int row, int col) {11        if (col == 0 || col == row) {12            return 1;13        }14        // Recursive step15        return pascalValue(row - 1, col - 1) + pascalValue(row - 1, col);16    }17}

1. Initialize a list of lists, triangle.
2. Add the first row, [1], to triangle.
3. Loop with an index i from 1 to rowIndex.
   • In each iteration, get the previous row prevRow from triangle.get(i-1).
   • Create a new list currentRow.
   • Add 1 as the first element of currentRow.
   • Loop with an index j from 1 to i-1.
     • Calculate the sum prevRow.get(j-1) + prevRow.get(j) and add it to currentRow.
   • Add 1 as the last element of currentRow.
   • Add currentRow to the triangle.
4. After the loops complete, return the list at index rowIndex from triangle.

Instead of recomputing values, we can use dynamic programming. We build the triangle from the top down. We start by creating the first row [1]. Then, for each subsequent row i, we generate its elements using the values from the previously computed row i-1. The j-th element of row i is the sum of the (j-1)-th and j-th elements of row i-1. We store all these rows in a list of lists. While this is much more efficient than the recursive approach, it uses more space than required.

1class Solution {2    public List<Integer> getRow(int rowIndex) {3        List<List<Integer>> triangle = new ArrayList<>();4        5        // First row6        triangle.add(new ArrayList<>());7        triangle.get(0).add(1);8        9        for (int i = 1; i <= rowIndex; i++) {10            List<Integer> row = new ArrayList<>();11            List<Integer> prevRow = triangle.get(i - 1);12            13            row.add(1); // First element of each row is 114            15            for (int j = 1; j < i; j++) {16                row.add(prevRow.get(j - 1) + prevRow.get(j));17            }18            19            row.add(1); // Last element of each row is 120            triangle.add(row);21        }22        23        return triangle.get(rowIndex);24    }25}

1. Initialize a list row with the first element 1.
2. Loop with an index i from 1 to rowIndex. This outer loop corresponds to building each row from 1 to rowIndex.
3. Inside the loop, iterate backwards from j = i - 1 down to 1.
   • Update the element at index j by adding the element at j-1 to it: row.set(j, row.get(j) + row.get(j-1)).
4. After the inner loop, append a 1 to the end of the list row. This completes the i-th row.
5. After the outer loop finishes, row will hold the rowIndex-th row of Pascal's triangle.

We can optimize the space complexity of the DP approach to O(rowIndex). We only need to store one row at a time. To compute the next row, we can modify the current row in-place. The key insight is to perform the updates from right to left. If we update from left to right, we would overwrite values that are still needed for subsequent calculations in the same row. By iterating backwards, we use the 'old' values from the previous row's computation before they are updated.

For each new row i, we first conceptually have the (i-1)-th row. The i-th row will have one more element. We can add a 1 at the end and then update the values from right to left.

1class Solution {2    public List<Integer> getRow(int rowIndex) {3        List<Integer> row = new ArrayList<>();4        row.add(1); // Corresponds to row 05 6        for (int i = 1; i <= rowIndex; i++) {7            // Update existing elements from right to left8            for (int j = i - 1; j > 0; j--) {9                row.set(j, row.get(j) + row.get(j - 1));10            }11            // Add the last element for the new row12            row.add(1);13        }14        return row;15    }16}

1. Create an empty list row.
2. Initialize a long variable val = 1. This will hold the current coefficient value.
3. Loop with an index k from 0 to rowIndex.
   • Add the current val (cast to an int) to the row list.
   • Update val for the next iteration using the formula: val = val * (rowIndex - k) / (k + 1).
4. Return the row list.

The k-th element (0-indexed) of the n-th row is given by the binomial coefficient C(n, k). Instead of calculating factorials, which can lead to overflow, we can use the multiplicative formula which relates adjacent coefficients: C(n, k) = C(n, k-1) * (n - k + 1) / k.

We can generate the entire rowIndex-th row in a single pass. We start with the first element, C(rowIndex, 0), which is 1. Then, we loop from k = 1 to rowIndex, calculating each subsequent element using the value of the previous element and the formula above. This avoids nested loops and results in a linear time complexity.

1class Solution {2    public List<Integer> getRow(int rowIndex) {3        List<Integer> row = new ArrayList<>(rowIndex + 1);4        long val = 1;5        6        for (int k = 0; k <= rowIndex; k++) {7            row.add((int) val);8            // Calculate the next value in the row9            // C(n, k+1) = C(n, k) * (n-k) / (k+1)10            val = val * (rowIndex - k) / (k + 1);11        }12        13        return row;14    }15}