Given a positive integer N, return the N^{th} row of pascal's triangle.
Pascal's triangle is a triangular array of the binomial coefficients formed by summing up the elements of previous row.
Example :
1
1 1
1 2 1
1 3 3 1
For N = 3, return 3rd row i.e 1 2 1
Example 1:
Input:
N = 4
Output: 1 3 3 1
Explanation: 4^{th} row of pascal's triangle
is 1 3 3 1.
Example 2:
Input:
N = 5
Output: 1 4 6 4 1
Explanation: 5^{th} row of pascal's triangle
is 1 4 6 4 1.
 
Your Task:
Complete the function nthRowOfPascalTriangle() which takes n, as input parameters and returns an array representing the answer. The elements can be large so return it modulo 10^{9} + 7. You don't to print answer or take inputs.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ N ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3



#User function Template for python3

class Solution:



	def nthRowOfPascalTriangle(self,n):

	    # code here

Solutions:
class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = [[1], [1, 1]]
		if n < 2:
			return ans[n - 1]
		else:
			for i in range(2, n + 1):
				k = [0] * (i + 1)
				for j in range(i + 1):
					if j == 0 or j == i:
						k[j] = 1
					else:
						k[j] = (ans[i - 1][j - 1] + ans[i - 1][j]) % (10 ** 9 + 7)
				ans.append(k)
			return ans[n - 1]


class Solution:

	def sum_list(self, l):
		x = [1]
		for i in range(1, len(l)):
			x.append((l[i - 1] + l[i]) % (10 ** 9 + 7))
		x.append(1)
		return x

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		if n == 2:
			return [1, 1]
		l = [[] for i in range(n)]
		l[0] = [1]
		l[1] = [1, 1]
		for i in range(2, n):
			l[i] = self.sum_list(l[i - 1])
		return l[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		mat = [[1]]
		m = 1000000007
		for i in range(n - 1):
			temp1 = mat[-1] + [0]
			temp2 = [0] + mat[-1]
			mat.append([(temp1[i] + temp2[i]) % m for i in range(len(temp1))])
		return mat[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		if n == 2:
			return [1, 1]
		lst = self.nthRowOfPascalTriangle(n - 1)
		ans = []
		l = len(lst)
		ans.append(1)
		for i in range(l - 1):
			ans.append((lst[i] + lst[i + 1]) % 1000000007)
		ans.append(1)
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		lst = [1]
		for i in range(n - 1):
			ans = []
			for j in range(len(lst) - 1):
				ans.append((lst[j] + lst[j + 1]) % 1000000007)
			ans.insert(0, 1)
			ans.append(1)
			lst = ans.copy()
		return lst


class Solution:
	modNo = 10 ** 9 + 7

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		if n == 2:
			return [1, 1]
		prevRow = self.nthRowOfPascalTriangle(n - 1)
		currRow = []
		l = len(prevRow)
		for i in range(l):
			if i == 0 or i == l - 1:
				currRow.append(prevRow[i])
			if i != l - 1:
				currRow.append((prevRow[i] + prevRow[i + 1]) % Solution.modNo)
		return currRow


class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = [1] * n
		for i in range(n - 1):
			for j in range(i, 0, -1):
				ans[j] = (ans[j] + ans[j - 1]) % 1000000007
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		res = [[1]]
		mod = 1000000007
		for i in range(n - 1):
			temp = [0] + res[-1] + [0]
			row = []
			for j in range(len(res[-1]) + 1):
				row.append((temp[j] + temp[j + 1]) % mod)
			res.append(row)
		return res[n - 1]


from math import factorial

class Solution:

	def nthRowOfPascalTriangle(self, n):
		l = []
		for i in range(0, n):
			a = factorial(n - 1) // (factorial(n - 1 - i) * factorial(i)) % (10 ** 9 + 7)
			l.append(a)
		return l


class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = []
		mod = pow(10, 9) + 7
		for i in range(n):
			l = []
			if i == 0:
				l.append(1)
				ans.append(l)
			else:
				l.append(1)
				j = 1
				while j < i:
					l.append((ans[i - 1][j - 1] + ans[i - 1][j]) % mod)
					j += 1
				l.append(1)
				ans.append(l)
		return ans[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = [1]
		res = 1
		for i in range(1, n):
			res = res * (n - i)
			res = res // i
			ans.append(res)
		ans = [i % (10 ** 9 + 7) for i in ans]
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			tmp = [1]
			return tmp
		tans = self.nthRowOfPascalTriangle(n - 1)
		ans = []
		ans.append(1)
		for i in range(1, len(tans)):
			ans.append((tans[i] + tans[i - 1]) % 1000000007)
		ans.append(1)
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = [[1]]
		num = 1000000007
		for i in range(n - 1):
			temp = [0] + ans[-1] + [0]
			row = []
			for j in range(len(ans[-1]) + 1):
				row.append((temp[j] + temp[j + 1]) % num)
			ans.append(row)
		return ans[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):

		def element(n, c):
			res = 1
			for i in range(c):
				res = res * (n - i)
				res = res // (i + 1)
			return res
		li = []
		if n == 1:
			return [1]
		if n % 2 == 0:
			num = n // 2
			for i in range(1, num + 1):
				li.append(element(n - 1, i - 1) % (10 ** 9 + 7))
			li = li + li[::-1]
		else:
			num = n // 2 + 1
			for i in range(1, num + 1):
				li.append(element(n - 1, i - 1) % (10 ** 9 + 7))
			li = li + li[len(li) - 2::-1]
		return li


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		temp = self.nthRowOfPascalTriangle(n - 1)
		temp2 = []
		pow = 10 ** 9 + 7
		for i in range(n):
			if i == 0 or i == n - 1:
				temp2.append(1)
			else:
				temp2.append((temp[i] + temp[i - 1]) % pow)
		return temp2


class Solution:

	def nthRowOfPascalTriangle(self, n):
		li = [[1] * (i + 1) for i in range(n)]
		for i in range(n):
			for j in range(1, i):
				li[i][j] = (li[i - 1][j - 1] + li[i - 1][j]) % (10 ** 9 + 7)
		return li[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		num = n - 1
		den = 1
		row = [1]
		prev = row[-1]
		for i in range(n - 1):
			prev = prev * num // den
			num -= 1
			den += 1
			row.append(prev % (10 ** 9 + 7))
		return row


class Solution:

	def nthRowOfPascalTriangle(self, n):
		arr = [1]
		i = 1
		while i != n:
			arr1 = [1]
			for j in range(len(arr) - 1):
				arr1.append((arr[j] + arr[j + 1]) % (1000000000 + 7))
			arr1.append(1)
			arr.clear()
			arr.extend(arr1)
			i += 1
		return arr


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		lst = []
		n -= 1

		def rec(n, lst):
			ans = []
			if not n:
				return
			for i in range(len(lst) - 1):
				s = lst[i] + lst[i + 1]
				ans.append(s % (10 ** 9 + 7))
			lst[:] = [1] + ans[:] + [1]
			rec(n - 1, lst)
		rec(n, lst)
		return lst


import collections

class Solution:

	def nthRowOfPascalTriangle(self, n):
		op = []
		op.append(1)
		if n == 1:
			return op
		prev = self.nthRowOfPascalTriangle(n - 1)
		for i in range(1, len(prev)):
			curr = (prev[i - 1] % 1000000007 + prev[i] % 1000000007) % 1000000007
			op.append(curr)
		op.append(1)
		return op


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		if n == 2:
			return [1, 1]
		prev = self.nthRowOfPascalTriangle(n - 1)
		temp = [1]
		for i in range(len(prev) - 1):
			temp.append(prev[i] + prev[i + 1])
		temp.append(1)
		return list(map(lambda x: x % (10 ** 9 + 7), temp))


class Solution:

	def nthRowOfPascalTriangle(self, n):
		r = [1]
		c = 1
		for i in range(1, n):
			c = c * (n - i)
			c = c // i
			r.append(c % (10 ** 9 + 7))
		return r


class Solution:

	def nthRowOfPascalTriangle(self, n):
		m = 1000000007
		arr = []
		arr.append([1])
		arr.append([1, 1])
		k = 1
		for i in range(n):
			temparr = []
			temparr.append(1)
			for j in range(len(arr[k]) - 1):
				temparr.append((arr[k][j] + arr[k][j + 1]) % m)
			k += 1
			temparr.append(1)
			arr.append(temparr)
		return arr[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		MOD = int(1000000000.0) + 7
		temp = []
		all_rows = []
		for i in range(n):
			temp.insert(0, 1)
			for j in range(1, len(temp) - 1):
				temp[j] = (temp[j] + temp[j + 1]) % MOD
			all_rows.append(temp)
		return all_rows[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		else:
			answer = []
			answer.append(1)
			prev = self.nthRowOfPascalTriangle(n - 1)
			for i in range(1, len(prev)):
				answer.append((prev[i] + prev[i - 1]) % (10 ** 9 + 7))
			answer.append(1)
			return answer


class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = []
		for i in range(n):
			row = []
			for j in range(i + 1):
				if j == 0 or j == i:
					row.append(1)
				else:
					row.append((prev[j - 1] + prev[j]) % (10 ** 9 + 7))
			prev = row
			ans.append(prev)
		return ans[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		mod = 10 ** 9 + 7
		if n == 1:
			return [1]
		if n == 2:
			return [1, 1]
		arr = [1, 1]
		newarr = []
		n -= 2
		for i in range(n):
			newarr = []
			newarr.append(arr[0])
			for j in range(len(arr) - 1):
				newarr.append((arr[j] + arr[j + 1]) % mod)
			newarr.append(arr[-1])
			arr = newarr
		return arr


from math import factorial as f

class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		if n == 2:
			return [1, 1]
		pascal = [[1], [1, 1]]
		for j in range(2, n):
			temp = pascal[-1].copy()
			for i in range(j - 1):
				temp[i + 1] = (pascal[j - 1][i] + pascal[j - 1][i + 1]) % (10 ** 9 + 7)
			temp.append(1)
			pascal.append(temp)
		return pascal[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		arr = []
		for i in range(n):
			inner = []
			for index in range(i + 1):
				if index == 0 or index == i:
					inner.append(1)
				else:
					inner.append((arr[index] + arr[index - 1]) % (10 ** 9 + 7))
			arr = inner
		return arr


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		elif n == 2:
			return [1, 1]
		pascal_triangle = [[1], [1, 1]]
		for j in range(2, n):
			temp_row = pascal_triangle[-1].copy()
			for i in range(j - 1):
				temp_row[i + 1] = (pascal_triangle[j - 1][i] + pascal_triangle[j - 1][i + 1]) % 1000000007
			temp_row.append(1)
			pascal_triangle.append(temp_row)
		return pascal_triangle[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		l = [1]
		k = [[1], [1, 1]]
		if n == 1:
			return l
		elif n == 2:
			return k[-1]
		else:
			while n - 2:
				q = k[-1]
				p = [1]
				for i in range(len(q) - 1):
					p.append((q[i] + q[i + 1]) % (10 ** 9 + 7))
				p.append(1)
				k.append(p)
				n -= 1
		return k[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		res1 = []
		res2 = []
		mod = 10 ** 9 + 7
		for i in range(1, n + 1):
			res1.append(1)
			if i > 2:
				temp = []
				for j in range(len(res2) - 1):
					temp.append((res2[j] + res2[j + 1]) % mod)
				res1.extend(temp)
				res1.append(1)
			elif i == 2:
				res1.append(1)
			res2 = res1.copy()
			if i != n:
				res1.clear()
		return res1


class Solution:

	def nthRowOfPascalTriangle(self, n):
		mod = 10 ** 9 + 7
		triangle = []
		for i in range(n):
			row = [1]
			for j in range(1, i):
				row.append((triangle[i - 1][j - 1] + triangle[i - 1][j]) % mod)
			if i > 0:
				row.append(1)
			triangle.append(row)
		return triangle[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		mat = list()
		mat.append([1])
		for i in range(1, n):
			l = []
			for j in range(i + 1):
				if j == 0 or j == i:
					l.append(1)
				else:
					l.append((mat[i - 1][j] + mat[i - 1][j - 1]) % 1000000007)
			mat.append(l)
		return mat[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, N):
		prev = 1
		ans = [1]
		for i in range(1, N):
			curr = prev * (N - i) // i
			ans.append(curr % (pow(10, 9) + 7))
			prev = curr
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		temp = [0] * n
		if n == 1:
			a = [0] * 1
			a[0] = 1
			return a
		if n == 2:
			a = [0] * 2
			a[0] = 1
			a[1] = 1
			return a
		a = self.nthRowOfPascalTriangle(n - 1)
		temp[0] = 1
		temp[n - 1] = 1
		for i in range(n - 2):
			temp[i + 1] = (a[i] + a[i + 1]) % (10 ** 9 + 7)
		return temp


class Solution:

	def nthRowOfPascalTriangle(self, n):
		x = [[1] * i for i in range(1, n + 1)]
		for i in range(n):
			for j in range(1, i):
				x[i][j] = (x[i - 1][j - 1] + x[i - 1][j]) % 1000000007
		return x[n - 1]


from math import factorial

class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = []
		for i in range(n):
			ans.append(factorial(n - 1) // (factorial(i) * factorial(n - 1 - i)) % (10 ** 9 + 7))
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		res = []
		from math import factorial

		def ncr(n, r):
			return factorial(n) // (factorial(n - r) * factorial(r))
		for i in range(n):
			res.append(ncr(n - 1, i) % (10 ** 9 + 7))
		return res


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		arr = self.nthRowOfPascalTriangle(n - 1)
		ans = [0] * n
		ans[0] = 1
		ans[n - 1] = 1
		for i in range(1, len(arr)):
			ans[i] = (arr[i] + arr[i - 1]) % 1000000007
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		(r1, r2) = ([1], [1, 1])
		pt = []
		f = 1
		while f <= n:
			pt.append(r1)
			(r1, r2) = (r2, [1] + [sum(i) % (10 ** 9 + 7) for i in zip(r2, r2[1:])] + [1])
			f += 1
		return pt[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		MOD = 10 ** 9 + 7
		(dp1, dp2) = ([0] * n, [0] * n)
		dp1[0] = dp2[0] = 1
		for i in range(n):
			for j in range(1, i + 1):
				dp2[j] = (dp1[j] + dp1[j - 1]) % MOD
			(dp1, dp2) = (dp2, dp1)
		return dp1


class Solution:

	def nthRowOfPascalTriangle(self, n):
		l = [[1]]
		for i in range(1, n):
			o = []
			for j in range(i + 1):
				if j == 0 or j == i:
					o.append(1)
				else:
					o.append((l[i - 1][j] + l[i - 1][j - 1]) % (10 ** 9 + 7))
			l.append(o)
		return l[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		T = [[1] * i for i in range(1, n + 1)]
		for j in range(2, n):
			for i in range(1, len(T[j]) - 1):
				T[j][i] = (T[j - 1][i] + T[j - 1][i - 1]) % 1000000007
		return T[-1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		n -= 1
		m = int(1000000000.0 + 7)
		factorials = {0: 1}
		for i in range(1, n + 1):
			factorials[i] = factorials[i - 1] * i
			factorials[i] %= m
		factorial_inverse = {}
		for i in factorials:
			factorial_inverse[i] = pow(factorials[i], m - 2, m)
		ans = []
		for r in range(n + 1):
			ans.append(factorials[n] * factorial_inverse[n - r] * factorial_inverse[r] % m)
		return ans


class Solution:

	def nthRowOfPascalTriangle(self, n):
		mod = 1000000007
		r = [[1 for _ in range(i + 1)] for i in range(n)]
		for i in range(n):
			for j in range(1, i):
				r[i][j] = (r[i - 1][j - 1] + r[i - 1][j]) % mod
		return r[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, n):
		triangle = [[1]]
		for i in range(1, n):
			row = []
			for j in range(i + 1):
				prev_row = triangle[i - 1]
				if j - 1 < 0:
					left_part = 0
				else:
					left_part = prev_row[j - 1]
				if j > i - 1:
					right_part = 0
				else:
					right_part = prev_row[j]
				row.append((left_part + right_part) % (10 ** 9 + 7))
			triangle.append(row)
		return triangle[n - 1]


class Solution:

	def nthRowOfPascalTriangle(self, N):
		a = [1, 1]
		if N == 1:
			return [1]
		for i in range(0, N - 2):
			b = [1]
			for j in range(0, len(a) - 1):
				entry = a[j] + a[j + 1]
				b.append(entry % 1000000007)
			b.append(1)
			a = b
		return a


class Solution:

	def nthRowOfPascalTriangle(self, n):
		n -= 1
		l = [1]
		curr = 1
		for r in range(n):
			curr = curr * (n - r) // (1 + r)
			l.append(curr % 1000000007)
		return l


class Solution:

	def nthRowOfPascalTriangle(self, n):
		if n == 1:
			return [1]
		arr = []
		for row_idx in range(1, n):
			new_arr = [1] * (row_idx - 1)
			for el in range(0, row_idx - 1):
				new_arr[el] = arr[el] + arr[el + 1]
			arr = [1] + new_arr + [1]
		for i in range(len(arr)):
			arr[i] = arr[i] % 1000000007
		return arr


class Solution:

	def nthRowOfPascalTriangle(self, n):

		def recursion(n):
			if n == 1:
				return [1]
			prev = recursion(n - 1)
			res = [1]
			for i in range(1, len(prev)):
				res += ((prev[i] + prev[i - 1]) % 1000000007,)
			res.append(1)
			return res
		return recursion(n)


class Solution:

	def nthRowOfPascalTriangle(self, n):
		ans = [[1]]
		while len(ans) < n:
			lastRow = ans[len(ans) - 1]
			current = []
			current.append(lastRow[0])
			for i in range(len(lastRow) - 1):
				current.append(lastRow[i] + lastRow[i + 1])
			current.append(lastRow[len(lastRow) - 1])
			ans.append(current)
		final_ans = ans.pop()
		for i in range(len(final_ans)):
			final_ans[i] = final_ans[i] % (10 ** 9 + 7)
		return final_ans