Perfect Squares - Dynamic Programming - Leetcode 279 - Python

[@edwardteach2]

I ended up getting a time limit exceeded for the input: 3288

[@hoyinli7462]

same here

[@NeetCode]

Hey thanks for bringing it to my attention. I think this is just leetcode being dumb... I replaced the line where i call the min() function with an if-statement and it passed on leetcode. This is the code i used: class Solution: def numSquares(self, n: int) -> int: cache = [n] * (n + 1) cache[0] = 0 for i in range(1, n + 1): for s in range(1, i + 1): square = s * s if i - square < 0: break if 1 + cache[i - square] < cache[i]: cache[i] = 1 + cache[i - square] return cache[n]

[@aparnaaketi1616]

@@NeetCode I got time limit exceeded for input 8405 even after using the if statement

[@王雅璇-b7y]

@@aparnaaketi1616 same to me

[@michaelscotto4009]

The reason getting time limit exceeded is that we need to loop through perfect squares in the inner loop only. Add this at the top and use for inner loop: squares = [x**2 for x in range(0, n) if x**2

[@andreipoehlmann913]

It still blows mind to see such simple bottom-up DP implementations. Even though I've been practicing for weeks.

[@JackJackson-ho5bv]

Thanks for the video! It's so much better than all the other videos explaining this problem that I've seen so far on KZbin.

[@NeetCode]

💡 DP Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@dmitrydmitriev2554]

dp = [n] * (n+1) - nice move to fill dp array with maximum values. Thank you!

[@sunnilabeouf]

goated, your videos along with alvin's dynamic programming course have made dp problems soooo much easier for me

[@programming1734]

Alvin? Can you share the playlist or channel

[@sunnilabeouf]

@@programming1734 heres the video! kzbin.info/www/bejne/pXPXZmaPl7dsgc0 it starts off really simple and works up how to come up with a recursive brute force algo, then memoize it and turn it into a dp solution

[@programming1734]

Thank you @abdulrahman Tolba

[@balaganesh5484]

No time limit exceeded. Same concept: instead of checking minimal of target with all availble squares, here reaching to n with minimum squares with 1 after another. def numSquares(self, n: int) -> int: if(n

[@vincentwang5887]

Fan here. We can also utilize Lagrange's four-square theorem to solve this question. class Solution: def numSquares(self, n: int) -> int: def isPerfectSquare(x): y=int(x**0.5) return y*y==x def isFourSqaure(x): while x%4 == 0: x/=4 return x%8==7 if isPerfectSquare(n): return 1 if isFourSqaure(n): return 4 i = 1 while i*i

[@kxf8608]

This is absolutly savage!

[@albertgracelieu1506]

@NeetCode Interestingly enough, this DP method is even slower than brute force and leads to TLE. Did I get anything wrong here? Have you encountered TLE when submitting this answer?

[@333jjjjjj]

I did not watch the whole video; the only hint I needed was the similarity to coin change (though I'm facepalming for not recognizing it on my own.) I coded a bottom-up DP solution that easily ran within the time limit. Edit: I watched it and the only real difference is that i computed the set of squares i needed as an array once at the beginning.

[@zishiwu7757]

Not this answer, but when I pre-computed all the squares that are less than n, and iterated those in the inner for loop, I got TLE. Then I tried NeetCode’s solution in the video and got runtime of ~6900ms or faster than 13% of Python3 solutions. Then I tried NeetCode’s solution but using C++ and runtime shrank to 257ms which is faster than 42% of C++ solutions. I wonder if for this problem, LeetCode’s time limit is more harsh for Python3 than for C++. But I don’t think you should worry about what LeetCode says. If you can ask clarifying questions, propose and explain a correct solution clearly to the interviewer, and implement it - well that’s what really counts on the interview.

[@vivekgupta707]

Thanks for the video !!! Really helped to understand the recurrence relation

[@atharvakulkarni3007]

We can also do this using Unbounded Knapsack?

[@sidhartheleswarapu]

For all DP problems, should I always start with a decision tree in order to know how to approach it?

[@name_surname_1337]

precomputation is 20 times (real number) faster. The js runtime estimation is very random, but anyway, this solution is very slow. It's much faster to calculate all squares in advance

[@studyaccount794]

There's also a bfs based approach to this problem. I think the TC will be the same. Only one extra queue is required. Still the space complexity will be O(n) ig. class Solution { public int numSquares(int n) { Queue q = new LinkedList(); //add visited array so we don't go to values which we have traversed already (similar to dp) HashSet visited = new HashSet(); int ans = 0; q.offer(n); while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i

[@rkalyankumar]

This can also be solved using BFS. Can you please do a video of this problem solving using BFS?

[@numberonep5404]

As is, this code is O(n^2), it lacks the square root, but otherwise nice video :) ! I love your thumnails btw they really make the videos enticing and easy to click at imo!

[@zishiwu7757]

Why do you think NeetCode’s solution is O(n^2)? In the inner loop, it breaks as soon as we get a square > target. So we never evaluate more than sqrt(target) number of squares, which is bounded by sqrt(n), in each iteration of the inner loop. So I think NeetCode is correct saying his solution is O(n*sqrt(n)).

[@numberonep5404]

@@zishiwu7757 my baaad ! you are right indeed definitely O(n*sqrt(n))

[@adityagoyal9556]

def numSquares(self, n): return self.num(n,{}) def num(self, n,dic): if(n in dic): return dic[n] arr = [] frequency = int(math.sqrt(n)) for i in range(frequency): i+=1 arr.append(i) maxCount = -1 for i in arr: count = self.num(n-(i*i),dic) # the argument is >=0 since i*i

[@kx01]

This is similar to coin change problem. in coins we will have 1,4,9,... sqrt(n). amount will be n;

[@varunshrivastava2706]

Sort of

[@souparnomajumder]

This code will give TLE, as -> for s in range(1, target +1) will get the loop to run 1 extra time, to hit the condition if s*s > target: break, ex: if target is 5, the loop will run for 1, 2, 3 and then break, changing the loop to -> for s in range(1, int(sqrt(target)) + 1): will pass all the tests, as the 2nd loop for a target of 5 will run only for [1, 2]

[@forresthu6204]

import queue class Solution: def numSquares(self, n: int) -> int: # Breadth first search for solution, timed out at input 7168 Q=queue.Queue() Q.put((n,0)) while Q: currentValue, currentLevel = Q.get() start =1 while start*start

[@Kaviarasu_NS]

I just came across this below solution Perfect Squares on leetcode, can you teach us how its solved using deque class Solution: def numSquares(self, n: int) -> int: queue = deque([n]) ans = 0 while queue: ans +=1 for _ in range(len(queue)): cur = queue.popleft() j = 1 while cur-j*j >= 0: if not cur-j*j: return ans queue.append(cur-j*j) j+=1 return ans

[@ningzedai9052]

This is graph problem that looking for the shortest path by BFS. If you think it in this way, it will become an very easy problem.

[@smonkey001]

Best explanation on KZbin you rock sir!

[@lettry5297]

Hi., thanks for making this video Can you please cover this problem - Shortest subarray with sum atleast k (leetcode-862)

[@CS_n00b]

so basically coin change?

[@veliea5160]

dp[target]=min(dp[target],1+dp[target-square]) Can somebody please explain this. I did not understant :(

[@artemchaika]

we want to store the minimum amount of squares required to get to dp[target], let's say it's 7, so we iterate up to 7, for example we take 1, and see if 7 - 1*1 >= 0, so it's 6, and we want to check if the amount of squares required to get to 6 + 1 (cause we already substracted one square 1*1) is less then the previous amount we stored for 7. So as a result we will have the minimum to get to 7 stored there, which can be used by the following bigger values, the same way we used the minimum for 6, which was stored before etc.

[@veliea5160]

@@artemchaika we are calculating `dp[target` which is unknown yet. How come this equation work: `dp[target]=min(dp[target],1+dp[target-square])`. on the right side we still have `dp[target`

[@sabrish7263]

Hi, is it more like the coin change problem ?

[@sachinchhipa6222]

Go for more inf.,below link kzbin.info/www/bejne/gpqXlmaGg9t0r7c

[@aaroldaaroldson708]

as usual seems like an easy tutorial, but I didn’t get s*it

[@MHDNOUR-i4f]

is this way called backtracking

[@almaguerrero3041]

esta bien perro alv

[@hoyinli7462]

but your ans doesn't pass all the test cases

[@NeetCode]

Thanks for bringing it to my attention. Please see the pinned comment and let me know if it passes.

[@Eggleweb97]

it passed all test cases,check again