0367. Valid Perfect Square

Easy | Binary Search | 24 ms (95.55%), 14.2 MB (68.22%)

❓ Problem Statement

Source: LeetCode - Valid Perfect Square GitHub: Solution / Performance

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as sqrt.

✍🏻 Constraints & Example

Constraints:

• 1 <= num <= 2^31 - 1

Input: num = 16
Output: true

Input: num = 14
Output: false

💡 Ideas

Binary Search Problem Sorted array to find a minimum number that is the square root of the input number.

Boundary / Search Space

Left (Minimum) = 1 (first version) Right (Maximum) = n (last element could be the answer)

Condition

While Loop = Left < Right Return = mid * mid == n

Return Value

True or False

🤖 Python3

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        # (base case)
        if num == 1: return 1
        
        # ==================================================
        #  Array + Binary Search                           =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)
        
        l, r = 0, num
        while l < r:
            mid = (l + r) // 2
            val = mid * mid
            
            if val == num: return True
            elif val > num: r = mid
            elif val < num: l = mid + 1
            
        return False

🤖 Java

class Solution {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */
    
    public boolean isPerfectSquare(int num) {
        /* base case */
        if(num == 1) return true;
        
        long l = 1, r = num;
        while(l < r) {
            long mid = l + (r - l) / 2;
            long val = mid * mid;
            
            if(val == num) return true;
            else if(val > num) r = mid;
            else if(val < num) l = mid + 1;
        }
        
        return false;
    }
}