8. String to Integer (atoi)

Process the string in four phases: skip spaces, read an optional sign, accumulate digits, and clamp to the 32-bit range.

Four phases

1. Skip leading spaces.
2. Read an optional +/- sign.
3. Read consecutive digits, building num = num*10 + digit.
4. Apply the sign and clamp to [-2^31, 2^31-1].

Stop at the first non-digit. If no digit was read, the answer is 0.

Worked example

" -42" → skip spaces, sign -, digits 42 → -42. "4193 with words" → 4193.

Complexity

• Time: O(n).
• Space: O(1).

class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        while (i < n && s.charAt(i) == ' ') i++;
        int sign = 1;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            if (s.charAt(i) == '-') sign = -1;
            i++;
        }
        long num = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            num = num * 10 + (s.charAt(i) - '0');
            i++;
            if (sign == 1 && num > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (sign == -1 && -num < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        return (int) (sign * num);
    }
}