Question

Formatted question description: https://leetcode.ca/all/119.html

Given an integer rowIndex, return the rowIndex^th (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 1:

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

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

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

Constraints:

0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Algorithm

Except for the first and last numbers, the other numbers are the sum of the left and right values in the previous line. Then we only need two for loops.

Except for the first number being 1, the following numbers are the sum of the value of the previous loop plus the value of the previous position, and keep updating the value of each position. You can get the number in the nth row.

Code

public class Pascals_Triangle_II {

    public class Solution_noExtraSpace {
        public List<Integer> getRow(int rowIndex) {

            List<Integer> res = new ArrayList<>();
            res.add(1);
            for (int i = 1; i <= rowIndex; ++i) {
                for (int j = i; j >= 1; --j) {
                    res.set(j, res.get(j) + res.get(j - 1));
                }
            }
            return res;

        }
    }

    public class Solution {
        public List<Integer> getRow(int rowIndex) {

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

            if (rowIndex < 0) {
                return row;
            }

            row.add(1);
            if (rowIndex == 0) {
                return row;
            }

            for (int i = 2; i <= rowIndex + 1; i++) {
                List<Integer> current = new ArrayList<>(row);

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

                    if (j < row.size()) {
                        int add = row.get(j) + row.get(j - 1); // j starts at 1, so j-1 guaranteed ok
                        current.set(j, add);
                    } else {
                        // current.set(j, 1);
                        current.add(1); // @note: the last one, just add, not set
                    }
                }

                row = current;
            }

            return row;

        }
    }
}



############

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i < rowIndex + 1; ++i) {
            row.add(1);
        }
        for (int i = 2; i < rowIndex + 1; ++i) {
            for (int j = i - 1; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}

// OJ: https://leetcode.com/problems/pascals-triangle-ii/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex + 1, 1);
        for (int i = 2; i <= rowIndex; ++i) {
            for (int j = i - 1; j > 0; --j) ans[j] += ans[j - 1];
        }
        return ans;
    }
};

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)
        for i in range(2, rowIndex + 1):
            for j in range(i - 1, 0, -1):
                row[j] += row[j - 1]
        return row

############

class Solution(object):
  def getRow(self, rowIndex):
    """
    :type rowIndex: int
    :rtype: List[int]
    """
    fact = [1] * (rowIndex + 1)
    ans = [1] * (rowIndex + 1)
    for i in range(1, rowIndex + 1):
      fact[i] = fact[i - 1] * i
    for i in range(1, rowIndex):
      ans[i] = fact[-1] / (fact[i] * fact[rowIndex - i])
    return ans

func getRow(rowIndex int) []int {
	row := make([]int, rowIndex+1)
	row[0] = 1
	for i := 1; i <= rowIndex; i++ {
		for j := i; j > 0; j-- {
			row[j] += row[j-1]
		}
	}
	return row
}

function getRow(rowIndex: number): number[] {
    let ans = new Array(rowIndex + 1).fill(1);
    for (let i = 2; i < rowIndex + 1; ++i) {
        for (let j = i - 1; j > 0; --j) {
            ans[j] += ans[j - 1];
        }
    }
    return ans;
}

impl Solution {
    pub fn get_row(row_index: i32) -> Vec<i32> {
        let n = (row_index + 1) as usize;
        let mut res = vec![1; n];
        for i in 2..n {
            for j in (1..i).rev() {
                res[j] += res[j - 1];
            }
        }
        res
    }
}

119 - Pascal's Triangle II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions