Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Parse the string through four ordered phases: skip leading spaces, read one optional +/- sign, consume consecutive digits, and stop at the first non-digit. Accumulate the number while clamping to the 32-bit range [-2147483648, 2147483647]. The hard part is detecting overflow BEFORE it happens — check `result > (INT_MAX - digit) / 10` before each multiply.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you implement a precise multi-phase parser and, critically, whether your overflow handling is correct in a fixed-width integer — most candidates check overflow after the value has already wrapped.
Where candidates slip
Detecting overflow with `result * 10 + d > INT_MAX` AFTER the multiply (the multiply itself already overflowed), or mishandling INT_MIN whose magnitude (2147483648) exceeds INT_MAX.
How to stand out
State the four phases explicitly, check overflow before multiplying using `(INT_MAX - d) / 10`, and note that the same check clamps both INT_MAX and INT_MIN correctly without special-casing the negative boundary.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewStartNext char is + or -?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Sequential Phase Parse (Optimal)
1Hint 1Explore hintHide hint
Break the spec into ordered phases: skip spaces, read at most one sign, read digits, stop at the first non-digit. Use a single index i that only moves forward.
2Hint 2Explore hintHide hint
Accumulate digits as result = result * 10 + digit. The danger is that this expression can exceed INT_MAX mid-computation and wrap in a fixed-width int.
3Hint 3Explore hintHide hint
Before the multiply, ask: would result * 10 + digit exceed INT_MAX? That's exactly result > (INT_MAX - digit) / 10. If so, clamp to INT_MAX or INT_MIN by sign and return immediately.
A · Core idea
The problem is a miniature parser, and the cleanest implementation mirrors the spec's four phases literally with one forward-moving index i. Phase one advances i past leading spaces. Phase two peeks at one character: if it's '+' or '-', record the sign and step once; otherwise the number is positive and i stays put. Phase three loops while the current character is a digit, folding each into result. Phase four returns sign * result. There is no backtracking — i only increases — which is why a single pass suffices.
Why the phases must be ordered and non-repeating. Each phase consumes a distinct, non-overlapping part of the grammar. A sign is only valid immediately after the spaces and before any digit; that's why "+-12" yields 0 (after the first '+', the next char '-' is not a digit, so the digit loop reads nothing) and why " 42" works but " 4 2" parses only 4. Encoding the order directly — spaces, then at most one sign, then digits — makes these cases fall out automatically instead of needing special handling.
The overflow check is the entire difficulty. In a fixed-width 32-bit int, computing result * 10 + digit can silently wrap before you get a chance to compare it to INT_MAX. So the test must happen before the arithmetic. We ask: is result already big enough that result * 10 + digit would exceed INT_MAX? Algebraically that's result > (INT_MAX - digit) / 10. Using integer division here is deliberate and correct — it makes the boundary land precisely so that "2147483647" is accepted while "2147483648" clamps. Once the condition trips, we return INT_MAX for a positive sign or INT_MIN for a negative one and stop.
Why one check covers INT_MIN too. The negative boundary is sneaky: |INT_MIN| = 2147483648 = INT_MAX + 1, so the magnitude of the most-negative value is itself out of positive int range. But our check clamps the moment the magnitude would pass INT_MAX, and at that instant we return INT_MIN when the sign is negative. Tracing "-2147483648": at the last digit result = 214748364, digit = 8, and (INT_MAX - 8) / 10 = 214748363; since 214748364 > 214748363, we clamp — and because the sign is negative we return exactly INT_MIN, the correct answer. The same line that protects the positive side delivers the negative boundary for free, with no separate case.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = " -42"Interactive diagram
Overflow check, visualized
skip spacesBefore each multiply, ask whether result*10 + digit would pass INT_MAX. Rearranged so the test itself can't overflow.
-42C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Detecting overflow requires reasoning about the operation that hasn't happened yet. Rearranging result * 10 + d > INT_MAX into result > (INT_MAX - d) / 10 moves the dangerous multiply out of the comparison so the test itself never overflows. That 'check before you compute' move is the transferable lesson for any fixed-width accumulation.
ComplexityO(n) time, O(1) space — A single forward scan of the string, O(1) work per character, and a constant number of scalar variables → O(n) time, O(1) space.
E · Edge cases and pitfalls9s = "" — Empty → no spaces, no sign, no digits → result 0 → returns 0.Explore edge casesHide edge cases
Edge cases handled
s = ""Empty → no spaces, no sign, no digits → result 0 → returns 0.s = " +0 123"Skip spaces, sign +, read '0', then space stops it → 0.s = "+-12"Sign '+', then '-' is not a digit → digit loop reads nothing → 0.s = "2147483648"At digit '8': 214748364 > (INT_MAX-8)/10=214748363 → clamp to INT_MAX 2147483647.s = "-2147483648"Same clamp triggers; sign negative → returns INT_MIN exactly.
Pitfalls
- Checking overflow AFTER computing result*10 + digit — the value has already wrapped in a fixed-width int.
- Forgetting that |INT_MIN| = INT_MAX + 1, then special-casing the negative boundary incorrectly.
- Skipping whitespace anywhere, not just the front — '4 2' must parse as 4, not 42.
- Allowing more than one sign or a sign after digits.
Approach 2 of 2
Deterministic Finite Automaton (DFA)
1Hint 1Explore hintHide hint
Model the parser as a state machine with four states: START, SIGNED, IN_NUMBER, END. Each input character belongs to a class: space, sign, digit, other.
2Hint 2Explore hintHide hint
A 4×4 transition table maps (state, char-class) → next state. The table encodes every rule — e.g. a sign is only legal from START, a digit keeps you IN_NUMBER.
3Hint 3Explore hintHide hint
Drive the machine character by character. Update sign on entering SIGNED and accumulate (with the same overflow clamp) on entering IN_NUMBER. Break on END.
A · Core idea
Instead of hand-coding the phase order with if/while, the DFA captures it in data: a small transition table. There are four states — START (skipping spaces / awaiting sign), SIGNED (a sign was just read), IN_NUMBER (reading digits), and END (parsing finished) — and four character classes — space, sign, digit, and other. Each cell of the 4×4 table answers 'from this state, on this kind of character, where do I go?'.
Why the table is the spec, made executable. Every rule the prose describes becomes a single table entry. A space keeps you in START but, from any later state, drives you to END (because whitespace is only allowed up front). A sign is accepted only from START (moving to SIGNED); seeing a sign anywhere else goes to END, which is exactly why a second sign or a sign after digits halts parsing. A digit moves START/SIGNED/IN_NUMBER all into IN_NUMBER. This makes the legality rules auditable at a glance and trivial to extend — add a column for '.' if you later needed decimals.
Driving the machine. We scan the string, look up state = table[state][classOf(c)], and act on the transition: entering SIGNED records the sign; entering IN_NUMBER accumulates the digit using the same overflow-safe clamp as the direct approach; reaching END breaks the loop. Using a long accumulator that we clamp the instant it passes INT_MAX keeps the arithmetic from wrapping while staying within long range (we never let it grow beyond INT_MAX * 10 + 9).
Why mention it at all. Functionally it's identical to the sequential parse — same O(n)/O(1), same answers. Its value in an interview is signaling: it shows you can formalize an ad-hoc set of rules into a clean state machine, which is precisely how real lexers and protocol parsers are built. For this problem the sequential version is shorter and is the better default; the DFA is the 'I can also do it rigorously' flourish.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = " -012a"' '
START --space--> START
state = START-12C · Code with teaching comments
Reference implementation previewpublic int myAtoi(String s) { // states: 0=START, 1=SIGNED, 2=IN_NUMBER, 3=END // cols: 0=space, 1=sign, 2=digit, 3=other int[][] table = { {0, 1, 2, 3},Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Any parsing problem with ordered, mutually-exclusive phases can be expressed as a DFA: enumerate the states, classify the input alphabet, and fill a transition table. Once you see the table, correctness becomes a data-review exercise rather than a control-flow puzzle — a powerful reframing for messy parsing specs.
ComplexityO(n) time, O(1) space — One pass with a constant-size 4×4 table and O(1) per-character transition → O(n) time, O(1) space. The accumulation uses a long bounded by the clamp, so no wrap occurs.
E · Edge cases and pitfalls6s = " -012a" — Spaces skipped, sign -, leading zeros fine → IN_NUMBER reads 012=12, 'a' → END → -12.Explore edge casesHide edge cases
Edge cases handled
s = " -012a"Spaces skipped, sign -, leading zeros fine → IN_NUMBER reads 012=12, 'a' → END → -12.s = "+1"START --sign--> SIGNED, then digit → IN_NUMBER → 1.s = ". 5"'.' is class 'other' from START → END immediately → 0.
Pitfalls
- Using an int accumulator in the DFA — it can wrap before the clamp; use long (Java) and clamp each step.
- Mis-filling a table cell (e.g. allowing sign from IN_NUMBER) — silently accepts malformed input.
- Treating '.' or letters as anything but the 'other' class, which must route to END.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int myAtoi(String s) { int i = 0, n = s.length(); while (i < n && s.charAt(i) == ' ') i++; // 1. skip leading spaces int sign = 1; if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) { // 2. optional signExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Overflow checked after the multiply
result * 10 + digit can overflow a 32-bit int before the comparison runs, so the test sees a wrapped (often negative) value and lets bad data through.
Explore the code comparisonHide the code comparison
Overflow checked after the multiply
result * 10 + digit can overflow a 32-bit int before the comparison runs, so the test sees a wrapped (often negative) value and lets bad data through.
Don't write this
result = result * 10 + digit; // may already have wrapped
if (result > Integer.MAX_VALUE) { ... } // too late; also always false for intWrite this instead
if (result > (Integer.MAX_VALUE - digit) / 10) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
result = result * 10 + digit;2Special-casing INT_MIN wrong
Because |INT_MIN| = INT_MAX + 1, code that clamps the magnitude to INT_MAX for both signs returns -2147483647 for '-2147483648' instead of -2147483648.
Explore the code comparisonHide the code comparison
Special-casing INT_MIN wrong
Because |INT_MIN| = INT_MAX + 1, code that clamps the magnitude to INT_MAX for both signs returns -2147483647 for '-2147483648' instead of -2147483648.
Don't write this
if result > INT_MAX: # same bound for both signs
return -INT_MAX if sign == -1 else INT_MAX # off by one on INT_MINWrite this instead
if sign == 1 and result > INT_MAX:
return INT_MAX
if sign == -1 and -result < INT_MIN:
return INT_MIN3Skipping whitespace mid-number
Stripping all spaces (or skipping them inside the digit loop) makes '4 2' parse as 42, but the spec stops at the first space after digits.
Explore the code comparisonHide the code comparison
Skipping whitespace mid-number
Stripping all spaces (or skipping them inside the digit loop) makes '4 2' parse as 42, but the spec stops at the first space after digits.
Don't write this
s = s.replace(' ', '') # destroys the 'whitespace only at front' ruleWrite this instead
while i < n and s[i] == ' ':
i += 1 # skip ONLY leading spaces; inner spaces end the numberRevise
Carry the pattern into the interview
Pattern to remember
Ordered phase parse with overflow-safe accumulation
Code pattern to memorize
i = 0
skip while s[i] == ' '
sign = +1; if s[i] in '+-': sign = (s[i]=='-' ? -1 : +1); i++
result = 0
while s[i].isDigit():
d = s[i] - '0'
if result > (INT_MAX - d) / 10: return clamp(sign)
result = result*10 + d; i++
return sign * resultRules to remember
- 1The phases are strictly ordered: spaces → at most ONE sign → digits → stop. A sign after digits, or a second sign, ends parsing.
- 2Whitespace is only skipped at the FRONT. Spaces between digits or after the sign terminate the number.
- 3Check overflow BEFORE multiplying, not after —
result*10 + dmay already have overflowed by the time you test it in a fixed-width int. - 4Clamp, don't wrap: out-of-range returns
INT_MAX(2147483647) orINT_MIN(-2147483648), never a wrapped value. - 5Any leading non-space, non-sign, non-digit character means return 0 — e.g.
"words 987"→ 0.
Use this pattern when
- Hand-rolling a parser for a constrained grammar (sign + digits)
- You must consume input in a fixed phase order and stop on the first violation
- Fixed-width integer output requires overflow detection / saturation
- Tokenizing the leading numeric prefix of a messy string
Choose another pattern when
- You're allowed to use a library parser (Integer.parseInt) and trust its exceptions → not the point of this problem
- Input is guaranteed clean and in-range → the clamping/edge logic is the whole exercise, so a guarantee makes it trivial
- Need to parse floats / scientific notation → a richer grammar than this
- Big-integer output with no clamping → overflow handling disappears
Interview takeaway
atoi is a parsing problem disguised as a string problem. The interview signal is precision: correct phase order, whitespace only at the front, and — above all — overflow detected before it corrupts a fixed-width int. Get the overflow check right and the rest is bookkeeping.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPhase-ordered parsing with fixed-width overflow handling. The reusable ideas are (1) model ordered, mutually-exclusive rules as a DFA / explicit phases, and (2) detect overflow by rearranging the comparison so the dangerous arithmetic happens after the check — both reappear in Valid Number and Reverse Integer.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Valid NumberComing soonA richer DFA: signs, decimals, and exponents. The transition-table approach scales directly to it.
- Reverse IntegerComing soonSame overflow-before-multiply guard while pushing digits onto a 32-bit result.
- Roman to IntegerAnother character-by-character accumulation into a number, with a neighbor-dependent rule.