Pascal's Triangle - Leetcode 118 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
5:55 - Coding Explanation

leetcode 118

#pascals #triangle #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[shoooozzzz]

The easy problems look like hard problems when you're trying to come up with a solution in O(n). Turns out the "optimal" solution is O(n)^2 using a nested for-loop =)

[msyugandhar]

I have a doubt, Why can't we just add a 1 to the beginning and to the end for every new list so that there is no need to add a 0 to the previous list??

[Moch]

Your two-pointer hint made this easy. I was stuck on this for awhile

Super annoying problem

[abudajaaj]

There's a mathematical algorithm to find each value by row: (nCk) = (nC(k-1)) * (n+1-k)/k, which works really well, yet I couldn't get it to work because of a weird issue at row 11 where it goes from 461 down to 329, which is 1 less than it should be.

[putin_navsegda]

I did this problem by myself, however i used binomial distribution. Thank you for your video and explication

[edwardteach]

U a God. Got another way instead of dealing with those pesky 0's on the left and right end. We create another temp array already filled with 1's for both sides:

res = [[1]]
for _ in range(1, numRows):
temp = [1] * (len(res[-1]) + 1)
for i in range(1, len(temp)-1):
temp[i] = res[-1][i-1] + res[-1][i]
res.append(temp)
return res

[dikshyantthapa]

You can also use length of temp-1 for interating over previous rows numbers for making new row.

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[1]]
for i in range(numRows-1):
temp = [0] + res[-1] + [0]
row=[]
for j in range(len(temp)-1):
row.append(temp[j] + temp[j+1])
res.append(row)
return res

[jianchoi]

파스칼 삼각형의 각 행의 끝에 0을 넣는다는 아이디어는 인터넷 전체에서 이 분이 처음으로 내신 것 같은데, 정말 기발한 것 같아요. 다음에는 저 방식으로 스크립트를 짜 봐야겠다는 생각이 듭니다 감사합니다

[fazlerabbi]

in line 8 how was the range(len(res[-1]) + 1) deduced? can't wrap my head around it..

[AryanKumar-cmiq]

There is no need to add a 0 in the start or the end

def generate(self, numRows: int) -> List[List[int]]:

if numRows==1: return [[1]]
if numRows==2: return [[1], [1, 1]]
itr=numRows-2
pa=[[1], [1, 1]]
while itr:
l=[]
for i in range(len(pa[-1])-1):
s=pa[-1][i]+pa[-1][i+1]
l.append(s)
l.insert(0, 1)
l.append(1)
pa.append(l)
itr-=1
return pa

[Progamer-fqst]

Another solution without adding zeros at the end

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> v;


for(int i = 0;i<numRows;i++){
vector<int> row;
for (int j = 0; j <= i; j++)
{
if(j == 0 || j == i){
row.push_back(1);
}
else{
int num = v[i-1][j-1] + v[i-1][j];
row.push_back(num);
}
}
v.push_back(row);
}

return v;
}
};

[kbizzy]

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
temp = [1]*(i+1)
for j in range(1, i):
temp[j] = res[i-1][j-1] + res[i-1][j]
res.append(temp)
return res

[aishwaryadeep]

Correction maybe :
for i in range(1, numRows): #should be the first loop

[danielsun]

excluding tricks' version FYI:

def generate(self, numRows: int) -> List[List[int]]:
if numRows == 1:
return [[1]]
res = [[1], [1, 1]]
dp = res[-1]
for i in range(2, numRows):
nextDP = [1] * (len(dp) + 1)
for j in range(1, len(nextDP) - 1):
nextDP[j] = dp[j - 1] + dp[j]
dp = nextDP
res.append(dp)
return res

[BobBob-e]

how does this question have anything to do with bfs it doesnt use a queue? seems like you just store each layer so you can use it to calculate the next...

[vishnusunil]

Absolutely stunning piece of code can i get a reference to Google or Amazon 😃

[JashSingh-bvge]

im still not understanding how the code works :(

[nikhilgupta]

This might be easier to understand:

def generate(numRows):
dp=[[1]*i for i in range(1, numRows+1)]

for i in range(2, numRows):
for j in range(i+1):
if j!=0 and i!=j:
dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

return dp

[ksvignesh]

class Solution(object):
def generate(self, numRows):
n = numRows
fl = []
l = []
ans = [[1]]
for i in range(n-1):
r = []
for i in range(len(l)-1):
a = l[i]
b = l[i+1]
c = a + b
for i in range(len(l)):
a, b = b, a
r += c,
f = [1]
for i in r:
f += i,
f += 1,
ans += f,
l = f
fl += l
return ans


This solution is fully logical, simple and beats 74.18%
Feel free to comment if you have any doubts in my code! :)

[memeproductions]

i just added a 1 at the start and at the end of each new row