Pascal's Triangle - Leetcode 118 - Python

Подписаться 778 тыс.

Просмотров 88 тыс.

50% 1

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/pascals...
0:00 - Read the problem
1:40 - Drawing Explanation
5:55 - Coding Explanation
leetcode 118
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#pascals #triangle #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

Наука

Опубликовано:

4 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 85

@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 =)

@ferroumsamir6531 Год назад

what if we already have a list ? like [1,2,1] and we want the next one ? what would be the solution ?

@msyugandhar3377 2 года назад

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??

@thebigpart783 2 месяца назад

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

@dimakavetskyy2082 2 года назад

how is this question easy

@sriramkrishnamurthy4473 Год назад

Just is babe just is

@MrjavoiThe Год назад

Agreed, this took me like 1h to solve.

@akagamishanks7991 Год назад

Was thinking the same fr 🤣

@seenumadhavan4451 10 месяцев назад

@@MrjavoiThejust one hour 🤯 broo

@seit-55omvikhe50 4 месяца назад

@@seenumadhavan4451I have been doing this from past 3 hrs

@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.

@Melvinn27 2 года назад

So appreciative of these videos.

@putin_navsegda6487 11 месяцев назад

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

@Moch117 11 месяцев назад

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

@jianchoi7434 2 года назад

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

@josephjacob9883 2 года назад

nicely explained.

@hsoley 2 года назад

Brilliant explanation!

@thedropshipper96 Год назад

what will be the code for numrows=o?

@edwardteach2 3 года назад

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 3 года назад

good idea, i like it!

@chandank5266 9 месяцев назад

@@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

@vishnusunil9610 9 месяцев назад

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

@fazlerabbi2666 2 года назад

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

@akshatshukla143 2 года назад

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.

@kanyestan 2 года назад

I used for(let j=0;j

@aishwaryadeep8815 Год назад

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

@danielsun716 Год назад

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

@ericnarciso4701 3 года назад

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

@adt2311 3 года назад

wow

@reisjpug 2 года назад

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

@bobbobby3056 Год назад

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...

@memeproductions4182 2 года назад

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

@AryanKumar-cm2iq Год назад

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

@thebigpart783 2 месяца назад

you can remove your insert at the beginning this is O(n), you can just write l = [1]

@Progamer-fq8st Год назад

Another solution without adding zeros at the end class Solution { public: vector generate(int numRows) { vector v; for(int i = 0;i

@janvidalal476 2 года назад

Idk how to thank you anyway sending luck your way✨🌻

@NeetCode 2 года назад

Appreciate it :)

@JashSingh-bv5ge 6 месяцев назад

im still not understanding how the code works :(

@amitozazad1584 7 месяцев назад

Hmm, I used the same solution :)

@jamiearodi7325 2 года назад

instead of looping through (len(res[-1]) + 1), can you loop through (len(temp) -1) instead?

@shashankl8589 2 года назад

we can bro

@thirunaavukkarasum4487 2 года назад

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.

@shashankl8589 2 года назад

we can use len(temp)-1

@thirunaavukkarasum4487 2 года назад

Sorry, Actually res[-1] is not O(n) it is O(1) since we giving the index. Just realised. My bad!

@Rajmanov Год назад

@@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

@fareedahshaik1519 Год назад

why have we took res[-1]?

@nomaankhan6498 7 дней назад

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].

@challangour5557 18 дней назад

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

@chamikaonyt Год назад

#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

@theelitecoder5981 Год назад

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 !!

@huzaifanaseerkhan Год назад

Yeah, it's good but it is the same O(n^2) space and time complexity

@unpluggedalphaa Год назад

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.

@anupriya5535 Год назад

In line 8:- we cannot concatenate int to list. I am not able to fix that

@StfuSiriusly Год назад

your + 1 is prob outside of a paren

@littlecosmonaut 2 года назад

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

@soumikghosh1522 3 года назад

Solve Restore Binary Search Tree in O(1) space complexity solution. Thanks

@PriyanshuRaj-bx6to 4 месяца назад

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

@nightcrusader5047 3 года назад

I was asked this question for a 5 thousands per month internship

@harshvardhanranvirsingh9473 3 года назад

😆😆👍

@tanujkhochare3498 3 года назад

Bruh😂

@jayanthk9632 3 года назад

🤣🤣🤣

@AlAnherProvat 3 года назад

5k rupies?

@nightcrusader5047 2 года назад

@@AlAnherProvat yes brother, but back then I wasn't aware that this problem is pascal triangle 😂😂

@burburchacha Год назад

I use dynamic programming and its faster

@Z4746x 2 года назад

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)

@kyayaarbankey 2 года назад

Yes if you do exclude the resultant array from the space complexity, you resulting complexity will be O(1)

@Rajmanov Год назад

it's completely impossible to be 0 (1) just saying,

@prathamkesarkar 2 года назад

How is this related to dynamic programming

@neslzkusfep Год назад

This problem lends itself well to the application of dynamic programming techniques, but Neetcode didn't use any in his solution.

@rafx 5 месяцев назад

fuck, i guess im too stupid for that

@DanielPratt-bj9ly 18 дней назад

No you’re not, it’s just your first time in the thunderdome.

@CyrusWong-yq4uw 6 месяцев назад

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 :(

@DanielPratt-bj9ly 18 дней назад

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,

@adt2311 3 года назад

Didn't work

@lildawg1685 2 года назад

me tooo

@thetwogoats6851 Год назад

Use the formula binomial theorem, you can reply me if you want the code

@Sandeep-yw2rb 2 года назад

If you are making video, atleast use an optimized way i.e DP with Recursion instead of showing ads with n2 solution

@user-yj5qw8pd3p Месяц назад

Python is shit

@sureshbabuk5241 11 месяцев назад

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