Implement Atoi

Implement Atoi (string to integer) looks trivial but is a classic interview trap. There is no clever data structure — the whole challenge is reading the string carefully, in the right order, and handling the messy edge cases that real input throws at you: leading spaces, an optional sign, trailing garbage, and overflow.

The slow way first

There is no slow-versus-fast tradeoff here — a single pass is already optimal at O(n). The "slow" mistake is instead a correctness one: trying to handle everything with a regex or by stripping characters out of order. People skip the sign before the spaces, forget that digits stop at the first letter, or never clamp the overflow. The fix is not a smarter algorithm; it is a disciplined left-to-right sweep where each stage runs in a fixed order.

The idea: one sweep, four stages

Walk the string once with an index i, doing four things in this exact order:

1. Skip leading spaces — advance i while the current character is a space.
2. Capture the sign — if the next character is + or -, record it and advance once.
3. Accumulate digits — while the current character is a digit, do value = value * 10 + digit, clamping to int32 as you go.
4. Stop at the first non-digit — the moment a non-digit appears, the number is done.

The key insight: order is everything. Spaces come before the sign, the sign comes before the digits, and the very first non-digit after the digits ends the scan. Clamping happens inside the digit loop so a long run of digits can never overflow a real 32-bit integer.

Walk through it

Step through the animation for " -42abc". The pointer i skips the three leading spaces (shown as ·), lands on - and records sign = -1, then reads 4 and 2, building value up to 42. When i reaches a — a non-digit — the loop stops. Finally we apply the sign: -1 * 42 = -42.

Pseudocode

i = 0, n = length of s
sign = +1, value = 0
INT_MIN = -2^31, INT_MAX = 2^31 - 1
 
skip while s[i] is a space:          # stage 1
    i += 1
if s[i] is "+" or "-":               # stage 2
    if it is "-": sign = -1
    i += 1
while s[i] is a digit:               # stage 3
    value = value * 10 + digit(s[i])
    clamp value to the int32 range
    i += 1
return sign * value                  # stage 4: first non-digit ended the loop

The Python solution

def my_atoi(s):
    i, n = 0, len(s)
    sign, value = 1, 0
    INT_MIN, INT_MAX = -2**31, 2**31 - 1
    while i < n and s[i] == " ":
        i += 1
    if i < n and s[i] in "+-":
        if s[i] == "-":
            sign = -1
        i += 1
    while i < n and s[i].isdigit():
        value = value * 10 + int(s[i])
        value = min(value, INT_MAX + (1 if sign < 0 else 0))
        i += 1
    return sign * value

• i, n track our position and the string length; sign and value are the answer being built.
• The first while loop skips leading spaces — this must run before anything else.
• The if s[i] in "+-" block captures the sign exactly once and advances past it.
• The second while loop accumulates digits: value * 10 + int(s[i]) shifts the running number and adds the new digit.
• The clamp line caps value at INT_MAX, or at INT_MAX + 1 when negative (so a negative result can reach INT_MIN). Applying sign at the end then gives the correct clamped boundary.
• s[i].isdigit() becoming false stops the loop at the first non-digit, ignoring any trailing junk.

Complexity

We touch each character at most once and keep only a few integer variables, so the solution is O(n) time and O(1) extra space. There is no faster approach — every character that could be part of the number has to be read.

When this pattern shows up

Practice