367. Valid Perfect Square

EasyMathBinary Search

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Squaring is monotonic on positive integers, so binary search over `[1, num]` finds the first x with x*x >= num and checks for equality.

Open in Flowchart

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

1class Solution:
2    def isPerfectSquare(self, num: int) -> bool:
3        """
4        Determines if a given number is a perfect square using binary search.
5
6        We search for the first value x where x * x >= num. If x * x == num exactly,
7        then num is a perfect square.
8
9        Args:
10            num: A positive integer to check
11
12        Returns:
13            True if num is a perfect square, False otherwise
14        """
15        # Define feasible: x * x >= num
16        # We want the first x where this is true
17        def feasible(x: int) -> bool:
18            return x * x >= num
19
20        # Binary search for the first value where x * x >= num
21        left, right = 1, num
22        first_true_index = -1
23
24        while left <= right:
25            mid = (left + right) // 2
26            if feasible(mid):
27                first_true_index = mid
28                right = mid - 1
29            else:
30                left = mid + 1
31
32        # Check if first_true_index squared equals num exactly
33        return first_true_index != -1 and first_true_index * first_true_index == num
34

1class Solution {
2    /**
3     * Determines if num is a perfect square using the binary search template.
4     * Feasible condition: mid * mid >= num
5     * We find the first value where this is true, then check if it's an exact match.
6     */
7    public boolean isPerfectSquare(int num) {
8        int left = 1;
9        int right = num;
10        int firstTrueIndex = -1;
11
12        while (left <= right) {
13            int mid = left + (right - left) / 2;
14            // Use long to prevent overflow
15            if ((long) mid * mid >= num) {
16                firstTrueIndex = mid;
17                right = mid - 1;
18            } else {
19                left = mid + 1;
20            }
21        }
22
23        // Check if the found value squared equals num exactly
24        return firstTrueIndex != -1 && (long) firstTrueIndex * firstTrueIndex == num;
25    }
26}
27

1class Solution {
2public:
3    /**
4     * Determines if num is a perfect square using the binary search template.
5     * Feasible condition: mid * mid >= num
6     * We find the first value where this is true, then check if it's an exact match.
7     */
8    bool isPerfectSquare(int num) {
9        int left = 1;
10        int right = num;
11        int firstTrueIndex = -1;
12
13        while (left <= right) {
14            int mid = left + (right - left) / 2;
15            // Use long long to prevent overflow
16            if (static_cast<long long>(mid) * mid >= num) {
17                firstTrueIndex = mid;
18                right = mid - 1;
19            } else {
20                left = mid + 1;
21            }
22        }
23
24        // Check if the found value squared equals num exactly
25        return firstTrueIndex != -1 &&
26               static_cast<long long>(firstTrueIndex) * firstTrueIndex == num;
27    }
28};
29

1/**
2 * Determines if a given number is a perfect square using the binary search template.
3 * Feasible condition: mid * mid >= num
4 * We find the first value where this is true, then check if it's an exact match.
5 *
6 * Time Complexity: O(log n)
7 * Space Complexity: O(1)
8 */
9function isPerfectSquare(num: number): boolean {
10    let left = 1;
11    let right = num;
12    let firstTrueIndex = -1;
13
14    while (left <= right) {
15        const mid = Math.floor((left + right) / 2);
16        if (mid * mid >= num) {
17            firstTrueIndex = mid;
18            right = mid - 1;
19        } else {
20            left = mid + 1;
21        }
22    }
23
24    // Check if the found value squared equals num exactly
25    return firstTrueIndex !== -1 && firstTrueIndex * firstTrueIndex === num;
26}
27

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

Pitfall 1: Using Wrong Binary Search Template Variant

The Problem: Using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Wrong Implementation:

while left < right:
    mid = (left + right) // 2
    if mid * mid >= num:
        right = mid  # WRONG - should be mid - 1
    else:
        left = mid + 1
return left * left == num  # WRONG - should track first_true_index

Solution: Use the standard template with first_true_index to track the answer:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if mid * mid >= num:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index != -1 and first_true_index * first_true_index == num

Pitfall 2: Integer Overflow Issue

The multiplication mid * mid can exceed the maximum integer value in languages with fixed integer sizes.

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

Solution: Use long/long long types for the multiplication:

if ((long) mid * mid >= num)  // Java

if (static_cast<long long>(mid) * mid >= num)  // C++

Pitfall 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: Keep the search range as [1, num] which handles all cases correctly, including num = 1.

Pitfall 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 when left + right exceeds the maximum integer value.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: