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

💡 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