LeetCode 7. Reverse Integer

https://leetcode.com/problems/reverse-integer/description/




• Integer.MAX_VALUE = 2,147,483,647 = 231 - 1
• Integer.MIN_VALUE = -2,147,483,648 = -231

• -231 <= x <= 231 - 1

Time Complexity (TC) Classification Table for This Problem

Complexity Class	Example Explanation	Does It Apply?
O(1)	Constant time, independent of input size	No
O(log n)	Number of digits in integer ~ log₁₀	x
O(n)	Linear time with respect to input size	No
O(n log n)	Sorting or divide-and-conquer style algorithms	No
O(n²)	Nested loops over input	No
O(2^n)	Exponential, e.g. subset problems	No
O(n!)	Factorial time, permutations	No

Note: The number of digits in an integer x is approximately log₁₀|x|. The loop runs once per digit, so TC is O(log n).

 

package jan25;

public class ReverseInteger {
    public static void main(String[] args) {
        int x = 1534236469;
        System.out.println(reverse(x));  // Output: 0 (due to overflow)
    }

    /**
     * Reverses digits of an integer, returns 0 if overflow occurs.
     *
     * Time Complexity: O(log₁₀|x|) — proportional to the number of digits in x
     * Space Complexity: O(1) — uses a fixed amount of extra space
     */
    public static int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int temp = x % 10;
            x /= 10;

            // Overflow check before multiplying by 10 and adding digit
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && temp > 7))
                return 0;

            // Underflow check (for negative numbers)
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && temp < -8))
                return 0;

            rev = rev * 10 + temp;
        }
        return rev;
    }
}

Why? If rev > (Integer.MAX_VALUE - temp) / 10, then:
rev * 10 + temp > Integer.MAX_VALUE
which would cause overflow.


Case
Time Complexity
Space Complexity
Explanation
Best
O(1)
O(1)
Single-digit input exits loop quickly.
Average
O(log n)
O(1)
Number reversed digit-by-digit (most inputs).
Worst
O(log n)
O(1)
Full integer with max digits reversed, overflow checks happen.