Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.


In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:


Input: 3
Output: [1,3,3,1]


Follow up:

Could you optimize your algorithm to use only O(k) extra space?

Source: leetcode | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        

Solutions:
class Solution:

	def getRow(self, k):
		res = [1]
		cur = k
		for i in range(k // 2):
			res += (res[-1] * cur // (i + 1),)
			cur -= 1
		if k % 2 == 0:
			res = res + res[:-1][::-1]
		else:
			res = res + res[::-1]
		return res


class Solution:

	def getRow(self, rowIndex):
		a = [1]
		i = 0
		b = [1]
		while i < rowIndex:
			a.append(0)
			b = a[:]
			for j in range(i + 2):
				b[j] = a[j] + a[i - j + 1]
			a = b
			i += 1
		return b


class Solution:

	def getRow(self, rowIndex):
		res = [1]
		for i in range(1, rowIndex + 1):
			res += [1]
			for j in range(len(res) - 2, -1, -1):
				if j > 0:
					res[j] = res[j] + res[j - 1]
				else:
					res[j] = 1
		return res


class Solution:

	def getRow(self, rowIndex):
		out = [1]
		for i in range(1, rowIndex + 1):
			temp = []
			for j in range(0, i - 1):
				temp.append(out[j] + out[j + 1])
			out = [1] + temp + [1]
		return out


class Solution:

	def getRow(self, rowIndex):
		l = [1]
		for i in range(rowIndex):
			l = [j + k for (j, k) in zip([0] + l, l + [0])]
		return l


class Solution:

	def getRow(self, rowIndex):
		result = []
		for n in range(rowIndex + 1):
			num = 1
			for i in range(n):
				num = int(num * (rowIndex - i) / (i + 1))
			result = result + [num]
		return result


class Solution:

	def getRow(self, rowIndex):
		if rowIndex < 0:
			return list()
		if rowIndex == 0:
			return list([1])
		l = list([1])
		for i in range(1, rowIndex + 1):
			pre_value = l[0]
			for j in range(1, i):
				temp = l[j]
				l[j] = pre_value + l[j]
				pre_value = temp
			l.append(1)
		return l


class Solution:

	def getRow(self, rowIndex):
		rows = [1]
		for i in range(rowIndex):
			rows = [x + y for (x, y) in zip([0] + rows, rows + [0])]
		return rows


class Solution:

	def getRow(self, rowIndex):
		row = [1]
		for _ in range(rowIndex):
			row = [x + y for (x, y) in zip([0] + row, row + [0])]
		return row


class Solution:

	def getRow(self, rowIndex):
		if rowIndex < 0:
			return []
		result = [0 for _ in range(rowIndex + 1)]
		result[0] = 1
		for i in range(1, rowIndex + 1):
			result[i] = 1
			for j in range(i - 1, 0, -1):
				result[j] = result[j] + result[j - 1]
		return result


class Solution:

	def getRow(self, rowIndex):
		i = 1
		res = [1]
		while rowIndex >= 1:
			res.append(int(res[-1] * rowIndex / i))
			(rowIndex, i) = (rowIndex - 1, i + 1)
		return res