Perfect Squares | LeetCode | Solution Explained
279. Perfect Squares on LeetCode is a mathematical problem, requiring us to pair math with algorithms. I explore how we can do that using Dynamic Programming (DP) and BFS. Problem Link.
Perfect Squares: Logic
We know that mathematically we can break it down as:
- a, b, c, … represent the coefficients
- we have to minimize the sum of the coefficients
The first thing I wanted to do was to try and restrict the range of x. How far can it go, when we have n restricting it?
We can do x = (int)sqrt(n) to find the x value in an instant. This takes O(log(n)) time & O(1) space. Time is because Python calculates square roots using Newton’s method. Here’s a math.stackexchange link.
Let’s take an example. When n = 120, we have sqrt(120) as 10.95… which is 10 in terms of int value. Thus, we can try and break down the 120 value
Let’s take another example. In this case we start with 3.
Clearly, we can have multiple paths. How do we know the best one? When we are making a decision between the first 2 or 3, we don’t know what would happen in the future. How can we see into the future? if you have been following me, you know its the cue for recursion!
Perfect Squares: Recursive DP Code
class Solution:
def numSquares(self, n: int) -> int:
@lru_cache(None)
def recurse(n):
if n == 0: return 0
x = (int)(sqrt(n))
count = inf
for i in reversed(range(1, x+1)):
if n - i*i >= 0:
temp = recurse(n - i*i)
count = min(count, temp + 1)
return count
return recurse(n)
Modified Recursive DP Code for Manual DP
class Solution:
def numSquares(self, n: int) -> int:
# @lru_cache(None) no need now
def recurse(n):
if dp[n] != inf: return dp[n]
if n == 0: return 0
x = (int)(sqrt(n))
count = inf
for i in reversed(range(1, x+1)):
if n - i*i >= 0:
temp = recurse(n - i*i)
count = min(count, temp + 1)
dp[n] = count
return dp[n]
dp = [inf]*(n+1)
return recurse(n)Perfect Squares: BFS Solution
The above solutions were using dfs. What if we used BFS instead? Think about why that is better. I have explained it in my video solution.
class Solution:
def numSquares(self, n: int) -> int:
sq = [i*i for i in range(1, (int)(sqrt(n))+1)]
explore = {n}
count = 0
while explore:
count += 1
temp = set()
for n in explore:
for x in sq:
if n - x == 0:
return count
if n - x > 0:
temp.add(n-x)
explore = temp
return count
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Seats | InterviewBit | Solution Explained
June 13, 2022
Meeting Rooms | InterviewBit | Solution Explained
June 13, 2022