class Solution {
    public int numSquares(int n) {
        /*
        1 2 3 4 5 6 ...
        1 4 9 16 25 36 ...
        
        n = 13
        1 4 9
        
        3
        */
        
        int sqr = (int)Math.sqrt(n); // n = 25, sqrt = 5
        List<Integer> perfectSquares = new ArrayList();
        for (int i = 1; i <= sqr; i++) {
            perfectSquares.add(i * i);
        }
        // System.out.println(perfectSquares);
        // Integer[] memo = new Integer[n + 1];
        // return findMinSquares(n, perfectSquares, memo);
        
        Queue<Integer> queue = new LinkedList();
        queue.add(n);
        boolean[] visited = new boolean[n + 1];
        int level = 0;
        while (queue.size() > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int num = queue.poll();
                if (num == 0) return level;
                for (int sqrt : perfectSquares) {
                    if (sqrt > num) 
                        break;
                    if (visited[num - sqrt] == false) {
                        visited[num - sqrt] = true;
                        queue.add(num - sqrt);
                    }
                }
            }
            level++;
        }
        // unreachable statement
        return -1;
    }
    
    private int findMinSquares(int n, List<Integer> perfectSquares, Integer[] memo) {
        if (n == 0) return 0;
        if (memo[n] != null) return memo[n];
        int min = Integer.MAX_VALUE - 1;
        for (int sqr : perfectSquares) {
            if (sqr > n)
                break;
            min = Math.min(min, 1 + findMinSquares(n - sqr, perfectSquares, memo));
        }
        memo[n] = min;
        return min;
    }
}