BFS solution in Java


  • 0

    I couldn't find any BFS solution in Java, so here you go.
    Main idea: The number of levels BFS traverses in the graph to reach n, is the solution.

    class Solution {
        public int numSquares(int n) {        
          //A regular queue
           Queue<Integer> queue = new LinkedList<Integer>();
            queue.offer(0);
            int levels = 0;
            while(!queue.isEmpty()){
                int size = queue.size();
             // This loop helps us keep track of levels
                while(size-- > 0){
                    int x = queue.poll();
              // push only those values which do not exceed n                          
                    for(int i=n; i>0; i--){
                           if  ((x + i*i) == n)   return levels + 1;
                           else if((x + i*i) < n)    queue.offer(x+i*i);                        
                    }
                }
                levels ++;               
            }
            return levels;  
        }     
    }
        
    

  • 0

    I think you could add two condition check before x+ii == n to save some time;
    one is x+i
    i > n the other is visited check manage to speed up the run time from 1xxx to 405;

     if (x+i*i > n || visited[x+i*i]){
          continue;
      }

Log in to reply
 

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