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.

[@weaponkid1121]

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]

That would be nice. We can learn how to learn if we find a different way than ours.

[@_7__716]

Def

[@Terracraft321]

Clement

[@YT.Nikolay]

Neet, we need such series, time to make an account on twitch

[@shrimpo6416]

Just wanna thank you man... Just got my offer all bc of YOU!

[@user-bz9ve2ig5e]

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)

[@LiveType]

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.

[@reisturm9296]

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]

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]

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

@@reisturm9296 Awesome. Thank you!

[@oatmeal979]

@@mearaftadewos8508 bit late but how'd the interviews go?

[@mearaftadewos8508]

Thank you dear NeetCode. My fav channel.

[@vgsuresh]

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.

[@akhma102]

Simply the Best! I have no words!

[@mohamedhesham6008]

Very clear and great explanation thank you. you have the gift of teaching

[@cc-to2jn]

Man i cant appriciate you enough!

[@augustshen8018]

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.

[@ayoubalem865]

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]

My thoughts exactly

[@duanqichuzudefangwu]

was going to say: there is a direct analytical solution

[@baap6886]

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

[@mearaftadewos8508]

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

[@abhinowyt8564]

Hey Neetcode, how much time do you spend coding practice in a day? Before job and now

[@ilihaspatel399]

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

[@sankhadip_roy]

when you said u consider it as a medium level problem , I got relieved.

[@pabloarkadiuszkalemba7415]

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

[@Chirayu19]

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]

Same thoughts

[@sushantrocks]

Return the positive root of the quadratic eqn: k(k+1)/2 = n return int(math.sqrt(1+8*n)-1)//2

[@arjunreddy2647]

W

[@ChandraShekhar-by3cd]

Thanks a lot for such a great and clear explanation! How is things going at Google?

[@indonline]

O(1) algo comes to mind immediately including the rounding part ....

[@rupambasu9722]

Hi, I really like ur problem solving approach. Can you please solve account merge problem

[@Y1Rayn]

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

[@harshavardhanveerannanaval8605]

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

[@He_ze]

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

[@maamounhajnajeeb209]

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

[@oreoshake6287]

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

[@poonamgulwane6734]

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

[@call_me_lazarus]

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.

[@MrArpit1234]

n(n+1)/2 is summ of all natural numbers, which is nothing but AP, basic class 7 mathematics

[@darkmatter2958]

i saw there was an o(1) solution it was return (sqrt(8*n+1)-1)/2

[@darkmatter2958]

can you explain it how it was derived

[@pojunechen2617]

Just wanted to let you know your code doesn't pass the test cases. Line 8 should be changed to mid*(mid+1)/2

[@rahulprasad2318]

U can calculate it in O(1) N = floor(-.5 + sqft(1+2n))

[@JJKK-nj1vb]

sqrt is logn

[@rahulprasad2318]

@@JJKK-nj1vb still it's more readable and maintainable.

[@rppt]

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

[@santysayantan]

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]

I thougth of that tho.

[@oreoshake6287]

Can you please explain how you derived the formula

[@aabhishek4911]

Who has gone through school without learning gauss formula ? It is one of the very basic ones

[@masternobody1896]

nice

[@vadimkokielov2173]

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.

[@pradiptasarma4867]

Arithmatic Progression.

[@prabhatracherla3098]

How was this easy question then? I mean code is easy, but the thought process was not

[@thangnguyenduc9969]

just return right instead

[@flatmapper]

hard

[@HarvinderSandhuEsq]

Math formula is easier