String to Integer (atoi)

A reliable atoi parser is a small state machine: skip leading spaces, read one optional sign, consume one numeric prefix, and guard every accumulator update before it can exceed the 32-bit range.

Read the Contract First

The arithmetic is straightforward. The difficult part is preserving the boundary between the valid numeric prefix and everything that follows it.

The parser must:

1. Ignore leading space characters.
2. Read at most one optional + or -.
3. Consume consecutive decimal digits.
4. Stop at the first non-digit.
5. Clamp the result to the signed 32-bit range.

The output range is:

[ [-2^{31}, 2^{31}-1] = [-2147483648, 2147483647] ]

A few examples define the boundary more clearly than a paragraph:

Input	Result	Reason
""	0	There is nothing to parse
" "	0	Only leading spaces exist
"+"	0	A sign without digits produces no number
" +0012abc"	12	Consume digits, then stop at a
"1337c0d3"	1337	The first non-digit terminates parsing
"0-1"	0	The later - cannot restart parsing
"words and 987"	0	The first non-space character is invalid
"2147483648"	2147483647	Positive overflow clamps to the maximum
"-2147483649"	-2147483648	Negative overflow clamps to the minimum

Position matters. Searching for the first digit would incorrectly turn "words 123" into 123. Calling strip() would erase trailing spaces that should terminate the numeric prefix. The parser must follow the contract from left to right rather than normalize the input into a different grammar.

Recognize the Four Parsing Phases

Think of the input as a string parser state machine with four ordered phases. Each phase permits a narrow set of transitions.

1. Skip leading spaces

Advance while the current character is exactly ' '.

This phase can skip:

"   42"       -> 42

It cannot search through arbitrary text:

"   words 42" -> 0

The contract names the space character specifically, so the implementation should check for ' ' rather than silently accepting every kind of whitespace.

2. Read one optional sign

At the first non-space position, consume one + or - if present.

"-42"  -> -42
"+42"  -> 42
"+-12" -> 0

The sign is meaningful only in this phase. In "0-1", the parser consumes 0, then stops when it reaches -. It does not return to the sign phase.

Store the sign separately from the magnitude. That lets positive and negative input share the same digit-accumulation logic.

3. Consume consecutive digits

For each digit, extend the decimal prefix. If the current magnitude is m and the next digit has value d, the candidate update is:

[ m' = 10m + d ]

Leading zeroes require no special case. They are ordinary digit updates.

The digit phase ends at the first character outside '0' through '9'.

4. Terminate

Termination is an expected parser transition, not an error. Once a non-digit appears after the optional sign and digit prefix, return the value accumulated so far.

For example:

"1337c0d3" -> consume 1, 3, 3, 7; stop at c
" -042x"   -> skip space, read -, consume 0, 4, 2; stop at x
"words 42" -> consume no digits; return 0

The minimal state is:

• i: the current position
• sign: 1 or -1
• magnitude: the digits consumed so far
• limit: the largest allowed magnitude for this sign

No has_digit flag is required. If the digit loop consumes nothing, magnitude remains 0, and returning sign * magnitude already produces the required result for "", "+", "-", and other sign-only prefixes. Parsed zero also returns 0; the output does not need to distinguish those histories.

Maintain the Accumulator Invariant

The core invariant is:

After the digit loop has consumed a prefix, magnitude equals the base-10 value represented by exactly those consumed digits.

Suppose the parser has consumed "42". The magnitude is 42. Reading 7 appends that digit to the prefix:

[ 42 \times 10 + 7 = 427 ]

For " -042x", the state evolves as follows:

Consumed part	Sign	Magnitude
leading space skipped	1	0
- consumed	-1	0
0 consumed	-1	0
4 consumed	-1	4
2 consumed	-1	42
x observed	-1	42

The final result is -42.

This direct scan is preferable in an interview because every obligation remains visible. A substring-and-conversion solution still has to identify the legal start, optional sign, first terminator, and overflow boundary. It may be shorter, but it hides the mechanism being tested.

Guard Overflow Before the Update

A signed 32-bit integer has asymmetric limits:

• Positive maximum: 2147483647
• Negative minimum: -2147483648

The negative side has one extra unit of magnitude. Therefore:

positive input: limit = 2147483647
negative input: limit = 2147483648

Before applying:

[ m' = 10m + d ]

check whether m' would exceed limit. Rearranging the inequality gives two cases:

1. m > limit // 10
2. m == limit // 10 and d > limit % 10

So the guard is:

if magnitude > limit // 10:
    overflow

if magnitude == limit // 10 and digit > limit % 10:
    overflow

This is the important implementation move: guard the next state transition, not the state after damage.

Boundary trace

For the positive limit 2147483647:

limit // 10 = 214748364
limit % 10  = 7

When the parser has read 214748364:

• Next digit 7: allowed, producing 2147483647
• Next digit 8: rejected before the update, because 8 > 7

For the negative limit 2147483648:

limit // 10 = 214748364
limit % 10  = 8

When the parser has read 214748364:

• Next digit 8: allowed, producing 2147483648
• Next digit 9: rejected before the update

That one-remainder difference is why the negative limit must be selected before the digit loop.

Python integers do not overflow during multiplication, but the parser still needs this explicit guard. The output contract is 32-bit, and pre-update checking is the reasoning pattern that transfers directly to fixed-width languages.

Implement the One-Pass Parser

def myAtoi(s: str) -> int:
    n = len(s)
    i = 0

    # Phase 1: skip leading spaces
    while i < n and s[i] == " ":
        i += 1

    # Phase 2: read one optional sign
    sign = 1
    if i < n and s[i] in "+-":
        if s[i] == "-":
            sign = -1
        i += 1

    # A negative result may have magnitude 2147483648.
    limit = 2147483648 if sign == -1 else 2147483647

    magnitude = 0

    # Phase 3: consume consecutive decimal digits
    while i < n and "0" <= s[i] <= "9":
        digit = ord(s[i]) - ord("0")

        # Guard the next update before multiplying by 10.
        if (
            magnitude > limit // 10
            or (
                magnitude == limit // 10
                and digit > limit % 10
            )
        ):
            return -limit if sign == -1 else limit

        magnitude = magnitude * 10 + digit
        i += 1

    # Phase 4: stop at the first non-digit.
    # If no digit was consumed, magnitude is still 0.
    return sign * magnitude

The explicit comparison:

"0" <= s[i] <= "9"

matches the problem's decimal alphabet exactly. A broader predicate such as isdigit() may recognize characters outside that narrow grammar. In ordinary application code, that distinction may be acceptable; in an interview parser, explicit behavior is easier to audit.

The code also avoids int(s) and strip() because neither operation represents the required phase boundaries. Built-ins are useful when their semantics match the contract. Here, the contract itself is the algorithm.

Why the State Transitions Are Correct

Each phase preserves a specific condition.

During whitespace skipping, i advances only across leading spaces. It cannot skip letters or search for a later number.

After the sign phase, sign reflects the optional sign immediately following those spaces. If no sign appears, it remains positive. A later sign is never reconsidered.

During the digit phase, the invariant is:

magnitude is the value of exactly the consecutive digits consumed so far, and it never exceeds the sign-specific limit.

Appending digit d preserves the numeric part of the invariant because decimal concatenation is magnitude * 10 + d. The overflow guard preserves the bound by returning before an invalid update occurs.

Stopping at the first non-digit preserves prefix semantics. The parser returns the longest legal numeric prefix rather than skipping invalid characters and resuming later.

Consider "1337c0d3":

Character	Action	Magnitude
1	consume	1
3	consume	13
3	consume	133
7	consume	1337
c	terminate	1337

For "-2147483649", the final digit is where the guard matters:

1. The negative limit is 2147483648.
2. The parser safely consumes through 214748364.
3. The next digit is 9.
4. Since 9 > 8, the candidate update is rejected.
5. The function returns -2147483648.

The exact boundary is accepted:

• "-2147483648" returns -2147483648.
• "-2147483649" clamps to -2147483648.
• "2147483647" returns 2147483647.
• "2147483648" clamps to 2147483647.

Test the Failure Boundaries

Test groups should target contract obligations rather than merely provide random inputs.

Test group	Examples	Expected behavior
Empty and spaces	"", " "	0
Sign without digits	"+", "-", "+-12"	0
Valid prefix with text	" +0012abc", "1337c0d3"	12, 1337
Text before digits	"words and 987"	0
Internal space	"0 123"	0
Repeated or late signs	"--5", "0-1"	0, 0
Punctuation terminator	"12.5"	12
Leading zeroes	"0000", "-00042"	0, -42
Exact bounds	"2147483647", "-2147483648"	Same values
Positive overflow	"2147483648"	2147483647
Negative overflow	"-2147483649"	-2147483648

Always pair each exact endpoint with the first value beyond it. Endpoints prove that valid values survive. One-step overflow proves that the guard compares the final digit correctly.

Complexity and the Transferable Pattern

Each character is inspected at most once:

• Time: O(n), where n is the string length
• Auxiliary space: O(1)

The reusable pattern is state tracking with a guarded invariant:

1. Write the legal phases.
2. Name the state each phase must maintain.
3. Derive the update from the representation.
4. Guard the next update before changing state.
5. Stop when the next transition is illegal.

That is the durable String to Integer (atoi) solution. The code is short because the state model is small—not because the edge cases disappeared. When an unfamiliar parser appears in an interview, start by naming its phases, then write the invariant that makes each transition safe.