LeetCode 367 - Valid Perfect Square

LeetCode Problem 367

Difficulty: 🟢 Easy
Topics: Math, Binary Search

Solution

Problem Understanding

The problem asks us to determine whether a given positive integer num is a perfect square without using built in square root functions such as sqrt().

A perfect square is a number that can be written as:

$n = k^2$

where k is an integer. For example, 16 is a perfect square because 4 * 4 = 16, while 14 is not because no integer squared equals 14.

The input consists of a single positive integer num. The output should be a boolean value:

• Return true if there exists an integer whose square equals num
• Return false otherwise

The constraint is:

1 <= num <= 2^31 - 1

This tells us several important things. First, the input size can be quite large, up to over two billion. A naive linear search may still work in practice for smaller inputs, but it is not ideal for the upper bound. Second, since squaring numbers can exceed 32 bit integer limits in some languages, we need to be careful about integer overflow, especially in Go.

Several edge cases are important:

• num = 1, the smallest valid input, is a perfect square
• Very large perfect squares near the upper limit
• Very large non perfect squares
• Numbers between two consecutive squares, such as 15
• Overflow when computing mid * mid during binary search

The problem guarantees that the input is always positive, so we do not need to handle zero or negative values.

Approaches

Brute Force Approach

The simplest approach is to try every integer starting from 1 and check whether its square equals num.

We repeatedly compute:

$i^2$

If i * i == num, then num is a perfect square. If i * i becomes greater than num, we can stop because squares only increase as i increases.

This approach is correct because every possible integer square root candidate is checked. However, it can be too slow for large values. In the worst case, we may need to test numbers up to approximately:

$\sqrt{num}$

For values near 2^31 - 1, this means tens of thousands of iterations.

Optimal Approach, Binary Search

The key observation is that square numbers increase monotonically. If:

$mid^2 < num$

then the correct square root, if it exists, must be larger than mid. Similarly, if:

$mid^2 > num$

then the correct value must be smaller than mid.

This monotonic behavior makes binary search a perfect fit.

Instead of checking every number one by one, binary search repeatedly cuts the search range in half. This reduces the time complexity dramatically from linear to logarithmic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(√n)	O(1)	Checks every possible integer square root
Optimal	O(log n)	O(1)	Uses binary search on the possible square root range

Algorithm Walkthrough

1. Initialize two pointers, left and right.

The smallest possible square root is 1, and the largest possible square root of num cannot exceed num itself. So we begin with:

left = 1
right = num

2. Continue searching while left <= right.

This ensures we examine every possible candidate range. 3. Compute the middle value.

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

This form avoids overflow in languages with fixed size integers. 4. Compute mid * mid.

This tells us whether mid is too small, too large, or exactly correct. 5. Compare mid * mid with num.

• If equal, return true
• If smaller, move the left boundary upward because we need a larger square
• If larger, move the right boundary downward because we need a smaller square

6. If the loop finishes without finding an exact square, return false.

This means no integer square root exists.

Why it works

Binary search works because the function:

$f(x)=x^2$ .graphable-function-chartjs { position: relative; overflow: hidden; touch-action: none; }

    .graphable-function-chartjs-tooltip {
      position: absolute;
      z-index: 1;
      border-radius: 9px;
      background: rgb(0 0 0 / 90%);
      color: white;
      font-size: 11px;
      font-weight: 600;
      line-height: 14px;
      padding: 6px 12px;
      text-align: center;
      white-space: nowrap;
      pointer-events: none;
    }

    .graphable-function-chartjs-guide {
      position: absolute;
      top: 0;
      bottom: 0;
      border-left: 1px dashed var(--border-heavy);
      pointer-events: none;
    }

    .graphable-function-chartjs-hover-point {
      position: absolute;
      width: 8px;
      height: 8px;
      margin-left: -4px;
      margin-top: -4px;
      border: 1.5px solid white;
      border-radius: 9999px;
      background: black;
      pointer-events: none;
    }

    .graphable-function-chartjs-reset {
      position: absolute;
      left: 12px;
      bottom: 12px;
      display: inline-flex;
      align-items: center;
      justify-content: center;
      z-index: 2;
      width: 32px;
      height: 32px;
      border: 1px solid var(--border-light);
      border-radius: 9999px;
      background: var(--bg-primary);
      color: var(--text-primary);
      box-shadow: 0 2px 8px rgb(0 0 0 / 8%);
      padding: 0;
      transition: opacity 160ms ease, transform 160ms ease;
    }

is strictly increasing for positive integers. Once a square exceeds num, all larger squares will also exceed num. Similarly, once a square is smaller than num, all smaller squares will also be too small. This ordered structure guarantees that binary search can safely eliminate half the remaining search space at every step.

Python Solution

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
            elif square < num:
                left = mid + 1
            else:
                right = mid - 1

        return False

The implementation begins by initializing the binary search boundaries. The search space includes every possible integer square root candidate from 1 to num.

Inside the loop, the midpoint is calculated safely using:

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

This prevents overflow in other languages and is considered best practice even though Python integers are unbounded.

The variable square stores mid * mid so the multiplication is performed only once per iteration.

If square == num, we immediately return True because we found an integer whose square equals the target.

If square < num, then mid is too small, so we discard the left half by setting:

left = mid + 1

If square > num, then mid is too large, so we discard the right half by setting:

right = mid - 1

If the loop finishes, no integer square root exists, so the function returns False.

Go Solution

func isPerfectSquare(num int) bool {
    left := 1
    right := num

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

        if square == num {
            return true
        } else if square < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return false
}

The Go implementation follows the same binary search logic as the Python version.

One important consideration in Go is integer overflow. Since mid * mid could overflow a 32 bit integer in some environments, using int64 would be safer in production code. However, on LeetCode's Go environment, int is typically large enough for this problem.

Unlike Python, Go does not support arbitrary precision integers by default, so overflow awareness is more important.

Worked Examples

Example 1

Input:

num = 16

We search for an integer whose square equals 16.

Iteration	left	right	mid	mid * mid	Action
1	1	16	8	64	Too large, move right
2	1	7	4	16	Found exact square

The algorithm returns true.

Example 2

Input:

num = 14

Iteration	left	right	mid	mid * mid	Action
1	1	14	7	49	Too large, move right
2	1	6	3	9	Too small, move left
3	4	6	5	25	Too large, move right
4	4	4	4	16	Too large, move right

Now:

left = 4
right = 3

The loop stops, and the algorithm returns false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space each iteration
Space	O(1)	Only a few variables are used

The time complexity is logarithmic because each iteration removes half of the remaining search interval. Starting from a range of size n, binary search requires approximately:

$\log_2 n$

iterations.

The space complexity is constant because the algorithm only stores a fixed number of integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.isPerfectSquare(1) == True      # smallest valid perfect square
assert solution.isPerfectSquare(4) == True      # simple perfect square
assert solution.isPerfectSquare(9) == True      # odd perfect square
assert solution.isPerfectSquare(16) == True     # example case
assert solution.isPerfectSquare(25) == True     # larger perfect square

assert solution.isPerfectSquare(2) == False     # smallest non-square
assert solution.isPerfectSquare(3) == False     # small non-square
assert solution.isPerfectSquare(14) == False    # example case
assert solution.isPerfectSquare(15) == False    # between two perfect squares
assert solution.isPerfectSquare(26) == False    # just above a perfect square

assert solution.isPerfectSquare(808201) == True     # 899 * 899
assert solution.isPerfectSquare(2147395600) == True # largest square within 32-bit range
assert solution.isPerfectSquare(2147483647) == False # max 32-bit signed integer

Test	Why
1	Smallest valid input
4	Simple perfect square
9	Odd perfect square
16	Provided example
25	Larger perfect square
2	Smallest non-square
3	Small non-square
14	Provided non-square example
15	Between consecutive squares
26	Just above a square
808201	Medium sized perfect square
2147395600	Largest important perfect square in 32-bit range
2147483647	Maximum constraint value

Edge Cases

One important edge case is num = 1. Since 1 is both the smallest valid input and a perfect square, implementations that incorrectly initialize boundaries or loop conditions may fail here. Our binary search handles it correctly because the initial range includes 1, and the first midpoint immediately matches the target.

Another important case involves numbers directly adjacent to perfect squares, such as 15 or 26. These values are easy to mishandle if the binary search updates boundaries incorrectly. Our implementation carefully moves left and right by one position after each comparison, ensuring the loop terminates correctly without skipping possible answers.

A third critical edge case is very large inputs near the maximum constraint, especially 2147483647. Squaring large midpoint values can overflow fixed size integers in some languages. The algorithm avoids unnecessary operations and uses safe midpoint calculation. In production Go code, using int64 for the multiplication would provide additional overflow protection.