Reverse Integer LeetCode 7 Deep Dive

LeetCode 7 — Reverse Integer — gives you a signed 32-bit integer x and asks you to return x with its digits reversed. If the reversed integer overflows the 32-bit signed integer range [-2^31, 2^31-1] (i.e., outside [-2147483648, 2147483647]), return 0. The problem assumes the environment does not allow storing 64-bit integers, which means you cannot simply compute the reversal in a wider type and check afterward — you must detect overflow proactively before it occurs.

The examples clarify the behavior: 123 reverses to 321, -123 reverses to -321, and 120 reverses to 21 (the trailing zero is dropped automatically). The sign is preserved in the reversal. The overflow case: 1534236469 reversed is 9646324351, which exceeds INT_MAX = 2147483647, so the return value is 0. The challenge is implementing this reversal efficiently — O(log10(n)) time, O(1) space — while correctly handling negatives, trailing zeros, and overflow detection without using 64-bit arithmetic.

The pop-and-push pattern is the standard approach. It works by treating the integer as a stack of digits: pop the last digit off x using the modulo operator, push it onto the result using multiplication and addition. Repeat until x is zero. Because each pop removes one digit and each push adds one digit to the reversed number, the algorithm processes all digits in O(log10(n)) iterations — one per digit in x.

The core algorithm uses two operations repeated in a loop. Pop the last digit: digit = x % 10, then remove it from x with integer division x = x / 10 (truncating toward zero). Push digit onto the result: result = result * 10 + digit. Repeat while x is not zero. When the loop terminates, result holds the digits of x in reversed order. Trailing zeros in x become leading zeros in the reversed result and naturally disappear because leading zeros are not stored.

This works because multiplying result by 10 shifts all existing digits one place left (creates a new ones place), and adding digit fills the new ones place. After the first iteration result = digit_1 (last digit of x). After the second iteration result = digit_1 * 10 + digit_2 (second-to-last digit of x). Each iteration prepends the next-to-last remaining digit. The process is exactly the mirror of how positional decimal notation works.

The loop terminates when x becomes 0 after all digits have been popped. For positive integers this is straightforward. For negative integers, x % 10 gives a negative remainder in most languages (Java, C++): -123 % 10 = -3. The push operation result = result * 10 + digit then correctly builds -321 because all intermediate results are negative. In Python the behavior differs — Python % always returns a non-negative result for positive divisors — requiring explicit handling described in the negatives section.

The overflow check must happen before computing result = result * 10 + digit, not after. If you perform the multiplication first and the result overflows, the value is undefined in C/C++ or wraps silently in Java — you cannot recover the true mathematical value to check it. The safe check compares result against INT_MAX / 10 = 214748364 and INT_MIN / 10 = -214748364 before multiplying.

For positive overflow: if result > INT_MAX / 10, then result * 10 will exceed INT_MAX regardless of digit. If result == INT_MAX / 10, then result * 10 + digit overflows only if digit > 7 (because INT_MAX = 2147483647, and the last digit of INT_MAX is 7). So the positive overflow condition is: result > 214748364 OR (result == 214748364 AND digit > 7).

For negative overflow: if result < INT_MIN / 10, then result * 10 will underflow INT_MIN. If result == INT_MIN / 10, overflow happens only if digit < -8 (because INT_MIN = -2147483648, and the last digit is -8). So the negative overflow condition is: result < -214748364 OR (result == -214748364 AND digit < -8). When either overflow condition is met, return 0 immediately without performing the push.

In C and C++, signed integer overflow is undefined behavior. The compiler is permitted to assume it never occurs and can optimize accordingly, producing incorrect results that do not even resemble a wrap-around. In Java, integer arithmetic wraps silently modulo 2^32 — so overflowing INT_MAX wraps to a large negative number that looks valid but is wrong. In both cases, checking after the overflow has already occurred yields an unreliable or meaningless value.

By checking before the push, you ensure that result * 10 + digit is always computed only when the mathematical result is known to fit in 32 bits. This makes the overflow check correct by construction: you examine the pre-push state (which is always valid because you checked before the previous push too) and only proceed when the next push is safe.

The condition result > INT_MAX / 10 uses integer division which truncates: 2147483647 / 10 = 214748364 with remainder 7. So INT_MAX / 10 in integer arithmetic is 214748364. Any result strictly greater than this, when multiplied by 10, will exceed INT_MAX regardless of the digit. The digit-level check only matters for the boundary case where result equals exactly 214748364.

In Java and C++, the % operator returns a remainder with the same sign as the dividend. So -123 % 10 = -3 (not 7). This means the pop-and-push loop naturally handles negative integers without special treatment: the digits are popped as negative values (-3, -2, -1) and pushed as negative contributions. The final result -321 is built correctly. The overflow check on the negative side uses the same structure but with INT_MIN / 10 as the threshold.

In Python, the % operator always returns a non-negative result when the divisor is positive. So -123 % 10 = 7 in Python, not -3. This is mathematically consistent with Python's floor division, but it means the pop-and-push loop does not naturally handle negatives. The standard Python solution is to work with the absolute value: pop digits from abs(x), build the result as a positive number, then restore the sign at the end with a sign multiplier.

An alternative Python approach is to strip the sign, convert to string, reverse the string, convert back to int, restore the sign, and then clamp. This sidesteps the modular arithmetic entirely but uses O(log n) string storage. For interview purposes, the pop-and-push approach with abs() handling demonstrates deeper understanding of the algorithm and is preferred over the string trick.

Java implementation with direct pop-push and overflow check: public int reverse(int x) { int result = 0; while (x != 0) { int digit = x % 10; x /= 10; if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) return 0; if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) return 0; result = result * 10 + digit; } return result; } Java's % operator preserves sign for negatives, so this works for both positive and negative x without special cases. Time: O(log10(n)), space: O(1).

Python implementation using abs() to avoid Python's unsigned modulo: def reverse(self, x: int) -> int: sign = -1 if x < 0 else 1; x = abs(x); result = 0; while x != 0: digit = x % 10; x //= 10; result = result * 10 + digit; result = sign * result; return result if -2**31 <= result <= 2**31 - 1 else 0. Note the use of //= for floor division (ensuring integer result), and the final range check instead of per-step overflow detection since Python integers never overflow natively.

Both implementations run in O(log10(n)) time — there are exactly as many iterations as there are digits in x — and use O(1) extra space. No strings, arrays, or auxiliary data structures are used. The Java version detects overflow before each push; the Python version performs one range check at the end. Both approaches correctly handle 0, positive, negative, single-digit, and MAX/MIN boundary inputs.

String to Integer (atoi) — LeetCode 8 — is a sibling problem that also processes digits one at a time with overflow detection. Instead of reversing, atoi builds an integer from a string left-to-right by multiplying the accumulator by 10 and adding each new digit, with the same pre-multiplication overflow check: if result > INT_MAX / 10 or (result == INT_MAX / 10 and digit > 7), clamp and return. The overflow logic is nearly identical to Reverse Integer.

Palindrome Number — LeetCode 9 — can be solved by reversing only the second half of the digits and comparing to the first half. This uses the same pop-and-push digit technique but terminates halfway through, avoiding the overflow problem entirely since the half-reversal of a palindrome candidate never grows larger than the original number. Pow(x, n) — LeetCode 50 — is another integer math problem involving repeated multiplication and careful handling of overflow and negative exponents.

The integer manipulation family — LeetCode 7, 8, 9, 50 — covers the core digit-level operations that appear repeatedly in interview problems: pop-and-push reversal, digit-by-digit parsing, overflow detection before multiplication, and sign handling. Mastering these four problems equips you with the complete toolkit for integer manipulation questions. They also frequently appear as subroutines in larger problems involving number theory, bit manipulation, and mathematical reasoning.