LeetCode 7: Reverse Integer Solution in Python

This tutorial examines the Python solution to LeetCode’s Reverse Integer problem, highlighting its linear time and space complexity, O(n), based on the input’s string length.



In the Python solution code below for solving the Reverse Integer LeetCode problem, a class named Solution is first defined with a method called reverse. This is available in LeetCode’s code editor by default if the Python 3 language is selected. The reverse method is designed to take an integer x and return the reversed version of it.

The process begins by converting the integer into a string, making it easier to reverse. For positive numbers, the string is simply reversed using Python’s slicing feature. However, for negative numbers, the method is a bit more nuanced; it reverses the string while leaving out the negative sign, and then reattaches the sign to ensure the final number retains its original sign.

class Solution:
    def reverse(self, x: int) -> int:
        num_str= str(x)
        # Reverse it (careful with negative sign)
        if x >= 0:
            num_str = num_str[::-1]
            num_str = "-" + num_str[:0:-1]
        If reversing the value causes it to go outside the signed 32-bit integer range, return 0.
        large = 2**31 - 1
        small = -2**31

        reversed_num = int(num_str)
        if reversed_num > large or reversed_num < small:
            return 0
            return reversed_num

The solution also carefully addresses the limitations associated with a 32-bit signed integer. It sets up boundaries to check if the reversed number falls within the acceptable range. If the reversed number is larger or smaller than these limits, the method returns 0, indicating that an overflow has occurred. Otherwise, the reversed number, now safely within the range, is returned. This approach is both effective and meticulous, ensuring that the integer is reversed correctly while also taking into account the potential for overflow, all through the use of string manipulation and conditional logic.

Screenshot of my Python solution for Reverse Integer on LeetCode, which beats 90% of other submissions for execution time and 71% for memory usage.

Reverse Integer Complexity Analysis

The time complexity of the solution is O(n), where n is the length of the integer’s string representation, dominated by the string reversal process.

The space complexity is also O(n), primarily due to the memory required for storing the string representation of the integer. Additional variables used for checking overflow contribute only a constant O(1) space, making the space requirement linear in relation to the integer’s digit count.


Exit mobile version