367. Valid Perfect Square

LeetCode ↗

Problem Editor 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.

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 runs a binary search over x from 1 to num to find the smallest integer l such that l * l >= num, which is the position where num would fit in the sequence of perfect squares [1, 4, 9, 16, 25, ...]. 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.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution uses binary search to find the smallest integer x with x * x >= num, then checks whether that x squares to exactly num.

Feasibility Function: The helper feasible(x) returns x * x >= num. As x grows, x * x only grows, so over x = 1, 2, ..., num the results form a pattern of False values followed by True values. For num = 16 the pattern is False, False, False, True, True, ..., and the first True is at x = 4.

Binary Search Setup: The search range is left = 1, right = num. The answer always lies in this range because num * num >= num for any positive num. The variable first_true_index starts at -1 and records the smallest x found so far with feasible(x) true.

Search Loop: While left <= right, compute mid = (left + right) // 2:

If feasible(mid) is true, mid is a candidate. Record first_true_index = mid and continue searching to the left with right = mid - 1 for a smaller one.
Otherwise mid is too small, so search to the right with left = mid + 1.

Verification: When the loop ends, first_true_index is the smallest x with x * x >= num. If first_true_index * first_true_index == num, then num is a perfect square. Otherwise the smallest square at least as large as num is strictly larger, so no integer squares to num.

Example:

For num = 16: the first x with x * x >= 16 is 4, and 4 * 4 = 16, so the function returns true.
For num = 14: the first x with x * x >= 14 is also 4, but 4 * 4 = 16 ≠ 14, so the function returns false.

The time complexity is O(log num) because the search range halves on every iteration, and the space complexity is O(1).

Example Walkthrough

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

Step 1: Initialize Binary Search

left = 1, right = 20, first_true_index = -1
We are looking for the smallest x with x * x >= 20

Step 2: Binary Search Process

Range [1, 20], mid = 10
- Check: 10 * 10 = 100 >= 20, so record first_true_index = 10 and set right = 9
Range [1, 9], mid = 5
- Check: 5 * 5 = 25 >= 20, so record first_true_index = 5 and set right = 4
Range [1, 4], mid = 2
- Check: 2 * 2 = 4 < 20, so set left = 3
Range [3, 4], mid = 3
- Check: 3 * 3 = 9 < 20, so set left = 4
Range [4, 4], mid = 4
- Check: 4 * 4 = 16 < 20, so set left = 5
Now left = 5 > right = 4, so the loop ends

Step 3: Result of the Search

first_true_index = 5, the smallest integer whose square is at least 20

Step 4: Verification

Check if first_true_index * first_true_index == 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 search range starts as [1, num] and halves on every iteration of the while loop, so the loop runs about log₂(num) times, and each iteration does constant work.

The space complexity is O(1). The algorithm stores only left, right, mid, and first_true_index.

Common Pitfalls

Pitfall 1: Mixing Binary Search Template Variants

The Problem: There are two common templates. One uses while left < right with right = mid and returns left. The other uses while left <= right, records the answer, and sets right = mid - 1. Both are correct here, because x = num always satisfies x * x >= num, so the answer exists. Combining parts of the two breaks the search.

Wrong Implementation:

while left < right:
    mid = (left + right) // 2
    if mid * mid >= num:
        right = mid - 1  # WRONG with left < right: can skip the answer
    else:
        left = mid + 1
return left * left == num

For num = 16: mid = 8 sets right = 7, mid = 4 sets right = 3 (stepping past the answer 4), mid = 2 sets left = 3, and the loop ends with left = 3. Since 3 * 3 ≠ 16, the code returns false for a perfect square.

Solution: Use one template consistently. The solution records each candidate in first_true_index, so moving right past it is safe:

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 quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: