Problem Description

You are given a positive integer num. Your task is to determine whether this number is a perfect square or not. Return true if it is a perfect square, otherwise return false.

A perfect square is an integer that can be expressed as the product of some integer with itself. For example:

• 16 is a perfect square because 4 × 4 = 16
• 25 is a perfect square because 5 × 5 = 25
• 14 is not a perfect square because there's no integer that when multiplied by itself equals 14

The constraint is that you cannot use any built-in library functions like sqrt to solve this problem. You need to implement your own logic to check if the given number is a perfect square.

The solution uses binary search to find if there exists an integer x such that x × x = num. It searches for the smallest integer whose square is greater than or equal to num. If that integer's square exactly equals num, then num is a perfect square.

Intuition

Since we need to find if there exists an integer x where x * x = num, we essentially need to search for this value x in the range from 1 to num.

The key insight is that if num is a perfect square, then its square root must be an integer between 1 and num. Instead of checking every single number from 1 to num (which would be inefficient for large numbers), we can use binary search to quickly narrow down our search space.

Why does binary search work here? Because the function f(x) = x * x is monotonically increasing - as x increases, x * x also increases. This means if we pick a middle value and compute its square:

• If the square is less than num, we know we need to search in the higher half
• If the square is greater than num, we need to search in the lower half
• If the square equals num, we've found our answer

The solution cleverly uses bisect_left with a key function lambda x: x * x to find the position where num would fit in the sequence of perfect squares [1, 4, 9, 16, 25, ...]. This gives us the smallest integer l such that l * l >= num. Finally, we just need to check if l * l exactly equals num - if it does, then num is a perfect square; otherwise, it's not.

This approach reduces the time complexity from O(num) for a linear search to O(log num) using binary search.

Solution Approach

The solution implements a binary search approach to find if a number is a perfect square. Here's how the implementation works:

Binary Search Setup: The code uses Python's bisect_left function to perform the binary search. The search range is set from 1 to num, represented as range(1, num + 1).

Key Function: The crucial part is the key=lambda x: x * x parameter. This transforms our search space - instead of searching through the numbers [1, 2, 3, ..., num], we're effectively searching through their squares [1, 4, 9, ..., num²].

Finding the Position: bisect_left finds the leftmost position where num would fit in the sequence of perfect squares. Since bisect_left returns a 0-based index and our range starts at 1, we add 1 to get the actual value: l = bisect_left(...) + 1.

Verification: After finding l, we check if l * l == num. If this condition is true, it means num is exactly the square of l, making it a perfect square.

Example Walkthrough:

• For num = 16: The binary search finds that 16 fits at position 3 (0-indexed) in the sequence [1, 4, 9, 16, 25, ...]. Adding 1 gives us l = 4. Since 4 * 4 = 16, the function returns true.
• For num = 14: The binary search finds that 14 would fit between 9 and 16. It returns position 3, giving us l = 4. Since 4 * 4 = 16 ≠ 14, the function returns false.

The time complexity is O(log num) due to the binary search, and the space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with num = 20 to see how the binary search approach works:

Step 1: Initialize Binary Search

• We're searching in the range [1, 2, 3, 4, 5, ..., 20]
• The key function transforms each value x to x * x, so we're effectively searching where 20 fits in the sequence [1, 4, 9, 16, 25, 36, 49, ...]

Step 2: Binary Search Process

• Start with search range [1, 20], middle = 10
  • Check: 10 * 10 = 100 > 20, so search left half [1, 9]
• New range [1, 9], middle = 5
  • Check: 5 * 5 = 25 > 20, so search left half [1, 4]
• New range [1, 4], middle = 2
  • Check: 2 * 2 = 4 < 20, so search right half [3, 4]
• New range [3, 4], middle = 3
  • Check: 3 * 3 = 9 < 20, so search right half [4, 4]
• Final range [4, 4], middle = 4
  • Check: 4 * 4 = 16 < 20, need to go higher

Step 3: Result from bisect_left

• bisect_left returns index 4 (0-based) as the position where 20 would be inserted
• After adding 1 to convert from 0-based index: l = 5

Step 4: Verification

• Check if l * l == num: 5 * 5 = 25 ≠ 20
• Since 25 ≠ 20, return false

Therefore, 20 is not a perfect square. The closest perfect squares are 16 (4²) and 25 (5²), with 20 falling between them.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the given number. The bisect_left function performs a binary search on the range from 1 to num, which contains n elements. Binary search divides the search space in half at each step, resulting in logarithmic time complexity.

The space complexity is O(1). Although range(1, num + 1) is used as an argument to bisect_left, in Python 3, range objects are lazy iterators that don't create the entire list in memory. The bisect_left function only evaluates the key function for specific indices during the binary search process, using constant extra space for variables like search boundaries and the mid-point calculation.

Common Pitfalls

1. Integer Overflow Issue

The most critical pitfall in this solution is the potential for integer overflow when calculating mid * mid. For very large values of num, the multiplication mid * mid can exceed the maximum integer value, causing overflow issues in languages with fixed integer sizes (though Python handles arbitrary precision integers automatically).

Problem Example:

• When num = 2147483647 (maximum 32-bit integer), and mid = 46341, calculating mid * mid = 2147488281 would overflow in a 32-bit system.

Solution: Instead of comparing mid * mid with num, use division to avoid overflow:

if mid == num // mid and num % mid == 0:
    return True
elif mid < num // mid:
    left = mid + 1
else:
    right = mid - 1

2. Inefficient Search Range

Setting the initial right boundary to num is inefficient for large numbers. The square root of any number greater than 1 is always less than or equal to num / 2.

Problem Example:

• For num = 100, searching from 1 to 100 is unnecessary when the square root can't be larger than 50.

Solution: Optimize the initial search range:

left, right = 1, min(num, num // 2 + 1)

3. Not Handling Edge Cases Properly

The code might not handle num = 1 correctly if the search range is optimized incorrectly.

Problem Example:

• If you set right = num // 2, then for num = 1, right = 0, making the search range invalid.

Solution: Add special handling for small numbers:

if num < 2:
    return True  # Both 0 and 1 are perfect squares
left, right = 2, num // 2

4. Using Wrong Middle Point Calculation

Using (left + right) // 2 instead of left + (right - left) // 2 can cause overflow in languages with fixed integer sizes.

Improved Complete Solution:

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 2:
            return True
      
        left, right = 2, num // 2
      
        while left <= right:
            mid = left + (right - left) // 2
          
            # Use division to avoid overflow
            if mid == num // mid and num % mid == 0:
                return True
            elif mid < num // mid:
                left = mid + 1
            else:
                right = mid - 1
      
        return False