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

• 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;
}
``````

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

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