8. String to Integer (atoi) - Solution

Q: Is String to Integer (atoi) easy or hard?

String to Integer (atoi) is generally classified as a Medium problem. The core logic is straightforward, but handling all edge cases—leading whitespace, optional sign, stopping at non-digits, and overflow—makes it tricky in interviews.

Q: String to Integer (atoi) Python/Java solution

Both Python and Java implementations follow the same logic: iterate through the string, skip spaces, detect the sign, convert digits into a number, and clamp to the 32-bit range. The only differences are language-specific character checks and integer limits.

Q: How to solve String to Integer (atoi) in O(n)?

Iterate through the string once. Skip leading spaces, detect an optional '+' or '-' sign, then read digits while updating the integer using result = result * 10 + digit. Before multiplying, check whether the result would overflow a 32-bit signed integer and clamp to INT_MAX or INT_MIN if needed.

Q: What is the best approach for String to Integer (atoi)?

Iterative parsing is the preferred approach. You scan the string character by character, skip whitespace, process an optional sign, accumulate digits, and detect overflow before updating the result. This method runs in O(n) time and O(1) space while giving full control over edge cases.

Q: Is String to Integer (atoi) asked at Google/Amazon/Meta?

String parsing problems like atoi frequently appear in interviews at large tech companies including Amazon, Google, and Meta. The question tests attention to edge cases such as whitespace, sign handling, invalid characters, and integer overflow.

Q: What data structure is used in String to Integer (atoi)?

The solution mainly uses simple variables and sequential string traversal rather than complex data structures. The algorithm relies on character inspection, arithmetic operations, and boundary checks while scanning the string.

Q: What is the time complexity of String to Integer (atoi)?

The optimal solution runs in O(n) time where n is the length of the input string. Each character is inspected at most once during parsing. Space complexity is O(1) because only a few variables are used to store the sign, index, and numeric result.

The problem

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

Whitespace: Ignore any leading whitespace (" ").
Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present.
Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
Rounding: If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ - 1], then round the integer to remain in the range. Specifically, integers less than -2³¹ should be rounded to -2³¹, and integers greater than 2³¹ - 1 should be rounded to 2³¹ - 1.

Return the integer as the final result.

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 '.'.

Approach overview

Problem Overview: Convert a string into a 32-bit signed integer following rules similar to the C/C++ atoi function. You must ignore leading whitespace, detect an optional + or - sign, read digits until a non-digit appears, and clamp the result within the 32-bit signed integer range [-2^31, 2^31-1].

Approach 1: Iterative Parsing and Conversion (O(n) time, O(1) space)

Scan the string from left to right while maintaining a running integer result. First skip leading whitespace using a pointer. Then check for an optional sign and store whether the number is negative. Continue iterating while characters are digits, updating the result with result = result * 10 + digit. During each step, check for overflow by comparing against INT_MAX / 10 before multiplying; if overflow would occur, clamp to INT_MAX or INT_MIN. This approach directly simulates how numeric parsing works in low-level libraries and runs in O(n) time with O(1) space.

This technique relies on careful character inspection and arithmetic overflow checks. It’s essentially a controlled state machine over the string. Problems like this often appear under string processing and manual parsing tasks where built-in conversion functions are restricted.

Approach 2: Regular Expression Approach (O(n) time, O(n) space)

Use a regular expression to extract the valid numeric prefix from the string. A pattern such as ^\s*[+-]?\d+ captures leading whitespace, an optional sign, and a sequence of digits. After extracting the match, convert it to an integer using the language’s numeric conversion function. Finally clamp the value within the 32-bit signed range. Regex simplifies the parsing logic by delegating pattern matching to the regex engine.

This approach is concise and expressive, especially in languages like Python or JavaScript with strong regex support. However, it uses extra memory for the match object and hides some parsing logic inside the regex engine. It’s still linear O(n) time because the pattern scans the string once.

Regex-based solutions appear in some production code when input validation or token extraction is required. These patterns frequently show up in string manipulation and lightweight parsing workflows.

Recommended for interviews: Iterative parsing and conversion. Interviewers want to see how you handle character iteration, numeric accumulation, and overflow detection manually. The regex approach demonstrates knowledge of pattern matching, but the iterative method shows stronger control over algorithm design and edge cases.

Approach 1: Iterative Parsing and Conversion

In this approach, we manually parse the string character by character. First, we skip any leading whitespace. Then, we determine the sign of the number by checking the next character. After we've set up the sign, we convert succeeding string characters to a number as long as they are digits, and check if the number overflows the 32-bit signed integer range. The iterative parsing continues until we encounter a non-numeric character.

Python

class Solution:
    def myAtoi(self, s: str) -> int:
        i, sign, result = 0, 1, 0
        n = len(s)
        while i < n and s[i] == ' ': i += 1
        if i < n and s[i] in ['+', '-']:
            sign = -1 if s[i] == '-' else 1
            i += 1
        while i < n and s[i].isdigit():
            result = result * 10 + int(s[i])
            i += 1
            if result * sign > 2**31 - 1: return 2**31 - 1
            if result * sign < -2**31: return -2**31
        return result * sign

# Example usage:
sol = Solution()
print(sol.myAtoi("-42"))
print(sol.myAtoi("4193 with words"))
print(sol.myAtoi("words and 987"))
print(sol.myAtoi("-91283472332"))

Java

public class Solution {
    public int myAtoi(String s) {
        int i = 0, sign = 1, len = s.length();
        while (i < len && s.charAt(i) == ' ') i++;
        if (i < len && (s.charAt(i) == '+' || s.charAt(i) == '-'))
            sign = (s.charAt(i++) == '-') ? -1 : 1;
        long result = 0;
        while (i < len && Character.isDigit(s.charAt(i))) {
            result = result * 10 + (s.charAt(i++) - '0');
            if (result * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (result * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        return (int) (result * sign);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.myAtoi("-42"));
        System.out.println(sol.myAtoi("4193 with words"));
        System.out.println(sol.myAtoi("words and 987"));
        System.out.println(sol.myAtoi("-91283472332"));
    }
}

C++

#include <iostream>
#include <climits>
using namespace std;

int myAtoi(string s) {
    int i = 0, sign = 1;
    while (i < s.length() && s[i] == ' ') i++;
    if (i < s.length() && (s[i] == '-' || s[i] == '+'))
        sign = (s[i++] == '-') ? -1 : 1;
    long result = 0;
    while (i < s.length() && isdigit(s[i])) {
        result = result * 10 + (s[i++] - '0');
        if (result * sign > INT_MAX) return INT_MAX;
        if (result * sign < INT_MIN) return INT_MIN;
    }
    return result * sign;
}

int main() {
    cout << myAtoi("-42") << endl;
    cout << myAtoi("4193 with words") << endl;
    cout << myAtoi("words and 987") << endl;
    cout << myAtoi("-91283472332") << endl;
    return 0;
}

JavaScript

var myAtoi = function(s) {
    let i = 0, sign = 1, result = 0, n = s.length;
    while (i < n && s[i] === ' ') i++;
    if (i < n && (s[i] === '+' || s[i] === '-')) {
        sign = (s[i++] === '-') ? -1 : 1;
    }
    while (i < n && s[i] >= '0' && s[i] <= '9') {
        result = result * 10 + (s[i++] - '0');
        if (result * sign > 2 ** 31 - 1) return 2 ** 31 - 1;
        if (result * sign < -(2 ** 31)) return -(2 ** 31);
    }
    return result * sign;
};

// Example usages:
console.log(myAtoi("-42"));
console.log(myAtoi("4193 with words"));
console.log(myAtoi("words and 987"));
console.log(myAtoi("-91283472332"));

#include <stdio.h>
#include <limits.h>

int myAtoi(char * s) {
    int i = 0, sign = 1;
    while (s[i] == ' ') i++;
    if (s[i] == '-' || s[i] == '+')
        sign = (s[i++] == '-') ? -1 : 1;
    long result = 0;
    while (s[i] >= '0' && s[i] <= '9') {
        result = result * 10 + (s[i++] - '0');
        if (result * sign > INT_MAX) return INT_MAX;
        if (result * sign < INT_MIN) return INT_MIN;
    }
    return (int)(result * sign);
}

int main() {
    printf("%d\n", myAtoi(" -42"));
    printf("%d\n", myAtoi("4193 with words"));
    printf("%d\n", myAtoi("words and 987"));
    printf("%d\n", myAtoi("-91283472332"));
    return 0;
}

using System;

public class Solution {
    public int MyAtoi(string s) {
        int i = 0, sign = 1, n = s.Length;
        while (i < n && s[i] == ' ') i++;
        if (i < n && (s[i] == '+' || s[i] == '-'))
            sign = (s[i++] == '-') ? -1 : 1;
        long result = 0;
        while (i < n && char.IsDigit(s[i])) {
            result = result * 10 + (s[i++] - '0');
            if (result * sign > int.MaxValue) return int.MaxValue;
            if (result * sign < int.MinValue) return int.MinValue;
        }
        return (int)(result * sign);
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.MyAtoi("-42"));
        Console.WriteLine(sol.MyAtoi("4193 with words"));
        Console.WriteLine(sol.MyAtoi("words and 987"));
        Console.WriteLine(sol.MyAtoi("-91283472332"));
    }
}

In Python, the approach remains consistent with the C and Java implementations, though syntactically streamlined. Initial conditions are set, including ignoring whitespace and determining the sign. The conversion loop runs over numeric digits, and checks for overflows before returning a final integer result.

Complexity

Time Complexity: O(n), processing is linear with respect to the length of the string.

Space Complexity: O(1), characterized by a fixed amount of extra space use.

Try this approach in the editor

Approach 2: Regular Expression Approach

Using regular expressions simplifies extracting the integer portion from a string. This involves defining a regular expression to match the pattern for potential number initializations, determining whether followed by valid digits until non-numeric encounters or string end, and then mathematically transforming results. While elegant, care still needs to be taken on handling sign and range boundaries.

Python

import re

class Solution:
    def myAtoi(self, s: str) -> int:
        match = re.match(r'^[\s]*([+-]?\d+)', s)
        if not match:
            return 0
        num = int(match.group(1))
        int_max, int_min = 2**31 - 1, -2**31
        if num > int_max: return int_max
        if num < int_min: return int_min
        return num

# Example usage:
sol = Solution()
print(sol.myAtoi("-42"))
print(sol.myAtoi("4193 with words"))
print(sol.myAtoi("words and 987"))
print(sol.myAtoi("-91283472332"))

JavaScript

var myAtoi = function(s) {
    const match = s.match(/^\s*([+-]?\d+)/);
    const num = match ? parseInt(match[1], 10) : 0;
    const intMax = 2 ** 31 - 1;
    const intMin = -(2 ** 31);
    if (num > intMax) return intMax;
    if (num < intMin) return intMin;
    return num;
};

// Example usages:
console.log(myAtoi("-42"));
console.log(myAtoi("4193 with words"));
console.log(myAtoi("words and 987"));
console.log(myAtoi("-91283472332"));

Leveraging Python's regex library, we employ an expression that recognizes number-related input starting with whitespace/signs, combining matched string outcomes into an integer. Compared to other manual parsing routines, this method highlights reductionism while maintaining integrity on output values.

Complexity

Time Complexity: O(n), driven primarily by the parsing constraints of regex operation.

Space Complexity: O(1), based on the dependable storage allocation for interim units declared during use.

Try this approach in the editor

Approach 3: Traverse the String

First, we determine whether the string is empty. If it is, we directly return 0.

Otherwise, we need to traverse the string, skip the leading spaces, and determine whether the first non-space character is a positive or negative sign.

Then we traverse the following characters. If it is a digit, we judge whether adding this digit will cause integer overflow. If it does, we return the result according to the positive or negative sign. Otherwise, we add the digit to the result. We continue to traverse the following characters until we encounter a non-digit character or the traversal ends.

After the traversal ends, we return the result according to the positive or negative sign.

The time complexity is O(n), where n is the length of the string. We only need to process all characters in turn. The space complexity is O(1).

func myAtoi(s string) int {
	i, n := 0, len(s)
	num := 0

	for i < n && s[i] == ' ' {
		i++
	}
	if i == n {
		return 0
	}

	sign := 1
	if s[i] == '-' {
		sign = -1
		i++
	} else if s[i] == '+' {
		i++
	}

	for i < n && s[i] >= '0' && s[i] <= '9' {
		num = num*10 + int(s[i]-'0')
		i++
		if num > math.MaxInt32 {
			break
		}
	}

	if num > math.MaxInt32 {
		if sign == -1 {
			return math.MinInt32
		}
		return math.MaxInt32
	}
	return sign * num
}

PHP

class Solution {
    /**
     * @param string $s
     * @return int
     */

    function myAtoi($s) {
        $s = str_replace('e', 'x', $s);
        if (intval($s) < pow(-2, 31)) {
            return -2147483648;
        }
        if (intval($s) > pow(2, 31) - 1) {
            return 2147483647;
        }
        return intval($s);
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Parsing and Conversion	Time Complexity: O(n), processing is linear with respect to the length of the string. Space Complexity: O(1), characterized by a fixed amount of extra space use.
Regular Expression Approach	Time Complexity: O(n), driven primarily by the parsing constraints of regex operation. Space Complexity: O(1), based on the dependable storage allocation for interim units declared during use.
Traverse the String	–

Approach

Complexity

Iterative Parsing and Conversion

Time Complexity: O(n), processing is linear with respect to the length of the string.

Space Complexity: O(1), characterized by a fixed amount of extra space use.

Regular Expression Approach

Time Complexity: O(n), driven primarily by the parsing constraints of regex operation.

Space Complexity: O(1), based on the dependable storage allocation for interim units declared during use.

Traverse the String

–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Parsing and Conversion	O(n)	O(1)	Preferred for interviews and low-level parsing where overflow checks and manual control are required
Regular Expression Approach	O(n)	O(n)	Useful for quick input parsing or when regex is already used for validation

Frequently asked questions

Is String to Integer (atoi) easy or hard?

String to Integer (atoi) is generally classified as a Medium problem. The core logic is straightforward, but handling all edge cases—leading whitespace, optional sign, stopping at non-digits, and overflow—makes it tricky in interviews.

String to Integer (atoi) Python/Java solution

Both Python and Java implementations follow the same logic: iterate through the string, skip spaces, detect the sign, convert digits into a number, and clamp to the 32-bit range. The only differences are language-specific character checks and integer limits.

How to solve String to Integer (atoi) in O(n)?

Iterate through the string once. Skip leading spaces, detect an optional '+' or '-' sign, then read digits while updating the integer using result = result * 10 + digit. Before multiplying, check whether the result would overflow a 32-bit signed integer and clamp to INT_MAX or INT_MIN if needed.

What is the best approach for String to Integer (atoi)?

Iterative parsing is the preferred approach. You scan the string character by character, skip whitespace, process an optional sign, accumulate digits, and detect overflow before updating the result. This method runs in O(n) time and O(1) space while giving full control over edge cases.

Is String to Integer (atoi) asked at Google/Amazon/Meta?

String parsing problems like atoi frequently appear in interviews at large tech companies including Amazon, Google, and Meta. The question tests attention to edge cases such as whitespace, sign handling, invalid characters, and integer overflow.

What data structure is used in String to Integer (atoi)?

The solution mainly uses simple variables and sequential string traversal rather than complex data structures. The algorithm relies on character inspection, arithmetic operations, and boundary checks while scanning the string.

What is the time complexity of String to Integer (atoi)?

The optimal solution runs in O(n) time where n is the length of the input string. Each character is inspected at most once during parsing. Space complexity is O(1) because only a few variables are used to store the sign, index, and numeric result.

String to Integer (atoi) solution and explanation

The problem

Approach overview

Approach 1: Iterative Parsing and Conversion

Approach 2: Regular Expression Approach

Approach 3: Traverse the String

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

String to Integer (atoi) solution and explanation

The problem

Approach overview

Approach 1: Iterative Parsing and Conversion

Approach 2: Regular Expression Approach

Approach 3: Traverse the String

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems