Concise 3ms two-pointer c++ solution with O(1) space O(n) time


  • 1

    A DP solution typically takes O(n) space and O(n^1.5) time while a math solution can take O(1) space and O(n^0.5) time or even better. However you may not know or remember Legendre's three-square theorem.
    Here comes my solution. All you need to know is that 4 is always the maximum result. (I found this regularity by computing the first 20 numbers and a few bigger numbers.)

    • Result 1 is easy to check.
    • By using a two-pointer method, we are able to check for result 2 and 3.
    • Otherwise, we return 4.

    Time complexity is better than DP and practically faster. Also, no extra space is needed which is even better than DP.

    int numSquares(int n) {
        int sq = sqrt(n);
        if (sq * sq == n)
            return 1;
        for (int i = 0; i <= sq; i++) {
            int t = n - i * i;
            for (int l = i, r = sq; l <= r;) {
                int df = l * l + r * r - t;
                if (!df)
                    return i ? 3 : 2;
                df < 0 ? l++ : r--;
            }
        }
        return 4;
    }
    

  • 0

    Can you explain why this solution is O(n) time?


Log in to reply
 

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