☕ DSA Java Articles

Topics › Strings › Medium String Problems

String to Integer (atoi)

Medium TUF ID 974 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Implement the function myAtoi(String s), which converts the leading integer in a string to a 32-bit signed integer the way C’s atoi does:

  1. Skip any leading spaces (only the character ' ').
  2. Read one optional sign, '+' or '-'.
  3. Read digits until the first non-digit character or the end of the string. Leading zeros carry no value.
  4. If no digits were read the result is 0.
  5. If the value lies outside [-2^31, 2^31 - 1], clamp it to the nearest bound.

Constraints: 0 ≤ |s| ≤ 200; s may contain English letters, digits, spaces, '+', '-' and '.'.

Example 1

s = "   -42"
answer = -42           // spaces skipped, sign read, two digits read

Example 2

s = "4193 with words"
answer = 4193          // parsing stops at the first non-digit

Example 3

s = "-91283472332"
answer = -2147483648   // below the int range, so clamped to Integer.MIN_VALUE

Example 4

s = "words and 987"
answer = 0             // the first non-space character is not a sign or digit

The first three steps are the same in every solution, and they are the easy part. The whole difficulty of this problem is step 5: the number may not fit in the type we are building it in, and we have to notice that before it wraps around.

Approach 1: Accumulate in a long and clamp as soon as the range is left

Intuition. The natural way to build a number from digits is result = result * 10 + digit. The danger is overflow: int wraps silently, so 2147483648 would turn into a negative number. Using a long accumulator gives nine extra decimal digits of headroom, and if we compare sign * result against the int bounds after every digit we return the clamped value the moment the number steps out of range. Because we stop at the first excess digit, the long itself never gets anywhere near its own limit, even for an input like "99999999999999999999999".

Algorithm.

  1. Advance i past leading ' ' characters.
  2. If s[i] is '+' or '-', record sign and advance.
  3. While s[i] is a digit: result = result * 10 + digit; if sign * result > MAX return MAX; if sign * result < MIN return MIN; advance.
  4. Return (int) (sign * result).
static int usingLong(String s) {
    int i = 0, n = s.length();
    while (i < n && s.charAt(i) == ' ') i++;                       // 1. leading spaces (only ' ')
    int sign = 1;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {     // 2. one optional sign
        if (s.charAt(i) == '-') sign = -1;
        i++;
    }
    long result = 0;
    while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {   // 3. digits until the first non-digit
        result = result * 10 + (s.charAt(i) - '0');
        if (sign * result > Integer.MAX_VALUE) return Integer.MAX_VALUE;   // 4. clamp as soon as we overflow
        if (sign * result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        i++;
    }
    return (int) (sign * result);
}

Complexity. Time O(n): one pass. Space O(1).

The check must be inside the loop. Checking only once after the loop is a common bug: a string with twenty or more digits overflows a long just as surely as ten digits overflow an int.

Approach 2: Optimal, int only, test before multiplying

Intuition. We can avoid long entirely by asking, before we append a digit, whether result * 10 + digit would exceed Integer.MAX_VALUE. Rearranging that inequality gives a test that cannot itself overflow: result > (MAX - digit) / 10. Here is why the integer division is exact. Let q = (MAX - digit) / 10 rounded down. If result ≤ q then result * 10 + digit ≤ 10q + digit ≤ (MAX - digit) + digit = MAX, so appending is safe. If result ≥ q + 1 then result * 10 ≥ 10q + 10 > MAX - digit, so appending overflows. The test is therefore an exact “would it overflow” oracle using only int arithmetic on values that are all in range.

What about negative numbers? The most negative int is MIN = -(MAX + 1), so the magnitude of a negative result may be one larger than MAX. Our test clamps whenever the magnitude would exceed MAX, that is, whenever it would be at least MAX + 1. The only magnitude in that range that is actually representable is exactly MAX + 1, and clamping returns MIN, which is the correct answer for it. So one test serves both signs.

Algorithm.

  1. Skip spaces and read the optional sign exactly as before.
  2. For each digit: if result > (MAX - digit) / 10, return MAX for a positive sign or MIN for a negative one; otherwise result = result * 10 + digit.
  3. Return sign * result.
static int optimal(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++;
    }
    int result = 0;
    while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
        int digit = s.charAt(i) - '0';
        // result * 10 + digit > MAX  <=>  result > (MAX - digit) / 10, and MIN = -(MAX + 1) so the same test clamps negatives
        if (result > (Integer.MAX_VALUE - digit) / 10) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        result = result * 10 + digit;
        i++;
    }
    return sign * result;
}

Dry run on s = " -42":

step i character action result
skip spaces 0..2 ' ' advance 0
sign 3 '-' sign = -1 0
digit 4 '4' 0 > (MAX - 4) / 10? no; result = 4 4
digit 5 '2' 4 > (MAX - 2) / 10? no; result = 42 42
end 6   return -1 × 42 -42

Complexity. Time O(n), space O(1). This is the version to write when the interviewer asks you not to use a wider type.

Approach 3: The same parse written recursively

Intuition. The digit loop is a fold: each step takes the magnitude accumulated so far and one more character. A fold can be written as a recursive function that processes one digit and calls itself for the rest. This is how the recursion-focused rows of the sheet expect it, and it is worth seeing that the clamping logic transfers unchanged.

Algorithm.

  1. Skip spaces and read the sign iteratively (these steps have nothing to recurse over).
  2. Call parseDigits(s, i, sign, 0).
  3. parseDigits returns sign * acc if s[i] is not a digit; otherwise it computes next = acc * 10 + digit, clamps if next is out of range for the given sign, and recurses with i + 1 and next.
static int recursive(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++;
    }
    return parseDigits(s, i, sign, 0);
}

private static int parseDigits(String s, int i, int sign, long acc) {
    if (i == s.length() || s.charAt(i) < '0' || s.charAt(i) > '9') return (int) (sign * acc);
    long next = acc * 10 + (s.charAt(i) - '0');
    if (sign == 1 && next > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    if (sign == -1 && -next < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    return parseDigits(s, i + 1, sign, next);
}

Complexity. Time O(n). Space O(d) for the call stack, where d ≤ 200 is the number of digits read; the recursion is tail-recursive in shape, but Java does not eliminate tail calls, so the frames are really allocated.

Edge cases and pitfalls