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

Solution 1

What we need to do in this problem is to follow definition. Let us generate row r and do k iterations until we reached desired k-tho row. How we generate next row, using current? We need:

  1. Add 1 to the beginning of new row.
  2. Evaluate sums of elements with indexes differ by 1.
  3. Add 1 to the end of new row.

This can be written as [1]+[r[j]+r[j+1] for j in range(len(r)-1)]+[1].

What we need to do now is to repeat this k times and this is all, we can use reduce function to do it.

Complexity: space complexity as it asked is only O(k), each moment of time we have only one(two) rows. Time complexity is O(k^2) because for each row we do k iterations. Theoretically time complexity can be reduced to O(k) if we use direct formulas for elements of pascal triangle, but k is very small and there will no be difference in this problem.

class Solution:
    def getRow(self, rowIndex):
        return reduce(lambda r,_:[1]+[r[j]+r[j+1] for j in range(len(r)-1)]+[1], range(rowIndex),[1])

Solution 2

Let us note, that 1001^5 = 1 005 010 010 005 001, so if we want to find row of Pascal triangle for small numbers k, then we can just use power of number 1000...001 and then split it into parts. For thes problem it is enough to take 10000000001 and then split by blocks with size 10.

Complexity: Space complexity is also O(k), but more like O(10k), because we have string of length 10k in the end. Time complexity is more difficult to compute, I think it is O(k) also.

class Solution:
    def getRow(self, k):
        return [1] + [int(str((10**10+1)**k)[-10*(i+1):-10*i]) for i in range(1,k+1)]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0119