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 =)
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??
this is a way of doing it and it works, I have this solution: triangle = [] triangle.append([1]) if numRows == 1: return triangle triangle.append([1, 1]) if numRows == 2: return triangle for i in range(2, numRows): curr_row = [1] prev_row = triangle[-1] for j in range(1, i): curr_row.append(prev_row[j-1] + prev_row[j]) curr_row.append(1) triangle.append(curr_row) return triangle
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.
I had solved this before watching the video. His solution is better, but, for the sake of seeing another solution, I thought I would post the solution I had come up with. Python3 def generate(cls, num_rows: int) -> List[List[int]]: if num_rows
Nice Here is my solution, time complexity is O(n^2), need to optimize class Solution: def generate(self, numRows: int) -> List[List[int]]:
lst, finalLst = [0, 1, 0], [[1]] for i in range(numRows - 1): l, r = 0, 1 newLst = [] while(r < len(lst)): element = lst[l] + lst[r] newLst.append(element) l = r r = r + 1 finalLst.append(newLst) newLst = [0]+newLst+[0] lst = newLst
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
@@NeetCode here's the code without worrying much *) final_res = [ ] for i in range(numRows): res = [ ] for j in range(i+1): if j == 0 or j == i: res.append(1) else: elem = final_res[i-1][j] + final_res[i-1][j-1] res.append(elem) final_res.append(res)
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
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
Sir can u please check this once... I think this is a pretty clever approach.. Code : result = [] for i in range(row): s = [] for j in range(i + 1): if j !=0 and j != i: s.append(result[i-1][j] + result[i-1][j-1]) else: s.append(1) result.append(s) return result Please let me know !!
Yes, Your solution took 13.9 mb and his solution took 13.8 mb. It may seem insignificant for smaller inputs, but not for larger inputs. I think. Thanks for your sharing your solution.
So basically, len(res[-1]) is used to get the length of the last row in the list cuz [-1] represents the last element . Since every new row in the pascal's triangle is 1 element longer we add 1 to len(res[-1]) to get the range.
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...
@@thirunaavukkarasum4487 actually Here's a breakdown: [0]: This list creation has a time complexity of O(1) because it involves a single element. res[-1]: This operation has a time complexity of O(1). It's a simple retrieval operation that gets the last element of res. If res[-1] itself is a list of length m, then creating a new copy of this list (which happens implicitly when we do list concatenation) will take O(m). [0]: Same as the first operation, it's O(1). +: The concatenation operation has time complexity O(n), where n is the length of the resulting list. So overall you are right it is a O(n^3) solution
I Have added 1 at both ends and updated unfilled columns with two pointer solution List result = new ArrayList(numRows); if (numRows >= 1) { result.add(Arrays.asList(1)); } if (numRows >= 2) { result.add(Arrays.asList(1, 1)); } if (numRows > 2) { for (int i = 3; i
class Solution: def generate(self, numRows: int) -> List[List[int]]: outerArray = [] for i in range(1,numRows+1): tempArray = [1]*i for j in range(1,i-1): tempArray[j] = outerArray[i - 2][j-1] + outerArray[i - 2][j] outerArray.append(tempArray) return outerArray Is it good Solution
#My solution class Solution: def generate(self, numRows: int) -> List[List[int]]: answer = [[1], [1,1]] if numRows == 1: return [answer[0]] if numRows == 2: return answer for i in range(numRows-2): answer.append([1]) for i in range(2, len(answer)): for j in range(1, i): answer[i].append(answer[i - 1][j - 1] + answer[i - 1][j]) answer[i].append(1) return answer
Dude I litterally understand the drawing explaination but when I get to the actual coding part, I have no clue on how to code even after watching this video, maybe I am just too dumb for coding :(
I was there, there’s a reason a degree takes 4 years. No one gets this stuff without thousands of hours of practice. If you’re not prepared to commit to that I wouldn’t bother, but if you are it can show you some of the coolest things you’ll ever see,
we can use our math knowledge, with combunations. *from math import comb* *class Solution:* *def generate(self, numRows: int) -> List[List[int]]:* *ans = []* *temp = [i for i in range(numRows)]* *for v in temp:* *i = 0* *temp1 = []* *while i
Negative indices count from the end of the list. So -1 refers to the last element, -2 to the second last, and so on. In this case, res[-1] gives you the last element of res, which is [1].
![ไปอยู่ไสมา - ช๊อปเปอร์ โตเกียวมิวสิค [ OFFICIAL MUSIC VIDEO ]](http://i.ytimg.com/vi/sWuVNbRTJbc/mqdefault.jpg)
![ออกพรรษาน้ำตาหล่น - แอน อรดี [OFFICIAL MV]](http://i.ytimg.com/vi/PFZtOcY9ONA/mqdefault.jpg)
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 =)
what if we already have a list ? like [1,2,1] and we want the next one ? what would be the solution ?
how is this question easy
Just is babe just is
Agreed, this took me like 1h to solve.
Was thinking the same fr 🤣
@@MrjavoiThejust one hour 🤯 broo
@@seenumadhavan4451I have been doing this from past 3 hrs
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??
this is a way of doing it and it works, I have this solution:
triangle = []
triangle.append([1])
if numRows == 1:
return triangle
triangle.append([1, 1])
if numRows == 2:
return triangle
for i in range(2, numRows):
curr_row = [1]
prev_row = triangle[-1]
for j in range(1, i):
curr_row.append(prev_row[j-1] + prev_row[j])
curr_row.append(1)
triangle.append(curr_row)
return triangle
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.
Your two-pointer hint made this easy. I was stuck on this for awhile
Super annoying problem
파스칼 삼각형의 각 행의 끝에 0을 넣는다는 아이디어는 인터넷 전체에서 이 분이 처음으로 내신 것 같은데, 정말 기발한 것 같아요. 다음에는 저 방식으로 스크립트를 짜 봐야겠다는 생각이 듭니다 감사합니다
I had solved this before watching the video. His solution is better, but, for the sake of seeing another solution, I thought I would post the solution I had come up with.
Python3
def generate(cls, num_rows: int) -> List[List[int]]:
if num_rows
wow
Nice
Here is my solution, time complexity is O(n^2), need to optimize
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
lst, finalLst = [0, 1, 0], [[1]]
for i in range(numRows - 1):
l, r = 0, 1
newLst = []
while(r < len(lst)):
element = lst[l] + lst[r]
newLst.append(element)
l = r
r = r + 1
finalLst.append(newLst)
newLst = [0]+newLst+[0]
lst = newLst
return finalLst
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
good idea, i like it!
@@NeetCode here's the code without worrying much *)
final_res = [ ]
for i in range(numRows):
res = [ ]
for j in range(i+1):
if j == 0 or j == i:
res.append(1)
else:
elem = final_res[i-1][j] + final_res[i-1][j-1]
res.append(elem)
final_res.append(res)
return final_res
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
im still not understanding how the code works :(
So appreciative of these videos.
I did this problem by myself, however i used binomial distribution. Thank you for your video and explication
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
you can remove your insert at the beginning this is O(n), you can just write l = [1]
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return []
elif numRows == 1:
return [[1]]
x = [[1], [1, 1]]
for i in range(2, numRows):
y = [1]
for j in range(1, len(x[i-1])):
y.append(x[i-1][j] + x[i-1][j-1])
y.append(1)
x.append(y)
return x
Another solution without adding zeros at the end
class Solution {
public:
vector generate(int numRows) {
vector v;
for(int i = 0;i
Correction maybe :
for i in range(1,numRows): #should be the first loop
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
what will be the code for numrows=o?
Sir can u please check this once...
I think this is a pretty clever approach..
Code :
result = []
for i in range(row):
s = []
for j in range(i + 1):
if j !=0 and j != i:
s.append(result[i-1][j] + result[i-1][j-1])
else:
s.append(1)
result.append(s)
return result
Please let me know !!
Yeah, it's good but it is the same O(n^2) space and time complexity
Yes, Your solution took 13.9 mb and his solution took 13.8 mb. It may seem insignificant for smaller inputs, but not for larger inputs. I think. Thanks for your sharing your solution.
in line 8 how was the range(len(res[-1]) + 1) deduced? can't wrap my head around it..
So basically, len(res[-1]) is used to get the length of the last row in the list cuz [-1] represents the last element . Since every new row in the pascal's triangle is 1 element longer we add 1 to len(res[-1]) to get the range.
I used for(let j=0;j
I was asked this question for a 5 thousands per month internship
😆😆👍
Bruh😂
🤣🤣🤣
5k rupies?
@@AlAnherProvat yes brother, but back then I wasn't aware that this problem is pascal triangle 😂😂
i just added a 1 at the start and at the end of each new row
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...
when you use res[-1] you are using another O(n) there , that is makes this O(n^3) solution. Instead , you can use i.
we can use len(temp)-1
Sorry, Actually res[-1] is not O(n) it is O(1) since we giving the index. Just realised. My bad!
@@thirunaavukkarasum4487 actually
Here's a breakdown:
[0]: This list creation has a time complexity of O(1) because it involves a single element.
res[-1]: This operation has a time complexity of O(1). It's a simple retrieval operation that gets the last element of res. If res[-1] itself is a list of length m, then creating a new copy of this list (which happens implicitly when we do list concatenation) will take O(m).
[0]: Same as the first operation, it's O(1).
+: The concatenation operation has time complexity O(n), where n is the length of the resulting list.
So overall you are right it is a O(n^3) solution
Absolutely stunning piece of code can i get a reference to Google or Amazon 😃
I Have added 1 at both ends and updated unfilled columns with two pointer solution
List result = new ArrayList(numRows);
if (numRows >= 1) {
result.add(Arrays.asList(1));
}
if (numRows >= 2) {
result.add(Arrays.asList(1, 1));
}
if (numRows > 2) {
for (int i = 3; i
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
outerArray = []
for i in range(1,numRows+1):
tempArray = [1]*i
for j in range(1,i-1):
tempArray[j] = outerArray[i - 2][j-1] + outerArray[i - 2][j]
outerArray.append(tempArray)
return outerArray
Is it good Solution
#My solution
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
answer = [[1], [1,1]]
if numRows == 1: return [answer[0]]
if numRows == 2: return answer
for i in range(numRows-2):
answer.append([1])
for i in range(2, len(answer)):
for j in range(1, i):
answer[i].append(answer[i - 1][j - 1] + answer[i - 1][j])
answer[i].append(1)
return answer
Dude I litterally understand the drawing explaination but when I get to the actual coding part, I have no clue on how to code even after watching this video, maybe I am just too dumb for coding :(
I was there, there’s a reason a degree takes 4 years. No one gets this stuff without thousands of hours of practice. If you’re not prepared to commit to that I wouldn’t bother, but if you are it can show you some of the coolest things you’ll ever see,
Brilliant explanation!
we can use our math knowledge, with combunations.
*from math import comb*
*class Solution:*
*def generate(self, numRows: int) -> List[List[int]]:*
*ans = []*
*temp = [i for i in range(numRows)]*
*for v in temp:*
*i = 0*
*temp1 = []*
*while i
In line 8:- we cannot concatenate int to list. I am not able to fix that
your + 1 is prob outside of a paren
nicely explained.
Hmm, I used the same solution :)
Idk how to thank you anyway sending luck your way✨🌻
Appreciate it :)
why have we took res[-1]?
Negative indices count from the end of the list. So -1 refers to the last element, -2 to the second last, and so on.
In this case, res[-1] gives you the last element of res, which is [1].
fuck, i guess im too stupid for that
No you’re not, it’s just your first time in the thunderdome.
I use dynamic programming and its faster
instead of looping through (len(res[-1]) + 1), can you loop through (len(temp) -1) instead?
we can bro
I do not understand the space complexity of O(numRows^2). If we ignore the output space wouldn’t the space complexity be O(1)
Yes if you do exclude the resultant array from the space complexity, you resulting complexity will be O(1)
it's completely impossible to be 0 (1) just saying,
How is this related to dynamic programming
This problem lends itself well to the application of dynamic programming techniques, but Neetcode didn't use any in his solution.
Solve Restore Binary Search Tree in O(1) space complexity solution. Thanks
Didn't work
me tooo
Use the formula binomial theorem, you can reply me if you want the code
Python is shit
If you are making video, atleast use an optimized way i.e DP with Recursion instead of showing ads with n2 solution
how the hell you come up with that solution, that is clever
this guy's brain works differently. cant believe how much "neater" his code comparing to mine 🥲😅