Reverse Integer

LeetCode 7: Reverse Integer Solution & Explanation

Problem Overview

TL;DR: Extract digits from right to left, append each digit to a result accumulator, and check 32-bit overflow before every multiplication by 10.

LeetCode 7, Reverse Integer, asks you to reverse the decimal digits of a signed integer while preserving its sign. Leading zeroes in the reversed representation disappear naturally, and any result outside the signed 32-bit integer range must produce 0.

The main challenge is performing the reversal without relying on 64-bit integers. This makes overflow detection part of the algorithm rather than an afterthought. The resulting LeetCode 7 Solution is a popular interview question because it tests arithmetic simulation, boundary handling, and careful integer operations.

Brute Force Approach for Reverse Integer

A straightforward approach is to treat the number as a string:

1. Convert the integer to its decimal string representation.
2. Preserve the sign separately.
3. Reverse the digit portion.
4. Convert the reversed string back to an integer.
5. Return 0 if the converted value does not fit in the signed 32-bit range.

For example, -804 can be processed as:

• Sign: -
• Digits: "804"
• Reversed digits: "408"
• Result: -408

Naive Pseudocode

function reverse(x):
    sign = negative if x < 0, otherwise positive
    digits = decimal digits of absolute value of x
    reverse digits
    result = convert reversed digits back to an integer
    apply sign

    if result is outside [-2^31, 2^31 - 1]:
        return 0

    return result

Why This Approach Is Not the Preferred Solution

The string approach processes only a small number of digits, so its asymptotic time complexity is not poor. However, it does not address the central constraint cleanly:

• Converting the reversed string back to an integer can overflow before the range check is performed.
• On platforms without 64-bit integers, an intermediate numeric conversion may be invalid.
• A numeric reversal implementation that repeatedly computes result = result * 10 + digit without checking first can trigger signed integer overflow, which is undefined behavior in C++.
• The approach uses extra memory for the string even though the digits can be processed directly from the integer.

The optimal solution extracts digits arithmetically and validates each update before it can overflow.

Algorithm Strategy: Two Pointers

Use arithmetic operations to simulate the reversal process associated with the String Reversal subpattern.

Maintain:

• The unprocessed portion of the input number.
• The reversed result constructed so far.
• The next digit extracted from the right side.
• The appropriate 32-bit limit based on the sign.

At each step, remove one digit from the input and append it to the result. Before appending, verify that multiplying the current result by 10 and adding the digit will remain within the signed 32-bit range.

If the update would exceed the range, return 0 immediately.

Execution Flow

1. Determine whether the input is positive or negative when using the sign-separated implementation.
2. Store the absolute magnitude as the remaining value to process.
3. Select the corresponding upper limit:
   • 2,147,483,647 for positive results.
   • 2,147,483,648 for negative results.
4. While unprocessed digits remain:
   • Extract the last digit with % 10.
   • Remove that digit with integer division by 10.
   • Check whether the current reversed value can safely receive the digit.
   • Append the digit using reversedValue = reversedValue * 10 + digit.
5. Reapply the original sign.
6. Return the result.
7. If any boundary check fails, return 0.

For the C++ implementation, the sign is retained directly in the extracted digits. Therefore, both positive and negative overflow conditions are checked explicitly.

Proof of Correctness

We prove that the algorithm returns the reversed integer when it fits in the signed 32-bit range and returns 0 otherwise.

Digit Processing

At every iteration, x % 10 produces the rightmost unprocessed decimal digit. Integer division by 10 removes exactly that digit. Therefore, each input digit is processed once and in right-to-left order.

Result Construction

Assume result contains the reversal of all digits processed before the current iteration. Appending the newly extracted digit with:

result = result * 10 + digit

places the new digit at the rightmost position of the partial reversal. Thus, the invariant remains true after every safe update.

Overflow Handling

Before each update, the algorithm determines whether the current result can be multiplied by 10 and extended by the next digit without exceeding the relevant 32-bit boundary.

• If the update is safe, the invariant is preserved.
• If the update is unsafe, the final reversed number is outside the allowed range, so returning 0 is correct.

When all digits are processed, the invariant states that result is exactly the reversed decimal value. Since every update was verified as safe, the returned value lies within the required range.

Therefore, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 344: Reverse String
• LeetCode 151: Reverse Words in a String
• LeetCode 541: Reverse String II
• LeetCode 345: Reverse Vowels of a String

These problems use directional movement across a sequence to exchange or reconstruct elements in reverse order. LeetCode 344 uses two indices that move inward, LeetCode 151 reverses word segments, LeetCode 541 reverses selected intervals, and LeetCode 345 moves inward while skipping non-vowels. Reverse Integer applies the same reversal concept to decimal digits through arithmetic extraction rather than literal string pointers.

Reference Implementation

C++ Solution for LeetCode 7

1class Solution {
2public:
3    int reverse(int x) {
4        int result = 0;
5
6        while (x != 0) {
7            int digit = x % 10;
8            x /= 10;
9
10            if (result > 214748364 ||
11                (result == 214748364 && digit > 7)) {
12                return 0;
13            }
14            if (result < -214748364 ||
15                (result == -214748364 && digit < -8)) {
16                return 0;
17            }
18
19            result = result * 10 + digit;
20        }
21
22        return result;
23    }
24};

This version keeps the sign inside the digit values. For negative inputs, % 10 produces negative digits, so the negative boundary must be checked separately.

Java Solution for LeetCode 7

1class Solution {
2    public int reverse(int x) {
3        int sign = x < 0 ? -1 : 1;
4        long remaining = x < 0 ? -(long) x : (long) x;
5        long limit = sign < 0 ? 2147483648L : 2147483647L;
6        long reversedValue = 0;
7
8        while (remaining != 0) {
9            long digit = remaining % 10;
10            remaining /= 10;
11
12            if (reversedValue > (limit - digit) / 10) {
13                return 0;
14            }
15            reversedValue = reversedValue * 10 + digit;
16        }
17
18        return (int) (sign * reversedValue);
19    }
20}

This implementation separates the sign from the magnitude. It uses long for intermediate calculations so the absolute value of Integer.MIN_VALUE can be represented safely during processing. The final returned value is still a 32-bit int.

Python Solution for LeetCode 7

1class Solution:
2    def reverse(self, x: int) -> int:
3        sign = -1 if x < 0 else 1
4        remaining = abs(x)
5        limit = 2_147_483_648 if sign < 0 else 2_147_483_647
6        reversed_value = 0
7
8        while remaining:
9            digit = remaining % 10
10            remaining //= 10
11
12            if reversed_value > (limit - digit) // 10:
13                return 0
14            reversed_value = reversed_value * 10 + digit
15
16        return sign * reversed_value

Python integers do not overflow during normal arithmetic, but the explicit limit check is still required because the problem defines a 32-bit result range.