Perfect Squares - Dynamic Programming - Leetcode 279 - Python

0:00 - Read the problem
1:05 - Drawing Explanation
11:20 - Coding Explanation

leetcode 279

#perfect #squares #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[edwardteach]

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

[andreipoehlmann]

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

[JackJackson-hobv]

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

[sunnilabeouf]

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

[dmitrydmitriev]

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

[atharvakulkarni]

We can also do this using Unbounded Knapsack?

[albertgracelieu]

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

[name_surname_]

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

[rkalyankumar]

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

[sidhartheleswarapu]

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

[vincentwang]

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<=n:
y=n-i*i
if isPerfectSquare(y):
return 2
i+=1
return 3

[balaganesh]

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<3):
return n
result = [*range(0, n+1)]
end = int(n ** (1/2))
for i in range (2, end+1):
s = i**2
for j in range(s, n+1):
result[j] = min(result[j], 1+result[j-s])
#print(i, result)
return result[n]

Thanks Neetcode.

[studyaccount]

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<Integer> q = new LinkedList<>();
//add visited array so we don't go to values which we have traversed already (similar to dp)
HashSet<Integer> visited = new HashSet<>();
int ans = 0;
q.offer(n);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i<size; i++) {
int cur = q.poll();
if (cur == 0) return ans;
for (int j = 1; j<=cur/j; j++) {
if (!visited.contains(cur-j*j)) {
q.offer(cur-j*j);
visited.add(cur-j*j);
}
}
}
ans++;
}
return -1;
}
}

[numberonep]

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!

[kx]

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

[vivekgupta]

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

[adityagoyal]

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 <=n
if(maxCount==-1):
maxCount = count
else:
if(count<maxCount):
maxCount = count

dic[n] = maxCount+1
return maxCount+1

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

[ningzedai]

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.

[forresthu]

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<currentValue:
Q.put((currentValue-start*start, currentLevel+1))
start += 1
if currentValue == start * start:
return currentLevel +1