2 intuitive JAVA Solution. O(n) space


  • 0
    Z

    Solution 1: this is a very simple way of thinking. If we want to know n, then we check 1 + (n - 1), 2 + (n - 2).....

    public int numSquares(int n) {
            // use dp idea
            // m[i] represent the least number of perfect square numbers
            // base case m[1] = 1;
            // induction rule: if m[i] is square of some number, m[i] = 1;
            // otherwise m[i] = min(m[1] + m[i - 1], m[2] + m[i - 2])
            // use a hashset to store all square number
            // space complexity is O(n)
            // time complexity is O(n)
            int[] m = new int[n + 1];
            m[1] = 1;
            Set<Integer> square = new HashSet<Integer>();
            int i = 1;
            while (i * i <= n) {
                square.add(i * i);
                i++;
            }
            for (i = 2; i <= n; i++) {
                if (square.contains(i)) {
                    m[i] = 1;
                    continue;
                }
                int min = Integer.MAX_VALUE;
                for (int j = 1; j <= i / 2; j++) {
                    min = Math.min(min, m[j] + m[i - j]);
                }
                m[i] = min;
            }
            return m[n];
        }
    

    Solution2: further thinking: we can check history more efficiency. We want to know n, then we check n - 1, n - 4, n - 9.....
    So the time complexity will be O(sqrt(n)), instead of solution 1 O(n)

    public int numSquares(int n) {
            // use dp idea
            // m[i] represent the least number of perfect square numbers
            // base case m[1] = 1;
            // induction rule: if m[i] is square of some number, m[i] = 1;
            // otherwise m[i] = min(1 + m[i - 1], 4 + m[i - 4])
            // use a hashset to store all square number
            // space complexity is O(n)
            // time complexity is O(n)
            
            // sanity check
            int[] m = new int[n + 1];
            m[1] = 1;
            Set<Integer> square = new HashSet<Integer>();
            int i = 1;
            while (i * i <= n) {
                square.add(i * i);
                i++;
            }
            for (i = 2; i <= n; i++) {
                if (square.contains(i)) {
                    m[i] = 1;
                    continue;
                }
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j < i; j++) {
                    min = Math.min(min, m[i - j * j] + 1);
                }
                m[i] = min;
            }
            return m[n];
        }
    

Log in to reply
 

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