LeetCode 7 Solution: Reverse Integer

The LeetCode 7 solution seems simple, but when you’re dealing with constraints like 32-bit signed integers, things get tricky. LeetCode’s Reverse Integer problem asks us to reverse the digits of an integer, but we also need to watch out for overflow. In this post, I’ll walk you through two solutions: one using string manipulation (with a catch) and a better solution using arithmetic that avoids overflow issues.

Let’s dive in!

---

Problem Breakdown: What Are We Trying to Solve?

The Reverse Integer problem is pretty straightforward at first glance:

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], return 0.

The catch here is that we’re dealing with signed 32-bit integers. The possible range for these integers is from -2^31 to 2^31 - 1, or [-2147483648, 2147483647]. If our reversed number goes beyond this range, we must return 0.

For example:

• Input: 123 → Output: 321
• Input: -123 → Output: -321
• Input: 1534236469 → Output: 0 (because reversing gives 9646324351, which exceeds the 32-bit integer range).

---

The Initial (Flawed) Approach: String Reversal

A common first attempt at this problem involves converting the integer into a string, reversing it, and converting it back into an integer. It’s simple and works for many cases. Here’s how we’d approach it:

LeetCode 7 – String-Based Solution:

def reverse(x: int) -> int:
    # Define the 32-bit integer range boundaries
    INT_MIN, INT_MAX = -2**31, 2**31 - 1

    # Handle the sign of x and work with its absolute value
    sign = -1 if x < 0 else 1
    x_abs = abs(x)

    # Reverse the digits by converting to a string, reversing, and converting back to an integer
    reversed_x = int(str(x_abs)[::-1])

    # Restore the original sign to the reversed number
    reversed_x *= sign

    # Check for 32-bit overflow
    if reversed_x < INT_MIN or reversed_x > INT_MAX:
        return 0

    return reversed_x

How This Works:

• Step 1: Handle the sign of x. We’ll reverse the digits of the absolute value and then multiply the result by -1 if the number was negative.
• Step 2: Convert the absolute value of x to a string, reverse the string using Python’s slicing ([::-1]), and convert it back into an integer.
• Step 3: Before returning the result, check if the reversed number falls within the 32-bit signed integer range. If not, return 0.

Why It Fails for Large Numbers:

This approach works for small numbers, but it breaks for numbers close to the 32-bit integer limit. For example, consider the maximum 32-bit integer 2147483647. Reversing it gives 7463847412, which exceeds the allowed 2^31 - 1 range. Converting this result back into an integer would still cause overflow.

Key Flaw: By reversing the number as a string, we don’t immediately detect overflow during the reversal process. Thus, even though we perform the range check after reversing, it’s too late.

---

A Better Approach: Arithmetic Solution (Digit-by-Digit Reversal)

To solve the overflow issue, we need to avoid converting the number to a string. Instead, we can reverse the number digit-by-digit, keeping track of the number’s size as we go. This allows us to check for overflow before the final reversed number is fully constructed.

Arithmetic-Based Solution:

def reverse(x: int) -> int:
    # Define the boundaries for a 32-bit signed integer
    INT_MIN, INT_MAX = -2**31, 2**31 - 1

    result = 0
    sign = -1 if x < 0 else 1
    x = abs(x)

    while x != 0:
        # Extract the last digit
        digit = x % 10
        x //= 10

        # Check for overflow before adding the digit
        if result > (INT_MAX - digit) // 10:
            return 0

        # Add the digit to the reversed result
        result = result * 10 + digit

    return result * sign

Explanation:

1. Sign Handling: We first determine whether x is positive or negative. Then we work with the absolute value of x and apply the sign later.
2. Extracting Digits: We repeatedly extract the last digit of x using the modulo operation (x % 10). After extracting the digit, we remove it from x by dividing x by 10 (using integer division x //= 10).
3. Reconstructing the Reversed Number: We start with an empty result (result = 0) and keep appending the extracted digits to this result by multiplying the current result by 10 and adding the new digit.
4. Overflow Check: Before appending the new digit, we check whether this operation would cause the result to overflow beyond 2147483647. If appending the new digit causes overflow, we return 0.

Why It Works:

By handling the digits one by one, we can catch potential overflow before it happens. Specifically, we check if the result exceeds the threshold where multiplying it by 10 (to add a new digit) would cause overflow.

---

Comparing the Two Approaches

1. String-Based Reversal:

   • Pros: Simple to implement, easy to understand.
   • Cons: Fails to detect overflow during reversal and breaks for large inputs near the 32-bit boundary.

2. Arithmetic-Based Reversal:

   • Pros: Handles overflow gracefully by checking at each step, no string conversion needed, avoids unnecessary operations.
   • Cons: Slightly more complex, requires careful handling of overflow during digit-by-digit reconstruction.

---

Time and Space Complexity Analysis

• Time Complexity: Both solutions have O(n) time complexity, where n is the number of digits in the number x. We process each digit exactly once.

• Space Complexity: The string-based solution uses O(n) space due to the string conversion and slicing. The arithmetic solution uses O(1) space, as it only uses a few integer variables.

Clearly, the arithmetic solution is superior in terms of both correctness and space efficiency.

---

LeetCode 7 Solution: Summary

While reversing an integer might seem like a straightforward task, it’s easy to run into problems when dealing with constraints like 32-bit integer overflow. The string-based approach is simple but falls short when handling large numbers. By using an arithmetic approach, we can reverse the digits of the number while avoiding overflow, making our solution more robust.

Whenever you’re dealing with integer constraints in coding problems, it’s important to keep an eye out for overflow and ensure your solution handles edge cases gracefully. Mastering this problem will help you tackle similar challenges in the future!

Happy coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.