8. String to Integer (atoi)

MediumTrie and Advanced String SearchLinear scan with ordered phasesDeterministic finite state parsing

String to Integer (atoi)

Implement myAtoi, which converts a string to a 32-bit signed integer. Skip leading spaces, read an optional single '+' or '-' sign, then read consecutive digits, stopping at the first non-digit. Ignore everything after the number. If no digits were read, return 0. Clamp the result to the 32-bit signed range [-2^31, 2^31 - 1].

Open official problem prompt ↗

In plain English

Turn the leading numeric prefix of a possibly-messy string into a bounded 32-bit integer, following a fixed set of parsing rules.

Picture it like this

Like a turnstile that only lets certain tokens through in order: first ignore the queue of blanks, admit one sign token, then let a run of digits pass, and slam the gate the moment something unexpected arrives.

Example

Input: s = " -42"
Output: -42
Why: Three leading spaces are skipped, '-' sets the sign, then '42' is read as digits, giving -42.

Constraints

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

Pattern lesson

See the pattern, then code

Deterministic finite state parsing

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Process the string in exactly one forward pass with a moving index, handling each phase in order and clamping only at the end.

New words, made simpleKnow these before the algorithm

32-bit signed range: Integers from -2147483648 to 2147483647 inclusive.
Clamping (saturation): Replacing an out-of-range value with the nearest allowed boundary rather than wrapping around.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Regex extraction

Works but hides the state logic interviewers want to see, and regex clamping is awkward.

Match ^\\s*[+-]?\\d+ with a regular expression and convert the captured group.

Time O(n)Space O(1)

Best choiceSingle-pass index scan

Explicit, easy to reason about, and mirrors how a real parser is built.

Walk one pointer through whitespace, an optional sign, then digits, clamping the accumulated value at the end.

Time O(n)Space O(1)

The rule we keep true

Invariant

At every moment the index i points at the next unconsumed character, and num holds the non-negative integer built from all digits read so far.

Why this is correct

Reasoning

Each phase consumes a well-defined prefix in order, so once digit reading stops no earlier phase can resume; the accumulated magnitude is exact, and a single final clamp guarantees the 32-bit bound.

The algorithm in three movesSay these aloud before coding

1Advance past leading spaces

i moves to index 3 after spaces

2Read at most one optional '+' or '-' sign

sign = -1 at index 3

3Accumulate digits into a running integer until a non-digit appears

num = 42 after reading '4','2'

4Apply the sign

5Clamp the value into the 32-bit signed range and return it

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-3

1 · Read' '

2 · AskAre we still on a space?

3 · Update statei = 0 -> 3

4 · Resulti lands on '-'

Key takeaway

Spaces are skipped, the sign char is consumed, and the digit run '42' is accumulated.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Skip leading whitespace
Only spaces are skipped, and only at the front.
2
Lines 6-10Optional sign
At most one sign character is consumed; default is positive.
3
Lines 11-14Digit accumulation
Build the magnitude digit by digit until a non-digit halts the loop.
4
Lines 15-17Apply sign and clamp
A single min/max clamp enforces the 32-bit signed boundary.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty string or all spaces returns 0
A lone sign like "+" or "-" with no digits returns 0
Leading zeros such as "0032" yield 32
Values beyond the range like "2147483648" clamp to 2147483647
Trailing junk such as "4193 with words" stops after 4193

Common beginner mistakes

Skipping any whitespace instead of only leading spaces
Allowing more than one sign character
Clamping mid-loop instead of once at the end (still correct but easy to get the boundary wrong)
Forgetting that '.' or letters must terminate digit reading, not be parsed

Check your understanding

Why is it safe in Python to accumulate an arbitrarily large num before clamping, unlike in C++?

String to Integer (atoi)

String to Integer (atoi)

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search