0279-perfect-squares.java

//This is a BFS based approach.
//We can also do this problem similar to coin change but the Time and space complexity will remain same (Just an extra queue in this one stil linear space).

classSolution {

publicintnumSquares(intn) {
Queue<Integer> q = newLinkedList<>();
//add visited array so we don't go to values which we have traversed already (similar to dp) otherwise this will give tle
HashSet<Integer> visited = newHashSet<>();
intans = 0;
q.offer(n);
while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
intcur = q.poll();
if (cur == 0) returnans;
for (intj = 1; j <= cur / j; j++) {
if (!visited.contains(cur - j * j)) {
q.offer(cur - j * j);
visited.add(cur - j * j);
 }
 }
 }
ans++;
 }
return -1;
 }
}