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]
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
@@programming1734 heres the video! ruclips.net/video/oBt53YbR9Kk/видео.html 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
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
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
@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?
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.
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.
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
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
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!
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)).
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]
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
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
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
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.
@@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`
I ended up getting a time limit exceeded for the input: 3288
same here
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]
@@NeetCode I got time limit exceeded for input 8405 even after using the if statement
@@aparnaaketi1616 same to me
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
It still blows mind to see such simple bottom-up DP implementations. Even though I've been practicing for weeks.
Thanks for the video! It's so much better than all the other videos explaining this problem that I've seen so far on RUclips.
💡 DP Playlist: ruclips.net/video/73r3KWiEvyk/видео.html
dp = [n] * (n+1) - nice move to fill dp array with maximum values. Thank you!
goated, your videos along with alvin's dynamic programming course have made dp problems soooo much easier for me
Alvin? Can you share the playlist or channel
@@programming1734 heres the video! ruclips.net/video/oBt53YbR9Kk/видео.html 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
Thank you @abdulrahman Tolba
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
This is absolutly savage!
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
@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?
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.
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.
For all DP problems, should I always start with a decision tree in order to know how to approach it?
We can also do this using Unbounded Knapsack?
Thanks for the video !!! Really helped to understand the recurrence relation
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
This can also be solved using BFS. Can you please do a video of this problem solving using BFS?
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
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!
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)).
@@zishiwu7757 my baaad ! you are right indeed definitely O(n*sqrt(n))
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]
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
This is similar to coin change problem. in coins we will have 1,4,9,... sqrt(n). amount will be n;
Sort of
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
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
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.
Best explanation on RUclips you rock sir!
Hi., thanks for making this video
Can you please cover this problem - Shortest subarray with sum atleast k (leetcode-862)
so basically coin change?
dp[target]=min(dp[target],1+dp[target-square])
Can somebody please explain this. I did not understant :(
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.
@@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`
Hi, is it more like the coin change problem ?
Go for more inf.,below link
ruclips.net/video/Li4e3PNvAyU/видео.html
as usual seems like an easy tutorial, but I didn’t get s*it
esta bien perro alv
is this way called backtracking
but your ans doesn't pass all the test cases
Thanks for bringing it to my attention. Please see the pinned comment and let me know if it passes.
it passed all test cases,check again