LeetCode 367: Valid Perfect Square Solution in Python – A Step-by-Step Guide

What Is LeetCode 367: Valid Perfect Square?

LeetCode 367: Valid Perfect Square gives you a non-negative integer and asks you to determine if it’s a perfect square—i.e., if there exists an integer x such that x² equals the given number. It’s a straightforward problem that tests your ability to optimize a classic math check!

Problem Statement

• Input:
• num: Non-negative integer.
• Output: Boolean - True if num is a perfect square, False otherwise.
• Rules:
• A perfect square is an integer n such that n = x² for some integer x.
• No built-in square root functions allowed (e.g., math.sqrt).

Constraints

• 0 <= num <= 2³¹ - 1 (i.e., 0 to 2,147,483,647)

Examples

• Input: num = 16
• Output: True
• 4² = 16, so it’s a perfect square.
• Input: num = 14
• Output: False
• 3² = 9 < 14, 4² = 16 > 14, no integer x satisfies x² = 14.
• Input: num = 0
• Output: True
• 0² = 0, valid perfect square.

These show the square hunt—let’s solve it!

Understanding the Problem: Identifying Perfect Squares

To tackle LeetCode 367 in Python, we need to: 1. Check if num is the square of an integer x. 2. Avoid using built-in sqrt (to focus on algorithmic thinking). 3. Handle edge cases like 0 and large numbers efficiently.

A naive approach might test all integers up to num, but that’s slow. Instead, we’ll use:

• Best Solution: Binary search—O(log n) time, O(1) space—fast and intuitive.
• Alternative Solution: Newton’s method—O(log n) time, O(1) space—mathematical and elegant.

Let’s find squares with the best solution!

Best Solution: Binary Search

Why This Is the Best Solution

The binary search approach runs in O(log n) time by efficiently narrowing down the range of possible square roots (0 to num) using a divide-and-conquer strategy. It’s simple, avoids floating-point issues, and meets the problem’s constraints without extra tools—making it the top choice for clarity and performance!

How It Works

Think of it like guessing a number:

• Range: Search for x where x² = num, between 0 and num (or a tighter bound).
• Binary Search:
• Compute mid² and compare with num.
• If mid² = num, found it.
• If mid² < num, search higher.
• If mid² > num, search lower.
• Result: True if an exact match is found, False otherwise.

It’s like zeroing in on the perfect root!

Step-by-Step Example

For num = 16:

• Range: left=0, right=16.
• Step 1: mid=8, 8²=64 > 16, right=7.
• Step 2: mid=3, 3²=9 < 16, left=4.
• Step 3: mid=4, 4²=16 = 16, return True.

For num = 14:

• Range: left=0, right=14.
• Step 1: mid=7, 7²=49 > 14, right=6.
• Step 2: mid=3, 3²=9 < 14, left=4.
• Step 3: mid=4, 4²=16 > 14, right=3.
• Step 4: left=4 > right=3, no match, return False.

For num = 0:

• Range: left=0, right=0.
• Step 1: mid=0, 0²=0 = 0, return True.

Code with Explanation

Here’s the Python code using binary search:

Copy codeclass Solution:
    def isPerfectSquare(self, num: int) -> bool:
        # Handle edge case
        if num == 0:
            return True

        # Binary search for square root
        left, right = 1, num
        while left <= right:
            mid = (left + right) // 2
            square = mid * mid

            if square == num:
                return True
            elif square < num:
                left = mid + 1
            else:
                right = mid - 1

        return False

Explanation

• Lines 3-5: Handle num=0 (0²=0 is a perfect square).
• Line 8: Set search range: 1 to num (exclude 0 since handled).
• Lines 9-16: Binary search loop:
• Compute mid and square (mid * mid).
• If square = num, return True.
• If square < num, search higher (left = mid + 1).
• If square > num, search lower (right = mid - 1).
• Line 18: If loop ends (left > right), no perfect square found, return False.

• Time Complexity: O(log n)—halves the search range each step.
• Space Complexity: O(1)—only a few variables.

This is like a number-guessing game—find the square root fast!

Alternative Solution: Newton’s Method

Why an Alternative Approach?

Newton’s method also runs in O(log n) time by iteratively refining an approximation of the square root using a mathematical formula. It’s an elegant alternative—great for those who enjoy calculus-inspired solutions or want variety!

How It Works

• Formula: x₁ = (x₀ + num/x₀) / 2, starting with x₀ = num.
• Iterate: Refine x until x² ≈ num.
• Check: Verify if x² = num exactly (integer check).

It’s like zeroing in on the root with math magic!

Step-by-Step Example

For num = 16:

• Start: x=16.
• Iter 1: x = (16 + 16/16) / 2 = (16 + 1) / 2 = 8.5.
• Iter 2: x = (8.5 + 16/8.5) / 2 ≈ (8.5 + 1.882) / 2 ≈ 5.191.
• Iter 3: x = (5.191 + 16/5.191) / 2 ≈ (5.191 + 3.082) / 2 ≈ 4.136.
• Iter 4: x = (4.136 + 16/4.136) / 2 ≈ (4.136 + 3.868) / 2 ≈ 4.002.
• Iter 5: x ≈ 4 (converges), 4² = 16, return True.

For num = 14:

• Converges to ≈ 3.741, 3²=9, 4²=16, no exact match, return False.

Code with Explanation

Copy codeclass Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 0:
            return True
        if num == 1:
            return True

        # Newton’s method to approximate square root
        x = num
        while x * x > num:
            x = (x + num // x) // 2
        # Check if x is exact square root
        return x * x == num

Explanation

• Lines 3-6: Handle edge cases: 0 and 1 are perfect squares.
• Lines 9-11: Newton’s iteration:
• Start with x = num.
• Update x = (x + num/x) / 2 until x² ≤ num (use // for integer division).
• Line 13: Check if x² = num exactly.
• Time: O(log n)—converges quadratically.
• Space: O(1)—minimal variables.

It’s like a mathematical refinement process!

Comparing the Two Solutions

• Binary Search (Best):
• Time: O(log n)—divide-and-conquer.
• Space: O(1)—no extra space.
• Pros: Simple, intuitive, reliable.
• Cons: Slightly more iterations than Newton’s.
• Newton’s Method (Alternative):
• Time: O(log n)—quadratic convergence.
• Space: O(1)—minimal.
• Pros: Elegant, fewer iterations for large n.
• Cons: Less intuitive, integer handling trickier.

Binary search wins for simplicity and clarity!

Additional Examples and Edge Cases

• num=1: True (1²=1).
• num=2147483647: False (largest int, not a square).
• num=4: True (2²=4).

Both handle these, binary search is more straightforward.

Complexity Breakdown

• Binary Search:
• Time: O(log n).
• Space: O(1).
• Newton’s:
• Time: O(log n).
• Space: O(1).

Both are efficient, binary search is preferred.

Key Takeaways

• Binary Search: Find the root—fast and clear!
• Newton’s: Math refines it—elegant and quick!
• Squares: Numbers have patterns.
• Python Tip: Loops beat builtins—see [Python Basics](/python/basics).

Final Thoughts: Spot Those Squares

LeetCode 367: Valid Perfect Square in Python is a number-hunting challenge. Binary search is the clarity champ, while Newton’s offers mathematical flair. Want more? Try LeetCode 69: Sqrt(x) or LeetCode 278: First Bad Version. Ready to square? Visit Solve LeetCode 367 on LeetCode and check those numbers today!