Straightforward Java BFS - beats 93.69%


  • 5
    Y
    public class Solution {
        public int numSquares(int n) {
    
            ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
            queue.add(n);
            int depth = 1, m = 1, tmp = 0;
            
            while(true){
                if(m == 0){
                    depth++;
                    m = tmp;
                    tmp = 0;
                }
                
                int cur = queue.remove();
                m--;
                
                int l = (int) Math.sqrt(cur);
                for(int i=l; i>0; i--){
                    int sq = i*i;
                    int delta = cur - sq;
                    if(delta == 0)
                        return depth;
                    queue.add(delta);
                    tmp++;
                }
            }
        }
    }

  • 0
    S

    Learnt from your solution. The key is the use of ArrayDeque, which stated by Java Docs that most of its operations take amortized constant time except for "remove" or "contains", have no capacity restrictions and faster than that implemented by LinkedList, which I tried and got MLE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.