Leftmost bisect search to find valid perfect square

Question

I am working on Valid Perfect Square - LeetCode and wrote a standard leftmost bisect search to solve the problem:

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        #base case 1
        if num == 1: return True 
        lo = 1
        hi = num
        #recur case 
        while lo < hi:
            mid = (lo + hi) // 2
            if num > mid ** 2:
                lo = mid + 1
            else:
                hi = mid 
        return True if lo ** 2 == num else False

However, the score is annoying:

Runtime: 48 ms, faster than 24.22% of Python3 online submissions for Valid Perfect Square. Memory Usage: 13.2 MB, less than 5.17% of Python3 online submissions for Valid Perfect Square.

I am not able to improve a standard template a little bit.

Could you please provide any advice?

Answer 1

Some small points:

ternary expression

No need for return True if lo ** 2 == num else False. you can use just return lo ** 2 == num

early return

If mid**2 == num, you can return early:

sq = mid ** 2
if num == sq:
    return True
if num > sq:
    lo = mid + 1
else:
    hi = mid -1

returns early in this case. This reduced the time for me to 36ms.

unpacking

If you want, you can use a ternary expression and tuple unpacking to redefine hi and lo

lo, hi = (mid + 1, hi) if num > sq else (lo, mid - 1)

but this is a matter of taste, and doesn't seem to save any time or memory.

memory

I don't see a lot of ways in which to reduce this method's memory usage. If you look at the distribution of all submissions, almost all use this bisect method, so memoty reduction will be based on the wims of the VM.