Simple solution using Mathematical formula for Pascal's triangle. Beats 95%!!


  • 0
    H

    Nth row of Pascal's triangle is given by:

    NC0, NC1, NC2, NC3,... NCN

    where NCR = factorial(n)/(factorial(r)*factorial(n-r))

    using this concept we can easily generate rows for Pascal's triangle by writing a function for finding NCR. Here is the code in Python:

    def ncr(n,r):
        """
        Be careful about overflow while writing code for factorial.
        Numbers can get very huge very quickly.
        In here since we have to divide by other factorials, multiply only required numbers.
        """
        if n == r or r == 0:
            return 1
        num = 1
        den = 1
        x = min(r,n-r)
        for i in range(x):
            num *= n-i
        for i in range(x):
            den *= i+1
        
        return num/den    
        
    class Solution(object):
        def generate(self, numRows):
            """
            :type numRows: int
            :rtype: List[List[int]]
            """
            res = []
            for i in range(numRows):
                row = []
                for j in range(i+1):
                    row.append(ncr(i,j))
                res.append(row)
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.