Sunday, March 22, 2020

LeetCode 119. Pascal's Triangle II

Question: https://leetcode.com/problems/pascals-triangle-ii/

This is a classic question, but I have not done this problem before. Personally, I like solving math-related algorithm questions, like those in the Euler's Project. This is not quite the kind of math question. Nonetheless, Pascal is one of the greatest mathematicians. So a question bearing his name would be worth doing.  The idea is just to apply the definition of a pascal triangle but using a fixed-size array. Given a rowIndex, we will know the size of the array. For instance, rowIndex=3, gives us [1,3,3,1] an array of size 4. Therefore, given rowIndex, we simply initialize a size (rowIndex+1) array. The key idea is that an array of this size would be sufficient enough to store all the previous solutions for smaller rowIndex. We will keep using this same array to store the solutions when the input = rowIndex-1. For instance, we will start with [1,1,1,1]. Starting from the rowIndex =2, we will have a = 1, b=1 and c = a+b=2 and insert 2 into the correct position yielding [1,2,1,1]. In the next iteration, we will calculate the rowIndex=3. The initial array is [1,2,1,1] , where the subarray [1,2,1] is the solution to rowIndex=2, summing from left to right will yield [1,3,3,1], as desired. A small detail to pay attention to is the assignment of a,b for the next iteration. Since we will be assigning ans[j+1] to the new value c=a+b, we will lose the reference to the next a, therefore, we will do the assignment after we have moved a, b pointers forward for the next iteration.


class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0:
            return [1]
        elif rowIndex == 1:
            return [1,1]
        else:
            ans = [1 for _ in range(rowIndex+1)]
            for i in range(1, rowIndex):
                a = ans[0]
                b = ans[1]
                for j in range(i):
                    c = a + b
                    a, b = b, ans[j+2]
                    ans[j+1] = c
            return ans

No comments:

Post a Comment