String to Integer (atoi)

Implement myAtoi(s), which reads a 32-bit signed integer from the start of the string s by following these rules in order:

• Spaces: skip any leading space characters ' '.
• Sign: if the next character is '+' or '-', read it; it decides the sign. With no sign character the number is positive. At most one sign character is allowed.
• Digits: read consecutive digits 0-9 and stop at the first non-digit character or at the end of the string. Leading zeros are allowed. Everything after that point is ignored.
• Result: if no digits were read, return 0. Otherwise apply the sign and, if the value lies outside [-2³¹, 2³¹ − 1], clamp it to the nearest end of that range.

Example 1

Example 2

Example 3

Constraints

• 0 <= s.length <= 200
• s consists of English letters, digits, spaces, '+', '-' and '.'

Pattern Path · Math, Bits & Strings · problem 37 of 169

Start simple

Use a regular expression to extract the prefix and a big-integer conversion, then clamp: O(n), but it hides the logic the interviewer wants to see and breaks the 32-bit rule.

The key idea

Walk the string once with an index i, applying each rule in turn: advance past spaces, read at most one sign, then consume digits. Every character is looked at no more than once, so the work is linear.

The interesting part is overflow. In a language with fixed-width integers, value * 10 + digit can overflow before you get a chance to clamp. The fix is to test before updating: with LIMIT = 231 − 1, the update is unsafe exactly when value > (LIMIT - digit) / 10. At that point the true magnitude already exceeds the range, so return INT_MAX for a positive sign or INT_MIN for a negative one; no later digit can bring it back. Note that −2³¹ itself is reached through this clamp, since its magnitude is one more than LIMIT.

Stopping at the first non-digit also handles inputs like "+-5" (the second sign is not a digit, so the answer is 0) and " " (no digits, answer 0).

Complexity

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

Python

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

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

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

        value = 0                            # 3. digits
        while i < n and s[i].isdigit():
            digit = ord(s[i]) - ord('0')
            # Would value * 10 + digit exceed INT_MAX? Then clamp now.
            if value > (INT_MAX - digit) // 10:
                return INT_MAX if sign == 1 else INT_MIN
            value = value * 10 + digit
            i += 1

        return sign * value

JavaScript

var myAtoi = function(s) {
  const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
  let i = 0;
  const n = s.length;

  while (i < n && s[i] === ' ') i++;      // 1. skip leading spaces

  let sign = 1;                            // 2. optional sign
  if (i < n && (s[i] === '+' || s[i] === '-')) {
    if (s[i] === '-') sign = -1;
    i++;
  }

  let value = 0;                           // 3. digits
  while (i < n && s[i] >= '0' && s[i] <= '9') {
    const digit = s.charCodeAt(i) - 48;
    // Would value * 10 + digit exceed INT_MAX? Then clamp now.
    if (value > Math.floor((INT_MAX - digit) / 10)) {
      return sign === 1 ? INT_MAX : INT_MIN;
    }
    value = value * 10 + digit;
    i++;
  }

  return sign * value || 0; // "|| 0" turns -0 into 0
};

What the interviewer is checking

This tests whether you can turn a fussy specification into clean, careful code and handle overflow without relying on bigger integer types.

Mistakes to avoid

• Accepting two sign characters, or a sign after spaces that follow digits.
• Skipping spaces in the middle of the number ("4 2" is 4, not 42).
• Overflowing before clamping in fixed-width languages; check the limit before multiplying by 10.
• Treating '.' as part of the number: "3.9" gives 3.

Follow-ups to expect

• How would you parse floating-point numbers with an exponent? (Extend the state machine.)
• Support other bases such as hex with a 0x prefix? (Digit value lookup, base parameter.)
• Report an error instead of returning 0 for invalid input? (Return an optional or throw.)

In real software

Every configuration-file reader, command-line argument parser and network protocol decoder needs a forgiving yet overflow-safe integer parser like this one.

Practice next