Pascal's Triangle II.md

Algorithm

• The elements of the kth row of Pascal's triangle are equal to the coefficients of the expansion of (a + b)^k
• For the 4th line, k = 4, so we have (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴
• The coefficients of the above polymonial are 1 4 6 4 1, which is the same as the 4th row of Pascal's triangle
• These coefficients could be calculated directly as ₄C₀, ₄C₁, ₄C₂, ₄C₃, ₄C₄, using the Combination Formula which lets us calculate any number in Pascal's triangle directly
• As an optimization, we can reuse the previous number in a row to create the next number. This is how you calculate the numbers in the kth row.

Solution

class Solution {
    public List<Integer> getRow(int k) {
        if (k < 0) {
            return new ArrayList();
        }
        List<Integer> row = new ArrayList();
        row.add(1);
        int top = k; // multiplier in numerator
        int bot = 1; // multiplier in denominator
        long C = 1; // use a `long` to prevent integer overflow
        for (int i = 1; i <= k; i++) {
            C *= top;
            C /= bot;
            top--;
            bot++;
            row.add((int) C);
        }
        return row;
    }
}

which can be simplified to:

class Solution {
    public List<Integer> getRow(int k) {
        if (k < 0) {
            return new ArrayList();
        }
        List<Integer> row = new ArrayList();
        row.add(1);
        long C = 1; // use a `long` to prevent integer overflow
        for (int i = 1; i <= k; i++) {
            C = C * (k + 1 - i) / i;
            row.add((int) C);
        }
        return row;
    }
}

Time/Space Complexity

• Time Complexity: O(k)
• Space Complexity: O(k)

Links

• github.com/RodneyShag