Shortest (4 Lines) single pass O(k) python solution


  • 0

    I realized that the 2nd element was always k, 3rd element was increased by the factor of 0.5(1/2) each time k increased by 1 (compared to the previous element), 4th element increased by the factor of 0.33..(1/3) each time k increased by 1 (also compared to the previous element).
    So after some time I figured out that the number at answer[i] = answer[i - 1] * (k + 1 - i) / i
    I would love to know the formal mathematics proof behind this.
    Anyways, here is my code:

    
    class Solution(object):
        def getRow(self, rowIndex):
            answer = [1]
            for i in xrange(1, rowIndex + 1):
                answer.append(answer[-1] * (rowIndex + 1 - i) / i)
            return answer
    

Log in to reply
 

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