LeetCode 279: Perfect Squares Solution in Python – A Step-by-Step Guide

What Is LeetCode 279: Perfect Squares?

In LeetCode 279: Perfect Squares, you’re given a positive integer n, and your task is to find the smallest number of perfect squares (numbers like 1, 4, 9, 16, etc.) that add up to n. A perfect square is an integer that’s the square of another integer—like 4 (2²) or 9 (3²). For example, if n=12, you can use 4 + 4 + 4 = 12 (three squares) or 9 + 1 + 1 + 1 = 12 (four squares)—the goal is the minimum, so three wins. This problem blends math and optimization, sharing vibes with classics like LeetCode 322: Coin Change, but here, our “coins” are perfect squares.

Problem Statement

• Input: A positive integer n.
• Output: An integer—the least number of perfect squares that sum to n.
• Rules: Use any perfect squares (1, 4, 9, etc.) as many times as needed; find the minimum count.

Constraints

• n: 1 to 10⁴ (10,000).

Examples

• Input: n = 12
• Possible sums: 4 + 4 + 4 = 12 (3 squares), 9 + 1 + 1 + 1 = 12 (4 squares)
• Output: 3
• Input: n = 13
• Possible sums: 9 + 4 = 13 (2 squares), 4 + 4 + 4 + 1 = 13 (4 squares)
• Output: 2
• Input: n = 4
• 4 = 4 (1 square)
• Output: 1

Understanding the Problem: Building with Squares

To solve LeetCode 279: Perfect Squares in Python, we need to figure out how to express n as a sum of perfect squares using the fewest terms. For n=12, we could try every combination—1+1+1+… (12 ones), 4+4+4 (three fours), 9+1+1+1 (one nine, three ones)—but that’s tedious and slow. Instead, we’ll use: 1. Best Solution (Dynamic Programming): O(n * √n) time—smart and scalable. 2. Alternative Solution (BFS): O(n) space but intuitive—like exploring paths.

Let’s dive into the dynamic programming solution with a beginner-friendly walkthrough.

Best Solution: Dynamic Programming

Why This Is the Best Solution

Dynamic programming (DP) shines here because it’s efficient—O(n * √n) time—and uses O(n) space, building the answer step-by-step without recalculating the same subproblems. It’s like keeping a cheat sheet of how many squares you need for every number up to n, making it both fast and practical for this problem’s constraints.

How It Works

Think of this as filling a toolbox: for every number from 1 to n, you figure out the fewest perfect squares needed, using smaller numbers you’ve already solved. Here’s how it works, explained simply:

• Step 1: Set Up the DP Array:
• Create an array dp where dp[i] is the least number of squares to sum to i.
• Start with dp[0] = 0 (zero needs zero squares).
• For all others, set a big initial value (like n+1) as a placeholder.

• Step 2: Fill the Array:
• For each number i from 1 to n:
• Try every perfect square j² (where j² ≤ i).
• Update dp[i] as the minimum of its current value or dp[i - j²] + 1.
• That “+1” is adding the square j² to the solution for i - j².

• Step 3: Why It Works:
• Each dp[i] builds on smaller subproblems.
• By checking all squares ≤ i, we ensure we find the minimum combination.
• It’s like breaking i into a square plus “what’s left,” picking the best option.

• Step 4: Return the Answer:
• dp[n] is the smallest number of squares for n.

It’s like solving a puzzle by piecing together smaller puzzles you’ve already cracked!

Step-by-Step Example

Example: n = 12

• Setup: dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf] (inf = infinity or n+1).
• Squares: 1 (1²), 4 (2²), 9 (3²) (since 16 > 12).
• Fill DP:
• i=1: Try 1². dp[1] = min(dp[1], dp[0] + 1) = min(inf, 0 + 1) = 1.
• i=2: Try 1². dp[2] = min(inf, dp[1] + 1) = min(inf, 1 + 1) = 2.
• i=3: Try 1². dp[3] = min(inf, dp[2] + 1) = 3.
• i=4: Try 1², 4². dp[4] = min(dp[3] + 1, dp[0] + 1) = min(4, 1) = 1.
• i=5: Try 1², 4². dp[5] = min(dp[4] + 1, dp[1] + 1) = min(2, 2) = 2.
• i=12: Try 1², 4², 9². dp[12] = min(dp[11] + 1, dp[8] + 1, dp[3] + 1) = min(12, 3, 4) = 3.
• Result: dp[12] = 3 (e.g., 4 + 4 + 4).

Example: n = 13

• Up to 9: dp[9] = 1 (9²).
• i=13: Try 1², 4², 9². dp[13] = min(dp[12] + 1, dp[9] + 1, dp[4] + 1) = min(4, 2, 2) = 2.
• Result: 2 (9 + 4).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def numSquares(self, n: int) -> int:
        # Step 1: Initialize DP array with "infinity" (n+1 is safe)
        dp = [n + 1] * (n + 1)
        dp[0] = 0  # Base case: 0 needs 0 squares

        # Step 2: Fill DP for each number up to n
        for i in range(1, n + 1):
            # Try every perfect square j² <= i
            j = 1
            while j * j <= i:
                # Update dp[i] with the minimum option
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1

        # Step 3: Return the answer for n
        return dp[n]

• Line 4-5: dp starts with n+1 (a big number) for all spots; dp[0] = 0 since zero needs no squares.
• Line 7: Loop over each target number i from 1 to n.
• Line 9-12: For each i, test squares (1, 4, 9, …) up to i. Update dp[i] as the best of its current value or dp[i - j²] + 1.
• Line 14: dp[n] is the minimum number of squares.

• Time Complexity: O(n * √n)—n numbers, up to √n squares each.
• Space Complexity: O(n)—the DP array.

This solution is like a recipe book—builds the answer one step at a time!

Alternative Solution: Breadth-First Search (BFS)

Why an Alternative Approach?

BFS treats this like a treasure hunt: start at n, subtract squares to reach 0, and count the steps. It’s O(n) space and slower in practice, but it’s a cool way to think about the problem—like exploring paths in a maze.

How It Works

Imagine n as the starting point and 0 as the goal. At each step, subtract a perfect square and explore the results, level by level, until you hit 0. The level you’re at is the answer. Here’s how:

• Step 1: Queue starts with (n, 0)—number and steps.
• Step 2: For each number, subtract all possible squares, add new numbers to queue with +1 step.
• Step 3: Stop when you reach 0—the steps are the minimum.

It’s like fanning out possibilities until you find the shortest path!

Step-by-Step Example

Example: n = 12

• Queue: [(12, 0)].
• Level 1: 12-9=3 (steps=1), 12-4=8 (1), 12-1=11 (1).
• Level 2: 3-1=2 (2), 8-4=4 (2), 11-1=10 (2), etc.
• Level 3: 4-4=0 (3)—stop!
• Result: 3.

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def numSquares(self, n: int) -> int:
        # Queue of (number, steps)
        queue = deque([(n, 0)])
        seen = set([n])

        while queue:
            num, steps = queue.popleft()
            # Try all squares
            i = 1
            while i * i <= num:
                next_num = num - i * i
                if next_num == 0:
                    return steps + 1
                if next_num not in seen:
                    seen.add(next_num)
                    queue.append((next_num, steps + 1))
                i += 1
        return n  # Fallback (n ones)

• Time Complexity: O(n * √n) in worst case, but often slower due to queue overhead.
• Space Complexity: O(n)—queue and seen set.

It’s a fun journey, but DP is faster!

Comparing the Two Solutions

• Dynamic Programming (Best):
• Pros: O(n * √n) time, O(n) space, predictable speed.
• Cons: Requires DP mindset.
• BFS (Alternative):
• Pros: Intuitive, graph-like approach.
• Cons: More space, slower in practice.

DP wins for efficiency.

Additional Examples and Edge Cases

• n = 1: 1² = 1 → 1.
• n = 16: 16 = 4² → 1.
• n = 7: 4 + 1 + 1 + 1 → 4.

Both handle all cases well.

Complexity Breakdown

• DP: Time O(n * √n), Space O(n).
• BFS: Time O(n * √n) worst case, Space O(n).

DP is the practical choice.

Key Takeaways

• DP: Build solutions from the ground up.
• BFS: Explore paths to the goal.
• Optimization: DP’s speed rules.
• Python Tip: Loops and arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Stack Those Squares

LeetCode 279: Perfect Squares in Python is a delightful mix of math and strategy. Dynamic programming gets you there fast, while BFS offers a scenic route. Want more? Try LeetCode 322: Coin Change or LeetCode 91: Decode Ways. Ready to play? Head to Solve LeetCode 279 on LeetCode and stack those squares today!