What pattern does Reverse Integer use?

The Pattern: Math & Geometry (Digit-by-Digit Integer Manipulation) The Heuristic: 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.

Reverse Integer — Math & Geometry

Q: What is the time complexity of Reverse Integer?

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|).

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

Input: x = 123

Output: 321

The 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class Solution:
  def reverse(self, x: int) -> int:
      MIN = -2147483648  
      MAX = 2147483647   
      
      res = 0
      while x:
          digit = int(x % 10) if x > 0 else int(x % -10)
          x = int(x / 10)
10
          if (res > MAX // 10 or 
              (res == MAX // 10 and digit > MAX % 10)):
              return 0
          if (res < MIN // 10 or
              (res == MIN // 10 and digit < MIN % 10)):
              return 0
          res = (res * 10) + digit
          
      return res

Step-by-Step Solution

1

Define 32-bit Integer Bounds and Initialize Result

3MIN = -2147483648  
4MAX = 2147483647   
6res = 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.

2

Extract Digits and Build Reversed Integer with Overflow Checks

To iteratively extract the last digit of x and append it to res while ensuring no overflow occurs.

3

Return the Final Reversed Integer

To output the reversed integer after all digits have been processed safely.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 11 Critical

if (res > MAX // 10 or

Check 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.

Line 14 Critical

if (res < MIN // 10 or

Check 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.

Line 12 Critical

(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.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why must the algorithm check for overflow before appending the next digit rather than after?

See the answer with Pro.

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

or drill a free problem

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`