Approach: Binary search on the root

def isPerfectSquare(n):
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        sq = mid * mid
        if sq == n: return True
        if sq < n: lo = mid + 1
        else: hi = mid - 1
    return False

Complexity: O(log n) time, O(1) space.

Full Solution — all languages

class Solution:
    def isPerfectSquare(self, n):
        lo, hi = 1, n
        while lo <= hi:
            mid = (lo + hi) // 2
            sq = mid * mid
            if sq == n:
                return True
            if sq < n:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

import java.util.*;
class Solution {
    public boolean isPerfectSquare(int n) {
        long lo = 1, hi = n;
        while (lo <= hi) {
            long mid = (lo + hi) / 2;
            long sq = mid * mid;
            if (sq == n) return true;
            if (sq < n) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: bool isPerfectSquare(int n) {
        long long lo = 1, hi = n;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            long long sq = mid * mid;
            if (sq == n) return true;
            if (sq < n) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
};

/**
 * @param {number} n
 * @return {boolean}
 */ var isPerfectSquare = function(n) {
    let lo = 1, hi = n;
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        const sq = mid * mid;
        if (sq === n) return true;
        if (sq < n) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
};

Valid Perfect Square

Example 1

Example 2

Example 3

Constraints