LeetCode 7 - Reverse Integer

LeetCode Problem 7

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

The problem asks us to reverse the digits of a signed 32-bit integer. Given an integer x, we must return a new integer whose digits appear in reverse order while preserving the sign.

For example, if the input is 123, reversing the digits produces 321. If the input is -123, the reversed result becomes -321. Leading zeros in the reversed number should not appear in the final answer, so reversing 120 produces 21, not 021.

The most important constraint is the requirement that the final result must remain within the signed 32-bit integer range:

• Minimum value: -2^31 = -2147483648
• Maximum value: 2^31 - 1 = 2147483647

If the reversed integer falls outside this range, we must return 0.

Another critical constraint is that the environment does not allow storing 64-bit integers. This means we cannot safely reverse the number first and then check whether it overflowed afterward. We must detect overflow before it happens.

The input is guaranteed to already fit inside the 32-bit signed integer range, so we only need to worry about overflow during the reversal process itself.

Several edge cases are important:

• Negative numbers must preserve their sign.
• Numbers ending in zero lose leading zeros after reversal.
• Very large numbers may overflow after reversal.
• Zero should simply return zero.
• The minimum 32-bit integer is especially tricky because its reversed form overflows.

Approaches

Brute Force Approach

A straightforward approach is to convert the integer into a string, reverse the string, and then convert it back into an integer.

For example:

• Convert 123 to "123"
• Reverse it into "321"
• Convert back into integer 321

For negative numbers, we can temporarily remove the sign, reverse the digits, and then restore the sign afterward.

This approach works correctly for many cases and is easy to implement. However, it violates the spirit of the problem because the problem specifically emphasizes integer manipulation and overflow handling without relying on larger integer storage.

Additionally, in languages with fixed-width integers, converting the reversed digits back into an integer may already overflow before we can validate the result.

Optimal Mathematical Approach

The better approach is to reverse the integer digit by digit using arithmetic operations.

The key insight is that we can repeatedly:

1. Extract the last digit using modulo.
2. Remove the last digit using integer division.
3. Append the extracted digit to the reversed number.

For example:

• 123 % 10 = 3
• 123 // 10 = 12
• Build reversed number incrementally.

The critical challenge is overflow detection.

Before appending a digit, we check whether multiplying the current reversed number by 10 would exceed the 32-bit integer limit. This allows us to safely avoid overflow before it occurs.

This approach satisfies all constraints and uses only constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Uses string conversion, where d is the number of digits
Optimal	O(d)	O(1)	Reverses digits mathematically with overflow checks

Algorithm Walkthrough

1. Initialize a variable reversed_num to 0. This variable will store the progressively reversed integer.
2. Define the 32-bit integer boundaries:

• INT_MAX = 2147483647
• INT_MIN = -2147483648

3. Repeat while x is not zero.
4. Extract the last digit using modulo:

• digit = x % 10

5. Remove the last digit from x using integer division:

• x = x // 10

6. In Python, negative modulo behaves differently from some other languages, so we adjust negative digits properly:

• If digit > 7, subtract 10 from digit and add 1 back to x.

7. Before updating reversed_num, check whether multiplying by 10 would overflow:

• If reversed_num > INT_MAX // 10, overflow will occur.
• If reversed_num == INT_MAX // 10 and digit > 7, overflow will occur.
• Similarly check the lower bound for negative overflow.

8. If overflow would occur, immediately return 0.
9. Otherwise, safely append the digit:

• reversed_num = reversed_num * 10 + digit

10. Continue until all digits have been processed.
11. Return reversed_num.

Why it works

At every iteration, the algorithm removes one digit from the original number and appends it to the reversed number in the correct position. The invariant is that reversed_num always contains the correctly reversed version of the digits processed so far.

The overflow checks guarantee that we never create a value outside the 32-bit signed integer range. Since every digit is processed exactly once, the final result is the correctly reversed integer if it fits within bounds, otherwise 0.

Python Solution

class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX = 2147483647
        INT_MIN = -2147483648

        reversed_num = 0

        while x != 0:
            digit = x % 10
            x = x // 10

            # Adjust for Python's modulo behavior with negatives
            if digit > 7:
                digit -= 10
                x += 1

            # Check positive overflow
            if (
                reversed_num > INT_MAX // 10 or
                (reversed_num == INT_MAX // 10 and digit > 7)
            ):
                return 0

            # Check negative overflow
            if (
                reversed_num < INT_MIN // 10 or
                (reversed_num == INT_MIN // 10 and digit < -8)
            ):
                return 0

            reversed_num = reversed_num * 10 + digit

        return reversed_num

The implementation begins by defining the 32-bit integer boundaries. These constants are used throughout the algorithm to ensure the reversed value never exceeds valid limits.

The variable reversed_num stores the reversed integer as it is constructed digit by digit.

Inside the loop, the last digit is extracted using modulo arithmetic. The original number is then shortened using integer division.

Python handles negative division and modulo differently from languages like C++ or Java. Specifically, Python's modulo operator always produces a non-negative remainder. The adjustment step corrects this behavior so that digit extraction matches the intended mathematical behavior for negative integers.

Before adding the new digit to reversed_num, the code checks whether multiplying by 10 and appending the digit would exceed the allowed integer range. If so, the function immediately returns 0.

Finally, the digit is appended to the reversed number and the process continues until all digits have been processed.

Go Solution

func reverse(x int) int {
	const INT_MAX = 2147483647
	const INT_MIN = -2147483648

	reversedNum := 0

	for x != 0 {
		digit := x % 10
		x /= 10

		// Check positive overflow
		if reversedNum > INT_MAX/10 ||
			(reversedNum == INT_MAX/10 && digit > 7) {
			return 0
		}

		// Check negative overflow
		if reversedNum < INT_MIN/10 ||
			(reversedNum == INT_MIN/10 && digit < -8) {
			return 0
		}

		reversedNum = reversedNum*10 + digit
	}

	return reversedNum
}

The Go implementation is slightly simpler because Go's integer division and modulo behavior for negative numbers already matches the desired truncation toward zero. As a result, the extra adjustment logic required in Python is unnecessary.

Overflow handling follows exactly the same logic as the Python solution. Since Go integers are fixed-width, checking before multiplication is essential to avoid invalid values.

Worked Examples

Example 1

Input: x = 123

Iteration	x Before	Digit	x After	reversed_num Before	reversed_num After
1	123	3	12	0	3
2	12	2	1	3	32
3	1	1	0	32	321

Final result: 321

Example 2

Input: x = -123

Iteration	x Before	Digit	x After	reversed_num Before	reversed_num After
1	-123	-3	-12	0	-3
2	-12	-2	-1	-3	-32
3	-1	-1	0	-32	-321

Final result: -321

Example 3

Input: x = 120

Iteration	x Before	Digit	x After	reversed_num Before	reversed_num After
1	120	0	12	0	0
2	12	2	1	0	2
3	1	1	0	2	21

Final result: 21

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Each digit is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm processes one digit per iteration, so the runtime depends linearly on the number of digits in the integer. Since a 32-bit integer contains at most 10 digits, the runtime is effectively constant in practice.

The space complexity is constant because no auxiliary data structures are allocated. Only a fixed number of variables are maintained regardless of input size.

Test Cases

solution = Solution()

assert solution.reverse(123) == 321              # basic positive number
assert solution.reverse(-123) == -321            # negative number
assert solution.reverse(120) == 21               # trailing zero removed
assert solution.reverse(0) == 0                  # zero input

assert solution.reverse(1) == 1                  # single digit positive
assert solution.reverse(-1) == -1                # single digit negative

assert solution.reverse(1534236469) == 0         # positive overflow
assert solution.reverse(-1534236469) == 0        # negative overflow

assert solution.reverse(1463847412) == 2147483641  # near upper bound
assert solution.reverse(-1463847412) == -2147483641  # near lower bound

assert solution.reverse(1000000003) == 0         # overflow after reversal
assert solution.reverse(-2147483412) == -2143847412  # valid negative reversal

assert solution.reverse(10) == 1                 # leading zero after reversal
assert solution.reverse(-10) == -1               # negative with trailing zero

Test	Why
123	Standard positive input
-123	Negative number handling
120	Removal of leading zeros after reversal
0	Smallest non-negative input
1	Single digit positive
-1	Single digit negative
1534236469	Positive overflow detection
-1534236469	Negative overflow detection
1463847412	Large valid positive reversal
-1463847412	Large valid negative reversal
1000000003	Overflow created during reversal
-2147483412	Valid negative near boundary
10	Positive trailing zero
-10	Negative trailing zero

Edge Cases

One important edge case is numbers ending in zero, such as 120. A naive implementation might incorrectly preserve leading zeros in the reversed result and produce something like 021. Since integers do not store leading zeros, the correct result is simply 21. This implementation naturally handles that because multiplying by 10 and adding digits skips insignificant leading zeros automatically.

Another critical edge case is integer overflow. For example, reversing 1534236469 produces 9646324351, which exceeds the 32-bit signed integer maximum. If overflow checks are not performed before multiplication and addition, the program may produce incorrect values or overflow internally. The implementation prevents this by checking bounds before updating reversed_num.

Negative numbers are also a common source of bugs because modulo and division behavior differs across programming languages. In Python specifically, negative modulo results differ from languages like Go or Java. The adjustment logic ensures that digit extraction behaves correctly for negative inputs, allowing the algorithm to produce accurate reversed values for cases like -123.

The minimum 32-bit integer, -2147483648, is another subtle case. Its reversed value exceeds the valid integer range. The overflow detection logic correctly identifies this condition and returns 0 before overflow occurs.