LeetCode 8 – String to Integer (atoi)

String to Integer (atoi) has almost no algorithm in it. It is a specification-reading exercise dressed as a coding problem, and it is asked precisely because sloppy engineers skim the spec and sloppy engineers write parsers that eat production data. Read the rules, write them down as steps, then implement the steps in order.

The problem

Convert the leading numeric portion of a string to a 32-bit signed integer, following the rules of C's atoi:

1. Skip any leading spaces.
2. Take an optional single + or -.
3. Read digits until a non-digit or the end of the string.
4. If no digits were read, return 0.
5. Clamp the result into [-2³¹, 2³¹ - 1] — clamp, do not return 0.

"42"               ->  42
"   -42"           -> -42        leading spaces skipped
"4193 with words"  ->  4193      stops at the space
"words and 987"    ->  0         the first non-space is not a sign or digit
"-91283472332"     -> -2147483648  clamped to INT_MIN, not 0
"+-12"             ->  0         only one sign is allowed
"  0000123"        ->  123       leading zeros are just digits

Clamp, do not reject

This is the one rule that differs from Reverse Integer, and mixing the two up is the most common way to fail this problem after writing otherwise correct code. Reverse Integer returns 0 on overflow. Atoi saturates: too large becomes 2³¹ - 1, too small becomes -2³¹.

The steps, in order

Every rule maps to one small block, and the order they run in is the specification. Resist the urge to merge them — a single pass with a state machine is fine once you have done this a hundred times, but the four-block version is what you should write on a whiteboard because each block is independently verifiable.

The overflow check is the same rearranged inequality as in Reverse Integer: overflow means result * 10 + digit > Integer.MAX_VALUE, and dividing through by 10 turns it into a comparison whose own arithmetic stays in range. The moment it trips, you can return immediately — more digits can only make it worse.

Because |INT_MIN| is one larger than INT_MAX, checking against Integer.MAX_VALUE and then returning Integer.MIN_VALUE for a negative number is exactly right, and it costs no extra case. The input "-2147483648" trips the check on its last digit and returns Integer.MIN_VALUE, which happens to be the correct answer anyway.

Java

class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();

        // 1. leading spaces
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        if (i == n) {
            return 0;                       // nothing but spaces
        }

        // 2. optional single sign
        int sign = 1;
        char c = s.charAt(i);
        if (c == '+' || c == '-') {
            sign = (c == '-') ? -1 : 1;
            i++;
        }

        // 3. digits, clamping as we go
        int result = 0;
        while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            int digit = s.charAt(i++) - '0';

            // result * 10 + digit > MAX_VALUE, rearranged so it cannot overflow itself
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + digit;
        }

        // 4. no digits read leaves result at 0, which is already the answer
        return sign * result;
    }
}

Python

Two Python-specific traps. str.isdigit() is True for non-ASCII digits such as '٣' and for superscripts like '²', neither of which int() handles the way you want — compare the character against '0' and '9' instead. And since Python integers never overflow, the clamp moves to the end:

class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1
        i, n = 0, len(s)

        while i < n and s[i] == ' ':                 # 1. leading spaces
            i += 1

        sign = 1
        if i < n and s[i] in '+-':                   # 2. optional single sign
            sign = -1 if s[i] == '-' else 1
            i += 1

        result = 0
        while i < n and '0' <= s[i] <= '9':          # 3. digits — not str.isdigit()
            result = result * 10 + (ord(s[i]) - ord('0'))
            i += 1

        return max(INT_MIN, min(INT_MAX, sign * result))   # 4. clamp, do not reject

Complexity

O(n) time in the length of the string, O(1) space. Every character is looked at once, and the loops only ever move forward.

Why not a regular expression

The whole spec fits in one pattern — ^\s*([+-]?\d+) — and in real code that is probably what you would write. In an interview it is the wrong answer: it hands the parsing back to the library, which is the exact thing being tested. Worse, parsing the captured group with Integer.parseInt throws on overflow instead of clamping, so you still have to write the saturation logic by hand. Mention that the one-liner exists, then write the loop.

What the interviewer is checking

• That you clamp instead of returning 0, and that you noticed this differs from Reverse Integer.
• That you detect overflow before it happens, not after — no long, no double.
• That "+-12", " ", "" and "words 987" all return 0 without a crash.
• That only ' ' counts as whitespace here — "\t42" returns 0, because the tab is neither a space, a sign, nor a digit.
• That you asked about the rules rather than assuming them. This problem is worded ambiguously on purpose.