LeetCode #8 Medium

String to Integer (atoi)

Parse a string into a 32-bit integer the way C's atoi does: skip spaces, optional sign, digits until a non-digit, clamp to [−2³¹, 2³¹−1].

stringparsing

Open on LeetCode ↗

02

Intuition

This is a tiny state machine: whitespace → sign → digits → stop. The only real trap is overflow — clamp when the accumulating value crosses the 32-bit boundary, checking before it grows out of range in fixed-width languages.

How to spot this pattern

Not an algorithm problem — a specification problem. The whole difficulty is executing four phases in the right order and stopping at the first violation: skip spaces, read an optional sign, consume digits, clamp. Interviewers use it to see whether you read requirements carefully, so the discipline is to follow the spec literally rather than reach for a parser.

03

Approach

1

Three phases in order

Skip leading spaces only; read at most one sign; consume digits until the first non-digit ends parsing. Anything malformed before a digit → 0.

2

Accumulate and clamp

num = num*10 + digit. If it exceeds 2³¹−1, return the clamp (positive) or −2³¹ (negative). Python can check after; C/Java must check before multiplying.

3

Everything else is ignored

Trailing garbage after digits is fine — parsing simply stops.

04

Solution & live demo

▶1class Solution:
▶2    def myAtoi(self, s):
▶3        i, n = 0, len(s)
▶4        while i < n and s[i] == " ": i += 1
▶5        sign = 1
▶6        if i < n and s[i] in "+-":
▶7            sign = -1 if s[i] == "-" else 1
▶8            i += 1
▶9        num = 0
▶10        while i < n and s[i].isdigit():
▶11            num = num * 10 + int(s[i])
▶12            i += 1
▶13        num *= sign
▶14        return max(-2**31, min(2**31 - 1, num))

05

Common pitfalls

Using the language's own parser

✗ Wrong

return int(s.strip())

✓ Right

while i < n and s[i] == " ": i += 1
...
while i < n and s[i].isdigit(): ...

int() raises on "42abc", which the spec says should yield 42, and it accepts forms the spec rejects. The problem defines its own grammar — trailing junk simply ends the number rather than invalidating it.

Clamping only at the end without a bounded accumulator

✗ Wrong

num = num * 10 + int(s[i])   # in C++/Java this overflows first

✓ Right

num = max(-2**31, min(2**31 - 1, num))

Python integers are unbounded so the final clamp suffices, but a literal C++ or Java translation overflows during accumulation and the clamp then sees a wrapped value. In those languages the bound has to be checked inside the digit loop.

Accepting a sign anywhere

✗ Wrong

if s[i] in "+-": ...   # checked inside the digit loop

✓ Right

if i < n and s[i] in "+-":   # once, before digits
    ...
    i += 1

Exactly one sign is allowed, and only immediately before the digits. Re-checking inside the loop would accept "+-12" or "1-2", both of which should stop at the first invalid character.

06

Edge cases

" -42"

Spaces skipped, sign captured → −42.

"4193 with words" / "words 42"

First: parses 4193 then stops. Second: no leading digit → 0.

"-91283472332"

Below INT_MIN → clamps to −2147483648.

07

Complexity

Time

O(n)

Space

O(1)

Single forward scan.