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].
- 0 <= s.length <= 200
- s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
Intuition
The string to integer atoi problem asks you to replicate C's atoi. There is no algorithmic difficulty here at all — the entire challenge is following the specification precisely and handling overflow. It is a problem about care rather than cleverness.
The parse is a small state machine that runs in a fixed order:
- Skip leading whitespace, read at most one optional sign, consume digits until a non-digit, then stop.
Order matters. Whitespace is only skipped at the front — a space after the sign invalidates the parse. At most one sign is allowed, so "+-2" is not −2, it is 0. And parsing stops at the first non-digit rather than failing, so "42abc" is 42 while "abc42" is 0.
The genuine trap is overflow. The result must be clamped to the 32-bit range [−2³¹, 2³¹−1], and in a fixed-width language the accumulator can wrap around before you get a chance to compare it. In C++ or Java the check must happen before the multiply: if the running value already exceeds (2³¹−1)/10, the next value * 10 will overflow. Python's unbounded integers let you check afterwards, which is why the same solution translated naively from Python to Java silently breaks.
When overflow is detected, return the boundary value for the sign rather than the wrapped result.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n) time and O(1) space.
Skip leading whitespace only
Advance past spaces at the front. Whitespace anywhere else ends the parse — a space after a sign or between digits is a terminator, not something to skip, and treating it otherwise silently accepts malformed input.
Read at most one sign
Accept a single + or - if present and record it. A second sign character is not a sign but a non-digit, which immediately ends parsing and yields 0 — the case "+-2" exists in the test set for exactly this reason.
Consume digits until a non-digit
Accumulate value = value * 10 + digit while characters are digits. The first non-digit ends the parse successfully with whatever has been read; trailing characters are simply ignored rather than treated as an error.
Check overflow before the multiply
In fixed-width languages, test whether value > (2³¹−1) / 10, or whether it equals that and the next digit exceeds 7, before performing the multiplication. Checking afterwards is too late — the value has already wrapped and the comparison sees garbage.
Clamp rather than wrap
On overflow return 2³¹−1 for a positive result and −2³¹ for a negative one. The problem asks for saturation at the boundary, not modular wraparound, and returning the wrapped value is the most common wrong answer.
Cost of the parse
A single pass over the string with constant work per character gives O(n) time and O(1) space. Every difficulty here is in the specification and the overflow boundary, not the complexity.
Solution & live demo
Common pitfalls
Using the language's own parser
return int(s.strip())
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
num = num * 10 + int(s[i]) # in C++/Java this overflows first
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
if s[i] in "+-": ... # checked inside the digit loop
if i < n and s[i] in "+-": # once, before digits
...
i += 1Exactly 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.
Edge cases
Spaces skipped, sign captured → −42.
First: parses 4193 then stops. Second: no leading digit → 0.
Below INT_MIN → clamps to −2147483648.