6 ms Java Solution


  • 0
    M
    
    public class Solution {
        public static int[] memo;
    
        public int numSquares(int n) {
            if(memo == null){
                memo = new int[(n * 2) + 1];
            }
            else if(memo.length <= n){
                int[] temp = new int[n * 2];
                for(int i = 0; i < memo.length; i++){
                    temp[i] = memo[i];
                }
                memo = temp;
            }
            return leastNumSquares(n);
        }
        
        
        private int leastNumSquares(int n){
            if(memo[n] > 0){
                return memo[n];
            }
            if(n == 0){
                return 0;
            }
            
            double root = Math.sqrt(n);
            root = Math.floor(root);
            int r = (int)root, min = Integer.MAX_VALUE;
            
            while(r > 0){
                int squares = leastNumSquares(n - (r*r)) + 1;
                min = squares < min ? squares : min; 
                r--;
            }
            memo[n] = min;
            return min;
            
        }
    }
    
    

    This solution uses memoization and a form of amortized doubling on the memoization array. I could probably combine the private method with the given method, but I am alright with the way it turned out.


Log in to reply
 

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