Arranging Coins - Leetcode 441 - Python
Ғылым және технология
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 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
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/arrangi...
0:00 - Read the problem
1:10 - Drawing Explanation
9:58 - Coding Explanation
leetcode 441
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
Пікірлер: 65
I think a lot of people would love if you made a video on your process for solving a problem you haven't seen before. How long do you spend on a problem, what do you do when you get stuck, how much do you create your own solution vs read other solutions and digest them, etc. In one of your videos you said you're not some leetcode god, but you definitely come across that way, and I think seeing your process from start to finish would be really motivating!
@mearaftadewos8508
2 жыл бұрын
That would be nice. We can learn how to learn if we find a different way than ours.
@_7__716
2 жыл бұрын
Def
@Terracraft321
2 жыл бұрын
Clement
@YT.Nikolay
Жыл бұрын
Neet, we need such series, time to make an account on twitch
i did it in O(1) by using the formula i(i+1)//2= n of n natural numbers, then find out the one positive(real) root (by the fomula (-b+(underroot(-b+4ac))//2a) and return int(root)
Hey NeetCode, just wanted to say thank you! I received an offer to Google and couldn't be more excited. I watched your videos as a way to passively ingest some knowledge and it helped tremendously since the last time I was job hunting out of school. Cheers :)
@mearaftadewos8508
2 жыл бұрын
Hey Rei, Congrats my bro!! I have interviews at google and amazon paralley. Can you please recommend me some focus areas for google and pretty much everything you noticed and how you have prepared and for which level? Thanks in advance!
@reisturm9296
2 жыл бұрын
@@mearaftadewos8508 thanks! I wouldn't say there is a specific topic you should focus on. you can focus on your weak areas if you think you are not particularly good at a topic like DP etc. The stronger your fundamentals, the more ideas you can suggest to the interviewer and you can work with them to make your way to the solution. As your fundamentals grow, you will begin to recognize patterns and what DS/algo you can apply to the problem while working out minor details/edge cases. Good luck! Don't be down about leetcoding. It's easy to feel dumb when you cannot solve a problem. Spend some time on the problem, if you can't solve, then read the solution and try to understand it so you know why they approached it this way and take it forward.
@mearaftadewos8508
2 жыл бұрын
@@reisturm9296 Awesome. Thank you!
@oatmeal979
5 ай бұрын
@@mearaftadewos8508 bit late but how'd the interviews go?
Just wanna thank you man... Just got my offer all bc of YOU!
I feel smugly accomplished that my many years of math classes allowed me to almost instantly do (-1+ sqrt(1+8*n)))/2 rounded down solve this problem.
well you described very easily the formula for sum of first n natural numbers much more intuitively than my maths teacher... thanks much for all the work you put in these videos, helps a lot.
Thank you dear NeetCode. My fav channel.
Man i cant appriciate you enough!
Hey Neetcode, how much time do you spend coding practice in a day? Before job and now
Simply the Best! I have no words!
Very clear and great explanation thank you. you have the gift of teaching
in Line 13, res = mid will be enough, cuz the next possible mid will always be larger than res.
@durgaprasadreddypeddireddy8740
Жыл бұрын
yes, that is what I was thinking too.
Hey @NeetCode, I think the time complexity of the brute force soution should be sqrt(N) instead of O(n) since the loop is starting at 1 and will not go upto N. It will go upto Please do correct me if I am wrong. Thanks!
@yfjsdgzjdnfn
10 ай бұрын
Same thoughts
when you said u consider it as a medium level problem , I got relieved.
the formula you are talking about is sum of n natural numbers which is taught in class 5 but still I appreciate the way you use the formula in binary search ... Thanks for the Solution
The approach that came to my mind was this. Please test it and let me know if it has bugs for certain test inputs def buildstairs(tiles): row = 0 i = 1 while i row += 1 i += row print(i, row) return row if abs(tiles - i) == 0 else row - 1 print('stairs: ',buildstairs(9)) # from math import sqrt, floor # return floor(-.5 + sqrt(1+2*tiles)) # works too
you can solve it like this too: s=0 for i in range(1,n+1): s+=i if s>n: return i-1 return i
Thanks a lot for such a great and clear explanation! How is things going at Google?
Isn't the Tim complexity of the 1st method so log(n)?as we are exiting from the loop when the number of coins becomes negative
Is there a typo somewhere in this solution? I've been breaking it down, and comparing it with what I have typed up, but I keep getting a few failed test cases.
I think you don't need to use Gauss formula to solve this. You use a semi-square, so te elements until that value will be row*col/2 and because its not a Perfect semi-square you need to add the stair (row/2). So the formula to get the values is (row*2+col)/2. And with that you can binarny search
my issue with binary search problems is that for the while loop I never know whether to use l < r or l
@practicefirsttheorylater
Жыл бұрын
hi, i am not that good but this is how i think about it. take just n = 1, so our left = right = 1 when we start. so if we used condition l < r, we will never check the array. thus, we must use l
Hi, I really like ur problem solving approach. Can you please solve account merge problem
I originally tried doing this with prefix sum + binary search. I got memory limit exceeded, but it looked like i was kinda on the right approach
Hi neetcode here is a simple solution: return int(((0.25 + 2 * n) ** 0.5) - 1/2) Actually 1 + 2 + 3 + 4 ... n = n (n + 1) / 2 is a serie where n is equal to the last term of our serie and also represents the number of terms so all we need is just solve the equation n = i*(i + 1)/2
@frankribery3362
2 жыл бұрын
My thoughts exactly
@duanqichuzudefangwu
7 ай бұрын
was going to say: there is a direct analytical solution
O(1) algo comes to mind immediately including the rounding part ....
Return the positive root of the quadratic eqn: k(k+1)/2 = n return int(math.sqrt(1+8*n)-1)//2
@arjunreddy2647
2 жыл бұрын
W
There is no need to use max(). I try this solution and it works on leet code with over 1300 test case. the solution: class Solution: def arrangeCoins(self, n : int): start, end = 0, n while start n: end = mid-1 elif guess
A cleaner easy to understand solution, def arrangeCoins(self, n): """ :type n: int :rtype: int """ def getCoins(stairs): return(stairs*(stairs+1)/2) l=0 r=n ans=None while(l
This can also work : def arrangeCoins(self, n): """ :type n: int :rtype: int """ row = 0 i = 0 while n > 0: if n >= (i + 1): row += 1 n = n - (i + 1) i += 1 return row
n(n+1)/2 is summ of all natural numbers, which is nothing but AP, basic class 7 mathematics
nice
i saw there was an o(1) solution it was return (sqrt(8*n+1)-1)/2
@darkmatter2958
2 жыл бұрын
can you explain it how it was derived
I don't understand why you didn't implement the math solution? Breaking that quadratic equation would make it R = -1 + sqrt(1 + 4.2.n))/2 - > quadratic equation. Basically if we can write return (1 + int((1 + 8*n)**(1/2))/2) That would directly solve the problem. I think it says easy because it is school grade mathematics.
@mearaftadewos8508
2 жыл бұрын
I thougth of that tho.
@oreoshake6287
Жыл бұрын
Can you please explain how you derived the formula
Just wanted to let you know your code doesn't pass the test cases. Line 8 should be changed to mid*(mid+1)/2
Who has gone through school without learning gauss formula ? It is one of the very basic ones
Arithmatic Progression.
I can't believe they marked the "math" solution O(1)?! Has rigor gone completely out of algorithm analysis?!!! The algorithm for computing square roots is Newton's Method -- which amounts to the same bisection in the case of square roots!! And it has the same logarithmic runtime??
@NeetCode
Жыл бұрын
Yeah, I was wondering the same thing. It seems any "math" solution is marked O(1) but it's technically not the case.
U can calculate it in O(1) N = floor(-.5 + sqft(1+2n))
@JJKK-nj1vb
2 жыл бұрын
sqrt is logn
@rahulprasad2318
2 жыл бұрын
@@JJKK-nj1vb still it's more readable and maintainable.
@rppt
2 жыл бұрын
@@JJKK-nj1vb On the ARM Cortex M4, the assembly instruction VSQRT takes exactly 14 cycles for any 32 bit floating point. SQRT() being O(log-n) is only if you're assuming potentially arbitrarily large integers or arbitrarily precise floating points.
hard
How was this easy question then? I mean code is easy, but the thought process was not
just return right instead
Math formula is easier