Least number of perfect square numbers that sums upto n

You can simplify your solution to:

def numSquares(self,n):    if(n == 0):        return 0    if(n == 1):        return 1    squares = self.findSquares(n)    rows = len(squares)    cols = n + 1    mat = [n] * cols    mat[0] = 0    for s in squares:        for j in range(s,cols):            mat[j] = min(mat[j], 1 + mat[j - s])    return mat[n]

This avoids using:

1. the self.min function
2. the division/modulus operation in the inner loop.
3. the 2d array

and is about twice as fast.

A bit late, but I believe this answer can help others as it did me. This below is the fastest solution possible with O(sqrt(n)) time complexity

It is based on Lagrange’s four-square theorem every natural number can be represented as the sum of four integer squares. So the answer set would be 1, 2, 3 or 4.

class Solution:    def is_perfect(self, n):        x = int(math.sqrt(n))        return x * x == n    def numSquares(self, n: int) -> int:        if n < 4:            return n        if self.is_perfect(n):  # number is a perfect square            return 1        # the result is 4 if number = 4^k*(8*m + 7)        while n & 3 == 0:  # while divisible by 4            n >>= 2        if n & 7 == 7:  # 8m+7 => last 3 digits = 111            return 4        x = int(math.sqrt(n))        for i in range(1, x + 1):  # sum of 2 perfect squares            if self.is_perfect(n - i * i):                return 2        return 3  # by elimination