String to Integer (atoi)
String to Integer (atoi) is a medium arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (overflow guard in 32 bits), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from scan with a wider accumulator up.
Problem
Implement myAtoi(s), which turns the start of a string into a 32-bit signed integer, reading it in this order:
- Skip any leading space characters
' '. - Read one optional sign,
'+'or'-'. Without a sign the number is positive. - Read consecutive digits until a non-digit character or the end of the string. Leading zeros are allowed. If no digits were read, the result is
0. - If the number is outside the range
[-2^31, 2^31 - 1], clamp it to the nearest end of that range.
Everything after the digits is ignored. Return the final integer.
Examples
Example 1
- Input
s = " -0071kg"- Output
-71- Why
- Skip the three spaces, read the minus sign, read the digits 0071 and stop at 'k'. Leading zeros do not matter.
Example 2
- Input
s = "+9999999999 apples"- Output
2147483647- Why
- 9999999999 is larger than 2^31 - 1, so the result is clamped to 2147483647.
Example 3
- Input
s = "rate 42"- Output
0- Why
- The first non-space character is 'r', not a sign or a digit, so nothing is read.
Constraints
0 <= s.length <= 200sconsists of English letters, digits, spaces and the characters+,-and..
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 25 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Scan with a wider accumulator | O(n) | O(1) |
| Optimal (overflow guard in 32 bits) | O(n) | O(1) |
1Scan with a wider accumulator
O(n)Each character is looked at at most once.O(1)A few scalar variables.Walk the string with one index: skip spaces, read an optional sign, then read digits into a 64-bit number. As soon as the value goes past the 32-bit range, stop and return the clamped bound; otherwise return sign times the value at the end.
- Skip leading ' ' characters.
- If the next character is '+' or '-', record the sign and move on.
- While the character is a digit: value = value * 10 + digit (in a 64-bit long).
- If sign * value > 2^31 - 1 return 2^31 - 1; if sign * value < -2^31 return -2^31.
- Return (int) (sign * value).
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 value = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
value = value * 10 + (s.charAt(i) - '0');
if (sign * value > Integer.MAX_VALUE) return Integer.MAX_VALUE;
if (sign * value < Integer.MIN_VALUE) return Integer.MIN_VALUE;
i++;
}
return (int) (sign * value);
}
}class Solution:
def myAtoi(self, s: str) -> int:
INT_MAX, INT_MIN = 2**31 - 1, -(2**31)
i, n = 0, len(s)
while i < n and s[i] == " ":
i += 1
sign = 1
if i < n and s[i] in "+-":
if s[i] == "-":
sign = -1
i += 1
value = 0
while i < n and s[i].isdigit():
value = value * 10 + (ord(s[i]) - 48)
if sign * value > INT_MAX:
return INT_MAX
if sign * value < INT_MIN:
return INT_MIN
i += 1
return sign * valueclass Solution {
public:
int myAtoi(string s) {
int i = 0, n = s.size();
while (i < n && s[i] == ' ') i++;
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) {
if (s[i] == '-') sign = -1;
i++;
}
long long value = 0;
while (i < n && isdigit((unsigned char) s[i])) {
value = value * 10 + (s[i] - '0');
if (sign * value > INT_MAX) return INT_MAX;
if (sign * value < INT_MIN) return INT_MIN;
i++;
}
return (int) (sign * value);
}
};function myAtoi(s) {
const INT_MAX = 2147483647, INT_MIN = -2147483648;
let i = 0;
const n = s.length;
while (i < n && s[i] === " ") i++;
let sign = 1;
if (i < n && (s[i] === "+" || s[i] === "-")) {
if (s[i] === "-") sign = -1;
i++;
}
let value = 0;
while (i < n && s[i] >= "0" && s[i] <= "9") {
value = value * 10 + (s.charCodeAt(i) - 48);
if (sign * value > INT_MAX) return INT_MAX;
if (sign * value < INT_MIN) return INT_MIN;
i++;
}
return sign * value + 0;
}2Optimal (overflow guard in 32 bits)
O(n)One pass over the characters.O(1)Only an index, a sign and the running result.Do the same scan but keep the result in a plain 32-bit int. Before result * 10 + digit, check whether it would pass 2^31 - 1: that happens when result > MAX / 10, or result == MAX / 10 and digit > 7. If so, return the bound for the current sign (for a negative number, the clamp is exactly -2^31, which also covers the value -2147483648 itself).
- Skip spaces and read an optional sign as before.
- For each digit d: if result > 214748364, or result == 214748364 and d > 7, return sign == 1 ? 2^31 - 1 : -2^31.
- Otherwise result = result * 10 + d.
- Return sign * result.
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++;
}
int result = 0;
int limit = Integer.MAX_VALUE / 10;
while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
int d = s.charAt(i) - '0';
if (result > limit || (result == limit && d > 7)) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
result = result * 10 + d;
i++;
}
return sign * result;
}
}class Solution:
def myAtoi(self, s: str) -> int:
INT_MAX, INT_MIN = 2**31 - 1, -(2**31)
i, n = 0, len(s)
while i < n and s[i] == " ":
i += 1
sign = 1
if i < n and s[i] in "+-":
if s[i] == "-":
sign = -1
i += 1
result = 0
limit = INT_MAX // 10
while i < n and "0" <= s[i] <= "9":
d = ord(s[i]) - 48
if result > limit or (result == limit and d > 7):
return INT_MAX if sign == 1 else INT_MIN
result = result * 10 + d
i += 1
return sign * resultclass Solution {
public:
int myAtoi(string s) {
int i = 0, n = s.size();
while (i < n && s[i] == ' ') i++;
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) {
if (s[i] == '-') sign = -1;
i++;
}
int result = 0;
int limit = INT_MAX / 10;
while (i < n && s[i] >= '0' && s[i] <= '9') {
int d = s[i] - '0';
if (result > limit || (result == limit && d > 7)) {
return sign == 1 ? INT_MAX : INT_MIN;
}
result = result * 10 + d;
i++;
}
return sign * result;
}
};function myAtoi(s) {
const INT_MAX = 2147483647, INT_MIN = -2147483648;
let i = 0;
const n = s.length;
while (i < n && s[i] === " ") i++;
let sign = 1;
if (i < n && (s[i] === "+" || s[i] === "-")) {
if (s[i] === "-") sign = -1;
i++;
}
let result = 0;
const limit = Math.floor(INT_MAX / 10);
while (i < n && s[i] >= "0" && s[i] <= "9") {
const d = s.charCodeAt(i) - 48;
if (result > limit || (result === limit && d > 7)) {
return sign === 1 ? INT_MAX : INT_MIN;
}
result = result * 10 + d;
i++;
}
return sign * result + 0;
}Edge cases to test
- Empty string or only spaces: return 0
- A sign with no digits after it, like "-" or "+x": return 0
- Two signs in a row, like "+-5": the second sign stops the read, so return 0
- A huge number of digits: clamp instead of overflowing
- Exactly -2147483648 must come back unchanged
- Spaces between the sign and the digits stop the read
Hints
Hint 1
Process the string in stages with one index: spaces, then an optional sign, then digits.
Hint 2
Stop at the first character that does not belong to the current stage.
Hint 3
Before appending a digit, check whether result * 10 + digit would pass 2^31 - 1.
FAQ
What is the best time complexity for String to Integer (atoi)?
Optimal (overflow guard in 32 bits) runs in O(n) time and O(1) extra space. One pass over the characters.
Which pattern does String to Integer (atoi) use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, Remove Comments.
Is there a brute force solution for String to Integer (atoi)?
Yes. Scan with a wider accumulator takes O(n) time and O(1) space. Walk the string with one index: skip spaces, read an optional sign, then read digits into a 64-bit number.
Which edge cases should I test for String to Integer (atoi)?
Empty string or only spaces: return 0; A sign with no digits after it, like "-" or "+x": return 0; Two signs in a row, like "+-5": the second sign stops the read, so return 0; A huge number of digits: clamp instead of overflowing; Exactly -2147483648 must come back unchanged; Spaces between the sign and the digits stop the read.