Perfect Squares - Video Solutions

Problem Overview: Given an integer n, determine the minimum number of perfect square numbers (1, 4, 9, 16, ...) whose sum equals n. You can reuse the same square multiple times, and the goal is to minimize the count.

Approach 1: Brute Force (Exponential Time, O(√n) space)

The brute force idea tries every possible perfect square ≤ n and recursively subtracts it from the remaining value. For each recursive call, iterate through all squares i*i ≤ n, then compute 1 + solve(n - i*i). The algorithm explores all combinations of squares until it reaches zero. This produces an exponential time complexity because the same subproblems are recomputed many times. Space complexity is O(√n) for the recursion depth. While inefficient, this approach clearly demonstrates the problem structure and why overlapping subproblems exist.

Approach 2: Dynamic Programming (O(n√n) time, O(n) space)

Dynamic programming removes redundant computation by storing the best result for every value from 1 to n. Create an array dp where dp[i] represents the minimum number of perfect squares that sum to i. For each number i, iterate through all squares j*j ≤ i and update dp[i] = min(dp[i], dp[i - j*j] + 1). This works because if you already know the optimal result for i - j*j, adding one square gives a candidate solution for i. The algorithm processes n states and checks up to √n squares per state, resulting in O(n√n) time and O(n) space. This approach relies on classic dynamic programming techniques and leverages the mathematical structure of perfect squares from math.

Another perspective models the problem as a shortest path search. Treat each number as a node and subtract squares as edges. A level-order traversal using breadth-first search finds the minimum number of steps to reach zero. BFS and DP end up with similar O(n√n) complexity, but DP is usually simpler to implement.

Recommended for interviews: The dynamic programming solution is the expected answer. Interviewers want to see you recognize overlapping subproblems and build a bottom-up state transition. Starting with brute force shows you understand the search space, but converting it into DP demonstrates algorithmic maturity and optimization skills.