Reverse Integer
Problem
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], then return 0.
- −2³¹ ≤ x ≤ 2³¹ - 1
Example
x = 123321The algorithm extracts digits from the end of x one by one and appends them to a result integer. For input 123, digits 3, 2, and 1 are extracted in order and combined to form 321. The algorithm checks for overflow before each append to ensure the reversed integer fits in 32-bit signed range.
Approach
Straightforward Solution
A naive approach converts the integer to a string, reverses it, and converts back to integer. This is simple but inefficient and requires extra space. It also needs explicit overflow checks after reversal.
Core Observation
Reversing an integer digit-by-digit can cause overflow if the reversed number exceeds 32-bit signed integer limits. The key is to detect overflow before it happens during the iterative construction of the reversed number.
Path to Optimal
The optimal approach extracts digits using modulo and division, building the reversed number incrementally as an integer. Before appending each digit, it checks if the current reversed number is safe to multiply by 10 and add the digit without overflowing. This avoids string conversion and handles overflow proactively.
Optimal Approach
Iteratively extract the last digit of x, append it to the reversed number res by res = res * 10 + digit, and update x by integer division by 10. Before each append, check if res is within safe bounds to avoid overflow. If overflow would occur, return 0 immediately. This approach runs in O(log|x|) time and O(1) space.
Time
O(log |x|)
Each iteration removes one digit from x by division by 10, so the number of iterations is proportional to the number of digits, which is O(log |x|).
Space
O(1)
Only a fixed number of integer variables are used, with no additional data structures proportional to input size.
Pattern Spotlight
Math & Geometry (Digit-by-Digit Integer Manipulation)
When reversing or manipulating digits of an integer, build the result incrementally and check for overflow before each digit append to maintain correctness within fixed integer bounds.
Solution
| 1 | class Solution:
|
| 2 | def reverse(self, x: int) -> int:
|
| 3 | MIN = -2147483648
|
| 4 | MAX = 2147483647
|
| 5 |
|
| 6 | res = 0
|
| 7 | while x:
|
| 8 | digit = int(x % 10) if x > 0 else int(x % -10)
|
| 9 | x = int(x / 10)
|
| 10 |
|
| 11 | if (res > MAX // 10 or
|
| 12 | (res == MAX // 10 and digit > MAX % 10)):
|
| 13 | return 0
|
| 14 | if (res < MIN // 10 or
|
| 15 | (res == MIN // 10 and digit < MIN % 10)):
|
| 16 | return 0
|
| 17 | res = (res * 10) + digit
|
| 18 |
|
| 19 | return res |
Step-by-Step Solution
Define 32-bit Integer Bounds and Initialize Result
| 3 | MIN = -2147483648
|
| 4 | MAX = 2147483647
|
| 6 | res = 0
|
Objective
To establish the integer overflow boundaries and prepare the accumulator for the reversed number.
Key Insight
Explicitly defining the minimum and maximum 32-bit signed integer values allows the algorithm to perform precise overflow checks. Initializing the result to zero sets the starting point for incremental digit appending.
Interview Quick-Check
Core Logic
Defining MIN and MAX constants enables direct comparison to detect potential overflow before it happens.
State & Boundaries
Initializing res to 0 ensures a clean starting state for building the reversed integer.
Extract Digits and Build Reversed Integer with Overflow Checks
| 7 | while x:
|
| 8 | digit = int(x % 10) if x > 0 else int(x % -10)
|
| 9 | x = int(x / 10)
|
| 11 | if (res > MAX // 10 or
|
| 12 | (res == MAX // 10 and digit > MAX % 10)):
|
| 13 | return 0
|
| 14 | if (res < MIN // 10 or
|
| 15 | (res == MIN // 10 and digit < MIN % 10)):
|
| 16 | return 0
|
| 17 | res = (res * 10) + digit
|
Objective
To iteratively extract the last digit of x and append it to res while ensuring no overflow occurs.
Key Insight
Extracting digits via modulo and division avoids string conversion and allows direct arithmetic manipulation. The overflow checks compare res against MAX//10 and MIN//10 to ensure multiplying by 10 and adding the next digit stays within bounds. This proactive check is crucial because integer overflow in many languages is undefined behavior and must be prevented.
Interview Quick-Check
Core Logic
The algorithm extracts the last digit of x, then checks if appending this digit to res would overflow by comparing res to MAX//10 and MIN//10 thresholds.
State & Boundaries
The loop continues while x is non-zero, ensuring all digits are processed.
Common Pitfalls & Bugs
Failing to check overflow before appending the digit can cause incorrect results or runtime errors.
Complexity
Each iteration processes one digit, so the loop runs O(log |x|) times.
Return the Final Reversed Integer
| 19 | return res |
Objective
To output the reversed integer after all digits have been processed safely.
Key Insight
Returning res after the loop completes ensures the fully reversed integer is returned only if no overflow was detected during construction.
Interview Quick-Check
Core Logic
Returning res here provides the final reversed integer, guaranteed to be within 32-bit bounds due to prior checks.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if (res > MAX // 10 orCheck if res is greater than MAX//10 or equal and next digit exceeds MAX's last digit.
This preemptive check prevents overflow by ensuring that multiplying res by 10 and adding digit won't exceed the 32-bit signed integer maximum.
if (res < MIN // 10 orCheck if res is less than MIN//10 or equal and next digit is less than MIN's last digit.
This preemptive check prevents underflow by ensuring that multiplying res by 10 and adding digit won't go below the 32-bit signed integer minimum.
(res == MAX // 10 and digit > MAX % 10)):Check the second condition for overflow when res equals MAX//10.
This fine-grained check handles the edge case where res is exactly at the threshold, ensuring the next digit doesn't push it over the limit.
(res == MIN // 10 and digit < MIN % 10)):Check the second condition for underflow when res equals MIN//10.
This precise check handles the edge case where res is exactly at the lower threshold, ensuring the next digit doesn't push it below the limit.
res = (res * 10) + digitAppend the extracted digit to res by multiplying res by 10 and adding digit.
This line incrementally builds the reversed integer digit by digit, which is the core operation of the reversal algorithm.
digit = int(x % 10) if x > 0 else int(x % -10)Extract the last digit of x, handling positive and negative values correctly.
Using modulo with conditional sign handling ensures the correct digit is extracted regardless of x's sign, which is critical for accurate reversal.
return 0Return 0 immediately if overflow would occur on positive side.
Returning 0 here enforces the problem's requirement to signal overflow by returning zero instead of an invalid integer.
return 0Return 0 immediately if underflow would occur on negative side.
Returning 0 here enforces the problem's requirement to signal underflow by returning zero instead of an invalid integer.
MIN = -2147483648Define the minimum 32-bit signed integer value.
Explicitly setting MIN allows the algorithm to check for underflow conditions before they occur, ensuring correctness within fixed integer limits.
MAX = 2147483647Define the maximum 32-bit signed integer value.
Explicitly setting MAX enables precise overflow detection, which is essential to prevent invalid reversed integers.
return resReturn the fully reversed integer after processing all digits.
Returning res here provides the final answer, guaranteed to be within 32-bit bounds due to prior overflow checks.
while x:Continue looping while x is not zero to process all digits.
This loop condition ensures every digit of the input integer is extracted and processed exactly once.
x = int(x / 10)Remove the last digit from x by integer division.
Dividing x by 10 truncates the last digit, preparing for the next iteration to process the remaining digits.
res = 0Initialize the accumulator for the reversed integer to zero.
Starting with zero provides a clean state to build the reversed number incrementally by appending digits.
Test Your Understanding
Why must the algorithm check for overflow before appending the next digit rather than after?
Because appending the digit might cause the integer to overflow beyond 32-bit limits, which leads to undefined behavior or incorrect results. Checking beforehand ensures the operation is safe and prevents invalid states.
Related Problems
Math pattern
Don't just read it. Drill it.
Reconstruct Reverse Integer from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reverse Integer drill