Valid Perfect Square

Easybinary-searchmath
Category: Fundamentals
Companies that ask this question:
AmazonGoogle
LeetCode →

Approach

Valid Perfect Square

Approach

Use binary search to find if number is perfect square.

Algorithm

  1. Handle edge cases (num < 2)
  2. Binary search in range [2, num/2]
  3. For each mid:
    • If mid² = num: return true
    • If mid² < num: search right half
    • If mid² > num: search left half
  4. Return false if not found

Complexity

  • Time: O(log n) - binary search
  • Space: O(1) - constant space

Key Insights

  • Square root of n is at most n/2 for n ≥ 2
  • Binary search more efficient than linear scan
  • Use long to prevent overflow in square calculation

Solution

java
1class Solution {
2    public boolean isPerfectSquare(int num) {
3        if (num < 2) return true;
4        
5        long left = 2, right = num / 2;
6        
7        while (left <= right) {
8            long mid = left + (right - left) / 2;
9            long square = mid * mid;
10            
11            if (square == num) {
12                return true;
13            } else if (square < num) {
14                left = mid + 1;
15            } else {
16                right = mid - 1;
17            }
18        }
19        
20        return false;
21    }
22}
Loading visualizer...