20 · String Parsing & Expression Evaluation
#8 String to Integer (atoi)
frequently reported atNetflixBloombergMetaAmazonMicrosoftGoogle
the problem
In plain words
Turn a string into a 32-bit signed int, the way C's atoi reads text. First skip any spaces at the start. Then read at most one '+' or '-' (no sign means positive). Then read digits until a character that isn't a digit, or the end. Leading zeros are fine. If no digits were read, the answer is 0. If the number is outside [−2³¹, 2³¹ − 1], return the nearest end of that range.
in s = "42"
out 42
in s = " -042"
out -42
Spaces skipped, '-' read, then 042 = 42.
in s = "1337c0d3"
out 1337
Reading stops at 'c'.
in s = "0-1"
out 0
After the 0, '-' is not a digit, so reading stops.
in s = "words and 987"
out 0
A letter comes before any digit.
- 0 ≤ s.length ≤ 200
- s has English letters, digits, ' ', '+', '-' and '.'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternString parsingDigit peeling (% 10 and / 10)
where this runsC's strtol follows the same steps — skip whitespace, optional sign, digits — and returns LONG_MAX or LONG_MIN on overflow.
It's a tiny state machine — spaces, then one sign, then digits, then stop — plus one overflow check before each result * 10 + d.
solutions
From brute force to optimal
Use indexes to find the digit run, copy it out, and let Long.parseLong do the arithmetic; more than 10 significant digits always clamps.
- Skip spaces; note the sign; skip leading zeros.
- Find the end of the digit run; take it as a substring.
- Over 10 digits → clamp. Else Long.parseLong, apply the sign, clamp to the int range.
A few scans over the input and one parse of at most 10 digits.
The substring of digits.
class Solution { public int myAtoi(String s) { int i = 0, n = s.length(); while (i < n && s.charAt(i) == ' ') i++; // 1. skip leading spaces boolean negative = i < n && s.charAt(i) == '-'; if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++; // 2. at most one sign while (i < n && s.charAt(i) == '0') i++; // leading zeros add nothing int from = i; while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') i++; String digits = s.substring(from, i); // 3. the digit run, as text if (digits.length() > 10) { // 11+ significant digits: no int is that long return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE; } long value = digits.isEmpty() ? 0 : Long.parseLong(digits); // 10 digits always fit in a long if (negative) value = -value; return (int) Math.max(Integer.MIN_VALUE, Math.min(Integer.MAX_VALUE, value)); // 4. clamp }}Three phases in order — spaces, sign, digits — and before every append, check that result × 10 + d still fits.
- Skip ' '. Read one '+' or '-' into sign.
- While s[i] is '0'..'9': d = s[i] − '0'.
- If result > (MAX − d) / 10, return sign == 1 ? MAX : MIN.
- result = result × 10 + d. At the first non-digit, return sign × result.
Each character is read at most once.
An index, a sign and an int — no long, no copy.
class Solution { public int myAtoi(String s) { int i = 0, n = s.length(); while (i < n && s.charAt(i) == ' ') i++; // state 1: skip leading spaces int sign = 1; if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) { // state 2: at most one sign sign = s.charAt(i) == '-' ? -1 : 1; i++; } int result = 0; while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') { // state 3: digits int d = s.charAt(i) - '0'; if (result > (Integer.MAX_VALUE - d) / 10) { // result * 10 + d would pass 2^31 - 1 return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; } result = result * 10 + d; i++; } return sign * result; // any other character ends the number }}Dry run
Write the machine as data: NEXT[state][charClass] with states start, signed, number, end.
- Classify each char: space, sign, digit, other.
- state = NEXT[state][class]; act on the new state (save the sign, or append a digit).
- Stop in the end state; a long notices the overflow at once.
One table lookup per character.
A 4 × 4 table.
class Solution { // Rows are states: 0 start, 1 after a sign, 2 inside the number, 3 end. // Columns are character classes: 0 space, 1 sign, 2 digit, 3 anything else. private static final int[][] NEXT = { {0, 1, 2, 3}, // start: spaces keep us here {3, 3, 2, 3}, // after a sign: only a digit may follow {3, 3, 2, 3}, // inside the number: digits continue, anything else ends it {3, 3, 3, 3}, // end: stay here }; public int myAtoi(String s) { int state = 0, sign = 1; long result = 0; for (int i = 0; i < s.length() && state != 3; i++) { char c = s.charAt(i); state = NEXT[state][column(c)]; if (state == 1) { sign = c == '-' ? -1 : 1; } else if (state == 2) { result = result * 10 + (c - '0'); if (result > Integer.MAX_VALUE) { // a long has room to notice the overflow return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; } } } return (int) (sign * result); } private int column(char c) { if (c == ' ') return 0; if (c == '+' || c == '-') return 1; if (c >= '0' && c <= '9') return 2; return 3; }}in the room
How to say it in the interview
talk track
- List the phases before coding: spaces, optional sign, digits, stop.
- Ask: is ' ' the only whitespace? Clamp or throw on overflow? (On LeetCode: yes, and clamp.)
- Write the guard and explain it: result > (MAX − d) / 10 means result × 10 + d > MAX.
- Point out that MIN works too: 2,147,483,648 trips the guard and the negative sign returns MIN_VALUE.
traps
- Accumulating in a
longand checking only at the end: 20 digits overflow even a long ("18446744073709551617" wraps round to 1). - Accepting a second sign: "+-12" is 0.
- Skipping spaces after the sign: "- 5" is 0.
Character.isDigitlets Unicode digits through; compare with '0' and '9'.
what they ask next
Follow-ups
Valid Number (LC 65): is a string a valid decimal or scientific number?
Grow the state machine: sign → digits → '.' → digits → 'e' → sign → digits, with a table of legal moves. The table form above scales best.
Why not just call Integer.parseInt?
It throws on leading spaces, on junk after the digits and on overflow, where atoi must skip, stop and clamp. You would still need your own scanner around it.
before you submit
Edge cases to test
- Empty, or only spaces → 0.
- Exactly the limits: "2147483647" and "-2147483648" fit; one more clamps.
- Very long numbers: "91283472332" → 2147483647, and 20 digits overflow even a long.
- A sign with nothing after it: "-" → 0.
practise next
Similar problems
- #7Reverse IntegerMediumin Math & Numbers
- #227Basic Calculator IIMediumin Parsing
- #13Roman to IntegerEasyin Parsing