Commit9ac845e

authored

Create 279-Perfect-Squares.java

1 parent17eb20b commit9ac845eCopy full SHA for 9ac845e

File tree

+27

-0

lines changed

+27

-0

lines changed

Lines changed: 27 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,27 @@`
	`1`	`+//This is a BFS based approach.`
	`2`	`+//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).`
	`3`	`+`
	`4`	`+classSolution {`
	`5`	`+publicintnumSquares(intn) {`
	`6`	`+Queue<Integer>q =newLinkedList<>();`
	`7`	`+//add visited array so we don't go to values which we have traversed already (similar to dp) otherwise this will give tle`
	`8`	`+HashSet<Integer>visited =newHashSet<>();`
	`9`	`+intans =0;`
	`10`	`+q.offer(n);`
	`11`	`+while (!q.isEmpty()) {`
	`12`	`+intsize =q.size();`
	`13`	`+for (inti =0;i<size;i++) {`
	`14`	`+intcur =q.poll();`
	`15`	`+if (cur ==0)returnans;`
	`16`	`+for (intj =1;j<=cur/j;j++) {`
	`17`	`+if (!visited.contains(cur-j*j)) {`
	`18`	`+q.offer(cur-j*j);`
	`19`	`+visited.add(cur-j*j);`
	`20`	`+ }`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+ans++;`
	`24`	`+ }`
	`25`	`+return -1;`
	`26`	`+ }`
	`27`	`+}`

Comments

(0)