DSA String to Integer (atoi)

The problem

String to integer conversion reads a number written as text and returns its value as an integer. The reader follows strict rules, in a fixed order. It is the conversion often called atoi, after the C function of the same name.

The rules are these. Leading spaces are skipped. One optional sign, + or -, may follow. Then digits are read until the first character that is not a digit, and everything after that point is ignored. A string with no digits at all converts to 0.

One more rule caps the value. The result must fit the signed 32-bit range, from -2147483648 to 2147483647. A number beyond either end is clamped to that end.

cases = [
    ("42", 42),
    ("   -42", -42),
    ("4193 with words", 4193),
    ("words 987", 0),
    ("+1", 1),
    ("91283472332", 2147483647),
    ("-91283472332", -2147483648),
]
for text, expected in cases:
    print(repr(text), "->", expected)

The last two rows are the clamping rows. The digits in 91283472332 describe a value far above the range. The answer is the top of the range, not the full value.

Intuition

Python already converts strings to integers. The first idea is to call int() and be done. That call handles some of the rules on its own and rejects the rest.

for text in ["42", "   -42", "+1", "4193 with words", "words 987"]:
    try:
        print(repr(text), "->", int(text))
    except ValueError:
        print(repr(text), "-> ValueError")
print(repr("91283472332"), "->", int("91283472332"), "(no clamping)")

The built-in accepts clean numbers, signs and surrounding spaces. It raises an error on the very inputs this problem is built around, where text follows or precedes the digits. It also never clamps, because Python integers grow without limit.

So the conversion has to be written by hand. The hand-written version is not a fallback. It is the only version that follows all the rules at once: skip spaces, read one sign, read digits, stop at the first non-digit, and clamp.

Brute force: isolate the token, then convert it

The straightforward hand-written method works in two stages. The first stage walks the string under the rules and cuts out the numeric token: the sign and the digit run. The second stage hands that token to int() and clamps the result.

This method reuses the built-in where the built-in is safe. The token holds only a sign and digits, so int() cannot fail on it. An empty digit run is handled before the call and gives 0.

def atoi_brute(text):
    i = 0
    n = len(text)
    while i < n and text[i] == " ":
        i += 1
    sign = ""
    if i < n and (text[i] == "+" or text[i] == "-"):
        sign = text[i]
        i += 1
    digits = ""
    while i < n and text[i].isdigit():
        digits += text[i]
        i += 1
    if digits == "":
        return 0
    value = int(sign + digits)
    return max(-2147483648, min(2147483647, value))

for text in ["42", "   -42", "4193 with words", "words 987", "91283472332"]:
    print(repr(text), "->", atoi_brute(text))

The method is correct. Its cost is structural. The string is walked once to isolate the token, then int() walks the token again to convert it, and the digit characters are copied into a new string along the way. The optimal version folds all of that into one pass with no token string at all.

The optimal solution: build the value digit by digit

Each new digit shifts the running value one decimal place left and adds itself, so the number is built during the same single pass that reads it. That one recurrence, value = value * 10 + digit, is the whole conversion.

Clamping happens during the build, not after it. Before each step, the code checks whether the step would pass the limit for the chosen sign. The positive limit is 2147483647 and the negative limit is 2147483648, because the negative side of the range reaches one step further. A step that would overflow returns the clamped end at once, and the remaining digits cannot change that answer.

def my_atoi(text):
    i = 0
    n = len(text)
    while i < n and text[i] == " ":
        i += 1
    sign = 1
    if i < n and (text[i] == "+" or text[i] == "-"):
        if text[i] == "-":
            sign = -1
        i += 1
    limit = 2147483647 if sign == 1 else 2147483648
    value = 0
    digits = 0
    while i < n and text[i].isdigit():
        digit = int(text[i])
        digits += 1
        if value > (limit - digit) // 10:
            return sign * limit
        value = value * 10 + digit
        i += 1
    if digits == 0:
        return 0
    return sign * value

cases = [
    ("42", 42),
    ("   -42", -42),
    ("4193 with words", 4193),
    ("words 987", 0),
    ("+1", 1),
    ("91283472332", 2147483647),
    ("-91283472332", -2147483648),
]
for text, expected in cases:
    print(repr(text), "->", my_atoi(text), "expected", expected)

All seven cases from the start of the article pass. The overflow check uses integer arithmetic only. Comparing value against (limit - digit) // 10 asks whether one more shift-and-add step still fits, without ever building a value outside the range.

Walkthrough

Follow the string ' -42' through the reader. The index, the sign and the running value are the whole state. Each phase below prints that state as it changes.

text = "   -42"
i = 0
while i < len(text) and text[i] == " ":
    i += 1
print("after spaces: index", i, "char", repr(text[i]))
sign = 1
if text[i] == "-":
    sign = -1
    i += 1
print("after sign: index", i, "sign", sign)
value = 0
while i < len(text) and text[i].isdigit():
    value = value * 10 + int(text[i])
    print("read", repr(text[i]), "-> value", value)
    i += 1
print("result:", sign * value)

Three spaces move the index to 3, where the minus sign sits. The sign phase records -1 and moves the index to 4. The digit phase then reads exactly two characters.

The first digit makes the value 4. The second digit shifts that to 40 and adds 2, giving 42. The string ends, the loop stops, and the stored sign turns the value into -42.

Complexity

The one-pass reader takes O(n) time, where n is the length of the string: each character is examined at most once across the space, sign and digit phases. It takes O(1) extra space, because the only state is the index, the sign and the running value.

def one_pass_steps(text):
    i = 0
    n = len(text)
    steps = 0
    while i < n and text[i] == " ":
        i += 1
        steps += 1
    if i < n and (text[i] == "+" or text[i] == "-"):
        i += 1
        steps += 1
    while i < n and text[i].isdigit():
        i += 1
        steps += 1
    return steps

for n in [10, 20, 40]:
    text = "0" * n + "7"
    print("length", len(text), "characters examined:", one_pass_steps(text))

These test strings are leading zeros followed by a 7, so the value stays tiny and no clamping shortcut fires. The examined count equals the length at every size. Doubling the string doubles the count, which is the linear growth the formula claims.

The brute-force method is also linear, but it walks the digit run twice and builds a token string. The one-pass version removes the second walk and the copy. Its space stays constant where the token method grows a string as long as the digit run.

Edge cases and pitfalls

A sign with no digits after it converts to 0. The digit counter is what separates that case from a real zero. Without the counter, a lone minus sign and the string 0 would be indistinguishable in the running value, and a string like '- 12' would need luck to answer 0. Here the space after the sign is a non-digit, the digit loop never runs, and the counter forces 0.

Leading zeros contribute nothing to the value. Each zero shifts the value and adds zero, so 00012 builds 0, 0, 0, 1 and 12 in turn. A negative zero is still zero, because the sign multiplies a value of 0.

Reading past the first non-digit is the most common failure. The digits after a letter are not a second number. The reader stops at the letter and never resumes, which is why ' -0012a42' answers -12 and not -1242.

def my_atoi(text):
    i = 0
    n = len(text)
    while i < n and text[i] == " ":
        i += 1
    sign = 1
    if i < n and (text[i] == "+" or text[i] == "-"):
        if text[i] == "-":
            sign = -1
        i += 1
    limit = 2147483647 if sign == 1 else 2147483648
    value = 0
    digits = 0
    while i < n and text[i].isdigit():
        digit = int(text[i])
        digits += 1
        if value > (limit - digit) // 10:
            return sign * limit
        value = value * 10 + digit
        i += 1
    if digits == 0:
        return 0
    return sign * value

tests = ["", "-", "+", "  -0012a42", "00000", "-0", "- 12",
         "2147483647", "2147483648", "-2147483648", "-2147483649"]
for text in tests:
    print(repr(text), "->", my_atoi(text))

The boundary rows deserve a close read. The exact ends of the range pass through unchanged. One past either end clamps back to that end. Overflow is therefore handled in both directions, at the exact boundary and beyond it.