LeetCode 367: Valid Perfect Square

Problem Restatement

Given a positive integer num, return True if it is a perfect square.

A perfect square is an integer that can be written as:

x * x

where x is also an integer.

We must not use built-in square root functions such as sqrt. The constraint is 1 <= num <= 2^31 - 1.

Input and Output

Example function shape:

def isPerfectSquare(num: int) -> bool:
    ...

Examples

Example 1:

num = 16

Since:

4 * 4 = 16

the answer is:

True

Example 2:

num = 14

There is no integer x such that:

x * x == 14

because:

3 * 3 = 9
4 * 4 = 16

So the answer is:

False

First Thought: Linear Search

The simplest method is to try every integer from 1 upward.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = 1

        while x * x <= num:
            if x * x == num:
                return True
            x += 1

        return False

This works, but it may check many numbers.

For large num, the loop may run around:

sqrt(num)

times.

We can do better with binary search.

Key Insight

If x * x is too small, then every smaller number also has a square that is too small.

If x * x is too large, then every larger number also has a square that is too large.

So the predicate has an ordered structure.

That means we can binary search over possible values of x.

The square root of num must be between:

1

and:

num

inclusive.

Algorithm

Use binary search on the integer range [1, num].

At each step:

1. Compute the middle value.
2. Compute middle * middle.
3. If it equals num, return True.
4. If it is smaller than num, search the right half.
5. If it is larger than num, search the left half.
6. If the search ends without equality, return False.

Correctness

The search range always contains every possible integer square root that has not been ruled out.

When mid * mid < num, mid and every smaller value cannot be the square root, so the algorithm safely moves left to mid + 1.

When mid * mid > num, mid and every larger value cannot be the square root, so the algorithm safely moves right to mid - 1.

When mid * mid == num, an integer square root has been found, so num is a perfect square.

If the loop ends, every possible integer candidate has been ruled out. Therefore, num is not a perfect square.

Complexity

Implementation

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 1
        right = num

        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid

            if square == num:
                return True

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

        return False

Code Explanation

The search begins with all possible roots:

left = 1
right = num

The midpoint is computed this way:

mid = left + (right - left) // 2

In Python, overflow is not a problem. In languages with fixed-width integers, this form is safer than (left + right) // 2.

Then we compute:

square = mid * mid

If it matches num, we found the integer square root.

If the square is too small:

left = mid + 1

If the square is too large:

right = mid - 1

If no exact square is found, return:

False

Testing

def run_tests():
    s = Solution()

    assert s.isPerfectSquare(1) is True
    assert s.isPerfectSquare(4) is True
    assert s.isPerfectSquare(9) is True
    assert s.isPerfectSquare(14) is False
    assert s.isPerfectSquare(16) is True
    assert s.isPerfectSquare(808201) is True
    assert s.isPerfectSquare(2147483647) is False

    print("all tests passed")

run_tests()

Test meaning: