10
\$\begingroup\$

I'm trying to solve this problem

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

I've come up with a solution that works correctly but times out on large inputs:

from collections import defaultdict
class Solution:
 def numSquares(self, n: int) -> int:
 coins = []
 for i in range(1, n+1):
 if i**2>n:
 break 
 coins.append(i**2)
 min_coins_to_make = defaultdict(lambda :float("inf"))
 min_coins_to_make[0] = 0 
 for coin in coins:
 if coin > n:
 break 
 for target in range(coin, n+1):
 min_coins_to_make[target] = min(min_coins_to_make[target], 1+min_coins_to_make[target-coin])
 if min_coins_to_make[target] == float("inf"):
 return 0 
 return min_coins_to_make[target]

How do I optimize it in terms of time and space complexity?

https://leetcode.com/problems/perfect-squares/

Martin R
24.2k2 gold badges37 silver badges95 bronze badges
asked Sep 28, 2019 at 16:01
\$\endgroup\$
0

5 Answers 5

7
\$\begingroup\$

I won't specifically address the execution time concerns to begin with; there are other issues:

Don't use a class

There's no reason for this to be a class. You have one method and you don't even reference self. In theory you could remove self and mark it a @staticmethod, but really it should just be a function without a class.

Reuse variables

Make this variable -

i2 = i**2

since it's used twice. The same goes for min_coins_to_make[target].

Loop limit

 for coin in coins:
 if coin > n:
 break 

That termination condition will be true if coin > n, but coin == i**2. i**2 > n will never be true, because in the previous loop,

 if i**2>n:
 break 

So can't you just write for coin in coins without an interior termination condition?

answered Sep 28, 2019 at 17:33
\$\endgroup\$
3
  • 3
    \$\begingroup\$ You are of course right about the class and instance method. Just note that this is given in the problem submission template on leetcode.com/problems/perfect-squares. \$\endgroup\$ Commented Sep 28, 2019 at 17:54
  • 2
    \$\begingroup\$ Ah true - that's a silly template. \$\endgroup\$ Commented Sep 28, 2019 at 17:56
  • 1
    \$\begingroup\$ I agree with Reinderien: codereview.meta.stackexchange.com/questions/9345/… \$\endgroup\$ Commented Sep 28, 2019 at 17:56
6
\$\begingroup\$

Here

if min_coins_to_make[target] == float("inf"):
 return 0 
return min_coins_to_make[target]

you use the fact that target has the last value from a preceding (nested) loop, and that happens to be n. It would be more clear to use n directly instead:

if min_coins_to_make[n] == float("inf"):
 return 0 
return min_coins_to_make[n]

Then note that the if-condition can never be true, so that you can remove that test: Every positive integer \$ n \$ can be written as $$ n = \underbrace{1 + 1 + \ldots + 1}_{n \text{ terms}} $$ which makes it a sum of \$ n \$ perfect squares. (Actually every positive integer can be written as the sum of at most four squares according to Lagrange's four-square theorem.)

This

coins = []
for i in range(1, n+1):
 if i**2>n:
 break 
 coins.append(i**2)

can be written as a list comprehension:

coins = [i * i for i in range(1, int(math.sqrt(n)) + 1)]
answered Sep 28, 2019 at 20:45
\$\endgroup\$
3
  • \$\begingroup\$ what are the gains in time/space complexity with these suggestions? \$\endgroup\$ Commented Sep 29, 2019 at 14:54
  • \$\begingroup\$ I made suggestions to remove unneeded code, to make it better understandable, and to use idiomatic Python. – The policy on this site is that an answer can review any aspect of the posted code, not only the topics the OP is concerned about. \$\endgroup\$ Commented Sep 29, 2019 at 15:58
  • 1
    \$\begingroup\$ Nice mentioning the theorem. It's a good option to speed things up. \$\endgroup\$ Commented Sep 29, 2019 at 18:58
3
\$\begingroup\$

You can remove the coins variable altogether and replace it with a generator of squares:

for coin in (x**2 for x in itertools.count(1)):
 ...

You don't necessarily need a defaultdict with a lambda, since you are going to create the all the values in the dict anyway (defaultdict is more appropriate if you don't know in advance what keys you'll need):

min_coins_to_make = {i: i for i in range(n)}

(which takes care of the square of 1, too, so you can start your count at 2, realistically)

In terms of space and complexity, space is O(N), complexity is O(N*Log(N)) (it's actually a Harmonic number (sum(1/i for i < n)), but it converges to ln(N)). I don't see a better option right now.

One other way to look at the problem could be to go backward from large squares, that way you can stop when the square you're looking at is smaller that N/current best (as you'd have to replace a bigger element, hence increasing the total count.) or when you somehow know that the current solution is optimal. I don't know exactly how you'd go about this approach, though.

answered Sep 29, 2019 at 4:06
\$\endgroup\$
1
  • 1
    \$\begingroup\$ for coin in (x**2 for x in itertools.count(1)): ... looks rather weird. for x in itertools.count(1): coin = x ** 2 is much better. \$\endgroup\$ Commented Sep 29, 2019 at 6:49
2
\$\begingroup\$

If you want to optimize your code, optimize the algorithm first.

Thanks to Lagrange's four-square theorem, you know you will need at most four squares of positive integers.

  • You can pretend that the last number chosen will succeed.
  • You can impose that the next number chosen is not greater.
  • You can pretend that the next try will be no worse than the best to date.
  • If you get a solution fast, you can cull the search-space, so start at the big end.

Every selection will be similar, though under potentially more severe constraints, so use recursion:

def numSquaresImpl(n: int, upper: int, num: int) -> int:
 upper = min(int(sqrt(n)) + 1, upper)
 while upper ** 2 > n:
 upper = upper - 1
 if upper ** 2 == n:
 return 1
 if num <= 2:
 return 2
 lower = max(0, int(sqrt(n // num)) - 1)
 while upper >= lower:
 r = numSquaresImpl(n - upper ** 2, upper, num - 1) + 1
 upper = upper - 1
 if r < num:
 if r == 2:
 return 2
 num = r
 lower = max(0, int(sqrt(n // num)) - 1)
 return num
def numSquares(n: int) -> int:
 return numSquaresImpl(n, n, 4) if n > 0 else 0

Warning: I only proved this correct, I didn't run it. Also, I rarely do Python.

As others already said, wrapping a pure function in a class without any good reason makes no sense.

answered Sep 29, 2019 at 22:30
\$\endgroup\$
1
\$\begingroup\$

Lagrange's_four-square_theorem says:

every natural number can be represented as the sum of four integer squares.

The theorem allows the squares to be zero, so in context of our problem we will say that every natural number can be represented as the sum of four or less integer squares. It means that when we want to determine which square is the largest in the "shortest" sum, it must be greater than n // 4. It is the most significant optimization of the code below, it is implemented in the line elif square > n_4:. The code runs in 1136 ms and 30.7 MB on leetcode. I believe it can be better improved and explained but the theorem is the main idea.

import collections
Parameters = collections.namedtuple('Parameters', ['n', 'last_index', 'num_squares'])
class Solution:
 def numSquares(self, n):
 squares = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]
 min_num = n
 lst = [Parameters(n, len(squares) - 1, 0)]
 while lst:
 new_lst = []
 for parameters in lst:
 if parameters.num_squares < min_num:
 n_4 = parameters.n // 4
 for index in range(parameters.last_index + 1):
 square = squares[index]
 if square == parameters.n:
 min_num = min(min_num, parameters.num_squares + 1)
 elif square > parameters.n:
 break
 elif square > n_4:
 new_lst.append(
 Parameters(
 parameters.n - square,
 index,
 parameters.num_squares + 1
 )
 )
 lst = new_lst
 return min_num
answered Sep 29, 2019 at 19:39
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.