N3mo LC
Back to blog
Sep 08, 2025
24 min read

String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function). The algorithm for myAtoi(string s) is as follows: 1. Read in and ignore any leading whitespace. 2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. If neither is present, assume the result is positive. 3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. 4. Convert these digits into an integer. If no digits were read, then the integer is 0. Change the sign as necessary. 5. If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1. Return the integer as the final result.

Difficulty: Medium | Acceptance: 19.66% | Paid: No

Topics: String

Examples

Example 1

Input:

s = "42"

Output:

42

Explanation: The underlined characters are what is read in and the caret is the current reader position. Step 1: “42” (no characters read because there is no leading whitespace) ^ Step 2: “42” (no characters read because there is neither a ’-’ nor ’+’) ^ Step 3: “42” (“42” is read in) ^

Example 2

Input:

s = " -042"

Output:

-42

Explanation: Step 1: ” -042” (leading whitespace is read and ignored) ^ Step 2: ” -042” (’-’ is read, so the result should be negative) ^ Step 3: ” -042” (“042” is read in, leading zeros ignored in the result) ^

Example 3

Input:

s = "1337c0d3"

Output:

1337

Explanation: Step 1: “1337c0d3” (no characters read because there is no leading whitespace) ^ Step 2: “1337c0d3” (no characters read because there is neither a ’-’ nor ’+’) ^ Step 3: “1337c0d3” (“1337” is read in; reading stops because the next character is a non-digit) ^

Example 4

Input:

s = "0-1"

Output:

0

Explanation: Step 1: “0-1” (no characters read because there is no leading whitespace) ^ Step 2: “0-1” (no characters read because there is neither a ’-’ nor ’+’) ^ Step 3: “0-1” (“0” is read in; reading stops because the next character is a non-digit) ^

Example 5

Input:

s = "words and 987"

Output:

0

Explanation: Reading stops at the first non-digit character ‘w’.

Constraints

- 0 <= s.length <= 200
- s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'

Brute Force Approach

Intuition

Iterate through the string character by character, following the exact steps described in the problem statement. Start by skipping leading whitespaces, then check for a sign, and finally convert the digits into a number.

Steps

  • Start by skipping all leading whitespaces in the string.
  • Check if the next character is ’+’ or ’-’, to determine the sign of the number. If it’s ’-’, set a negative flag.
  • Iterate through the subsequent characters and convert them into a number until a non-digit character is encountered.
  • While converting, handle overflow by checking if the number exceeds the 32-bit signed integer limits. If so, clamp it to the appropriate limit.
python
def myAtoi(s: str) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    i = 0
    n = len(s)
    
    # Step 1: Skip leading whitespaces
    while i &lt; n and s[i] == ' ':
        i += 1
    
    # Step 2: Check for sign
    sign = 1
    if i &lt; n and s[i] == '-':
        sign = -1
        i += 1
    elif i &lt; n and s[i] == '+':
        i += 1
    
    # Step 3: Convert digits to integer
    result = 0
    while i &lt; n and s[i].isdigit():
        digit = int(s[i])
        
        # Step 4: Handle overflow
        if result &gt; (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        
        result = result * 10 + digit
        i += 1
    
    # Apply sign and clamp value
    result *= sign
    
    if result &lt; INT_MIN:
        return INT_MIN
    if result &gt; INT_MAX:
        return INT_MAX
    
    return result

Complexity

  • Time: O(n), where n is the length of the input string s. We iterate through the string once.
  • Space: O(1). We use a constant amount of extra space.
  • Notes: The algorithm processes each character of the string at most once. Overflow checks are done using integer arithmetic to avoid using extra space for comparison.

Optimized Approach with Early Termination

Intuition

To improve efficiency, we can terminate the conversion process as soon as we encounter a non-digit character after the number. This avoids unnecessary iterations through the rest of the string.

Steps

  • Skip leading whitespaces as before.
  • Check for sign character and set appropriate flag.
  • Start converting digits to number.
  • As soon as a non-digit character is encountered, stop the conversion process.
  • Perform overflow check during conversion to prevent unnecessary operations on large numbers.
  • Return the final result after applying sign and clamping.
python
def myAtoi(s: str) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    i = 0
    n = len(s)
    
    # Step 1: Skip leading whitespaces
    while i &lt; n and s[i] == ' ':
        i += 1
    
    # Step 2: Check for sign
    sign = 1
    if i &lt; n and s[i] == '-':
        sign = -1
        i += 1
    elif i &lt; n and s[i] == '+':
        i += 1
    
    # Step 3: Convert digits to integer with early termination
    result = 0
    while i &lt; n and s[i].isdigit():
        digit = int(s[i])
        
        # Step 4: Handle overflow
        if result &gt; (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        
        result = result * 10 + digit
        i += 1
    
    # Apply sign and clamp value
    result *= sign
    
    if result &lt; INT_MIN:
        return INT_MIN
    if result &gt; INT_MAX:
        return INT_MAX
    
    return result

Complexity

  • Time: O(n), where n is the length of the input string s. We iterate through the string once, stopping early when we encounter non-digit characters.
  • Space: O(1). We use a constant amount of extra space.
  • Notes: This approach is essentially the same as the brute-force approach in terms of time complexity, but it can be slightly more efficient in practice by avoiding unnecessary iterations after the number portion.

Regular Expression Approach

Intuition

Use regular expressions to extract the relevant portion of the string that matches the pattern for a valid integer. This approach leverages pattern matching to simplify the parsing process.

Steps

  • Use a regular expression to match the optional leading whitespaces, followed by an optional sign, and then one or more digits.
  • If a match is found, extract the matched substring.
  • Convert the matched substring to an integer.
  • Apply clamping to ensure the result is within the 32-bit signed integer range.
python
import re

def myAtoi(s: str) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    # Use regex to find the matching pattern
    match = re.match(r'^s*([+-]?d+)', s)
    
    if not match:
        return 0
    
    num_str = match.group(1)
    
    try:
        result = int(num_str)
    except ValueError:
        return 0
    
    # Clamp the result to 32-bit signed integer range
    if result &lt; INT_MIN:
        return INT_MIN
    if result &gt; INT_MAX:
        return INT_MAX
    
    return result

Complexity

  • Time: O(n), where n is the length of the input string s. The regex matching process takes linear time in the worst case.
  • Space: O(1) for the basic operation, but regex engines may use additional space for pattern matching.
  • Notes: This approach is concise and leverages built-in pattern matching capabilities. However, regex engines can have overhead, and this approach might be less efficient than manual parsing for simple cases.
Prev
Reverse Integer
Next
Palindrome Number