LeetCode 633: Sum of Square Numbers Solution in Python – A Step-by-Step Guide

What Is LeetCode 633: Sum of Square Numbers?

In LeetCode 633: Sum of Square Numbers, you’re given a non-negative integer c, and your task is to determine if there exist two integers a and b (including 0) such that a² + b² = c. Return True if possible, False otherwise. For example, c = 5 works with a = 1, b = 2 (1² + 2² = 5), but c = 3 does not (no integer pair fits). This problem tests your ability to efficiently search for square sums, drawing on number theory and optimization techniques.

Problem Statement

• Input:
• c: A non-negative integer (0 ≤ c ≤ 2³¹ - 1).
• Output: A boolean—True if c is a sum of two squares, False otherwise.
• Rules:
• Find integers a and b where a² + b² = c.
• a and b can be 0 or positive.
• Return result based on existence.

Constraints

• 0 ≤ c ≤ 2³¹ - 1 (2,147,483,647).

Examples

• Input: c = 5
• Output: True (1² + 2² = 1 + 4 = 5)
• Input: c = 3
• Output: False (No integer pair works)
• Input: c = 0
• Output: True (0² + 0² = 0)

These examples set the stage—let’s solve it!

Understanding the Problem: Sum of Squares

To solve LeetCode 633: Sum of Square Numbers in Python, we need to check if a number c can be expressed as a² + b² for some integers a and b. A brute-force approach—testing all pairs up to √c—would be O(c), too slow for c up to 2³¹ - 1. Since squares grow quadratically, we can optimize by searching smarter. We’ll use:

• Best Solution (Two-Pointer Approach): O(√c) time, O(1) space—fast and efficient.
• Alternative Solution (Hash Set Approach): O(√c) time, O(√c) space—simple but uses more memory.

Let’s start with the two-pointer solution, breaking it down for beginners.

Best Solution: Two-Pointer Approach

Why This Is the Best Solution

The two-pointer approach is the top choice for LeetCode 633 because it’s efficient—O(√c) time with O(1) space—and intuitive, using a sliding window-like technique to find a pair of squares summing to c. It leverages the fact that if a² + b² = c, then as a increases, b must decrease, and we only need to check up to √c. It fits constraints (c ≤ 2³¹ - 1) perfectly. It’s like balancing two ends of a seesaw to hit the target!

How It Works

Think of this as a square balancer:

• Step 1: Set Pointers:
• left = 0 (smallest square).
• right = floor(sqrt(c)) (largest possible square).
• Step 2: Slide Pointers:
• Compute curr = left² + right².
• If curr = c, return True.
• If curr < c, increment left (need more).
• If curr > c, decrement right (need less).
• Step 3: Check Bounds:
• Stop when left > right.
• Step 4: Return Result:
• Return False if no pair found.

It’s like a number dance—adjust and match!

Step-by-Step Example

Example: c = 5

• Step 1: left = 0, right = floor(sqrt(5)) = 2.
• Step 2: Slide:
• 0² + 2² = 0 + 4 = 4 < 5, left = 1.
• 1² + 2² = 1 + 4 = 5 = 5, found!
• Step 3: Return True.
• Output: True.

Example: c = 3

• Step 1: left = 0, right = 1.
• Step 2:
• 0² + 1² = 1 < 3, left = 1.
• 1² + 1² = 2 < 3, left = 2.
• left > right, stop.
• Step 3: No match.
• Output: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeimport math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        # Step 1: Set two pointers
        left = 0
        right = int(math.sqrt(c))

        # Step 2: Slide pointers
        while left <= right:
            curr = left * left + right * right
            if curr == c:
                return True
            elif curr < c:
                left += 1
            else:
                right -= 1

        # Step 3: No pair found
        return False

• Line 1: Import math for sqrt.
• Lines 6-7: Init pointers: left at 0, right at √c.
• Lines 10-16: Slide:
• Compute sum, adjust pointers based on comparison.
• Line 19: Return False if no match.
• Time Complexity: O(√c)—pointers converge.
• Space Complexity: O(1)—no extra space.

This is like a square seeker—fast and lean!

Alternative Solution: Hash Set Approach

Why an Alternative Approach?

The hash set approach precomputes squares up to √c—O(√c) time, O(√c) space. It’s simpler, checking if c - a² is a square via lookup, but uses more memory. It’s like building a square library and searching it!

How It Works

Picture this as a square lookup:

• Step 1: Build set of squares up to √c.
• Step 2: For each a, check if c - a² is in set.
• Step 3: Return True if found, False otherwise.

It’s like a square matcher—check and find!

Step-by-Step Example

Example: c = 5

• Step 1: Squares = {0, 1, 4} (0², 1², 2²).
• Step 2:
• a = 0: 5 - 0 = 5, not in set.
• a = 1: 5 - 1 = 4, in set, found!
• Step 3: Return True.
• Output: True.

Code for Hash Set Approach

Copy codeimport math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        # Step 1: Build set of squares
        squares = set()
        for i in range(int(math.sqrt(c)) + 1):
            squares.add(i * i)

        # Step 2: Check for complement
        for a in squares:
            if c - a in squares:
                return True

        # Step 3: No pair found
        return False

• Lines 6-8: Build set of squares.
• Lines 11-13: Check if c - a is a square.
• Time Complexity: O(√c)—set building and lookup.
• Space Complexity: O(√c)—set storage.

It’s a square librarian—simple but bulkier!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(√c) time, O(1) space, fast and lean.
• Cons: Slightly less intuitive.
• Hash Set (Alternative):
• Pros: O(√c) time, O(√c) space, straightforward.
• Cons: More memory.

Two-pointer wins for efficiency.

Additional Examples and Edge Cases

• Input: c = 0
• Output: True (0² + 0²).
• Input: c = 2
• Output: True (1² + 1²).

Both handle these well.

Complexity Breakdown

• Two-Pointer: Time O(√c), Space O(1).
• Hash Set: Time O(√c), Space O(√c).

Two-pointer is optimal.

Key Takeaways

• Two-Pointer: Sliding elegance—smart!
• Hash Set: Lookup simplicity—clear!
• Numbers: Squares are fun.
• Python Tip: Math rocks—see Python Basics.

Final Thoughts: Find Those Squares

LeetCode 633: Sum of Square Numbers in Python is a neat number theory challenge. The two-pointer approach offers speed and minimalism, while the hash set provides a clear alternative. Want more? Try LeetCode 279: Perfect Squares or LeetCode 367: Valid Perfect Square. Ready to square up? Head to Solve LeetCode 633 on LeetCode and check those sums today!