Readable Python solution [250ms]


  • 0
    class Solution(object):
        def isPalindrome(self, x):
            """
            :type x: int
            :rtype: bool
            
            Time: O(log x)
            Space: O(1)
            
            """
            # Negative numbers are not palindromes
            if x < 0:
                return False
                
            # Find highest digit
            h = 10
            while x >= h:
                h *= 10
            h //= 10
            
            # Compare opposing digits
            l = 1
            while l < h:
                if x // h % 10 != x // l % 10:
                    # Not palindrome
                    return False
                l *= 10
                h //= 10
            
            # Palindrome
            return True
    

    Complexity:

    • Time: O(log x)
    • Space: O(1)

    No hidden space complexity in the above solution. As a contrast, the following one-liner solution would construct a temporary list of digits, therefore has O(log x) space complexity: return str(x) == ''.join(reversed(str(x)))


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.