Queue Deque Simulation
Intermediate Level

Implement the perfectSquaresBfsSteps method that returns the minimum number of perfect squares that sum to n.

The input contains a positive integer n. Your task is to return the minimum number of perfect square numbers whose sum is equal to n.

A perfect square is a number like 1, 4, 9, 16, and so on.

For example, 12 can be written as 4 + 4 + 4, so the answer is 3. The number 13 can be written as 4 + 9, so the answer is 2.

Example 1
Input:
n (int) = 12
Return:
(int) 3
Example 2
Input:
n (int) = 13
Return:
(int) 2
Example 3
Input:
n (int) = 1
Return:
(int) 1

Use BFS where each state represents a remaining sum.

Start from n. From the current value, subtract every perfect square that is less than or equal to it. Each BFS level means one more square has been used.

The first time the remaining value becomes 0, the current BFS level is the minimum number of squares required.

Pseudocode:

function perfectSquaresBfsSteps(n):
    squares = all perfect squares less than or equal to n
    queue = empty queue
    visited = empty set
    push n into queue
    add n to visited
    steps = 0
    while queue is not empty:
        steps++
        process all values currently in queue
        for each value processed:
            for each square in squares:
                next = value - square
                if next == 0:
                    return steps
                if next > 0 and next is not visited:
                    add next to visited
                    push next into queue
    return steps
Run your code to see the result.