String To Integer Atoi¶

Problem¶

Implement atoi which converts a string to a 32-bit signed integer. Handle leading whitespace, an optional ± sign, consecutive digits, and clamp the result to [-2^31, 2^31 - 1].

Approach¶

Linear scan with state tracking: skip whitespace, read optional sign, accumulate digits, clamp on overflow. Stop at first non-digit after sign processing.

When to Use¶

Parsing problems, state machine patterns. Tests attention to edge cases (whitespace, signs, overflow, trailing non-digits).

Complexity¶


Time	`O(n)`
Space	`O(1)`

Implementation¶

SolutionTestsChallenge

string_to_integer_atoi ¶

String to Integer (atoi) — convert a string to a 32-bit signed integer.

Problem

Implement atoi which converts a string to a 32-bit signed integer. Handle leading whitespace, an optional ± sign, consecutive digits, and clamp the result to [-2^31, 2^31 - 1].

Approach

Linear scan with state tracking: skip whitespace, read optional sign, accumulate digits, clamp on overflow. Stop at first non-digit after sign processing.

When to use

Parsing problems, state machine patterns. Tests attention to edge cases (whitespace, signs, overflow, trailing non-digits).

Complexity

Time: O(n) Space: O(1)

my_atoi ¶

my_atoi(s: str) -> int

Convert string s to a 32-bit signed integer.

my_atoi("42") 42 my_atoi(" -42") -42 my_atoi("4193 with words") 4193 my_atoi("-91283472332") -2147483648

Source code in src/algo/strings/string_to_integer_atoi.py

def my_atoi(s: str) -> int:
    """Convert string *s* to a 32-bit signed integer.

    >>> my_atoi("42")
    42
    >>> my_atoi("   -42")
    -42
    >>> my_atoi("4193 with words")
    4193
    >>> my_atoi("-91283472332")
    -2147483648
    """
    n = len(s)
    i = 0

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

    if i == n:
        return 0

    # read optional sign
    sign = 1
    if s[i] in ("+", "-"):
        if s[i] == "-":
            sign = -1
        i += 1

    # accumulate digits
    result = 0
    while i < n and s[i].isdigit():
        result = result * 10 + int(s[i])
        i += 1

    result *= sign

    # clamp to 32-bit signed range
    if result < INT_MIN:
        return INT_MIN
    if result > INT_MAX:
        return INT_MAX
    return result

tests/strings/test_string_to_integer_atoi.py

"""Tests for the string-to-integer (atoi) problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.strings.string_to_integer_atoi import INT_MAX, INT_MIN, my_atoi


class TestMyAtoi:
    def test_positive_number(self) -> None:
        assert my_atoi("42") == 42

    def test_negative_with_whitespace(self) -> None:
        assert my_atoi("   -42") == -42

    def test_trailing_non_digits(self) -> None:
        assert my_atoi("4193 with words") == 4193

    def test_overflow_positive(self) -> None:
        assert my_atoi("91283472332") == INT_MAX

    def test_overflow_negative(self) -> None:
        assert my_atoi("-91283472332") == INT_MIN

    def test_empty_string(self) -> None:
        assert my_atoi("") == 0

    def test_only_whitespace(self) -> None:
        assert my_atoi("   ") == 0

    def test_leading_non_digit(self) -> None:
        assert my_atoi("words and 987") == 0

    def test_plus_sign(self) -> None:
        assert my_atoi("+1") == 1

    @given(n=st.integers(min_value=INT_MIN, max_value=INT_MAX))
    def test_roundtrip_in_range(self, n: int) -> None:
        assert my_atoi(str(n)) == n

Implement it yourself

Run: just challenge strings string_to_integer_atoi

Then implement the functions to make all tests pass. Use just study strings for watch mode.

Reveal Solution

string_to_integer_atoi ¶

String to Integer (atoi) — convert a string to a 32-bit signed integer.

Problem

Implement atoi which converts a string to a 32-bit signed integer. Handle leading whitespace, an optional ± sign, consecutive digits, and clamp the result to [-2^31, 2^31 - 1].

Approach

Linear scan with state tracking: skip whitespace, read optional sign, accumulate digits, clamp on overflow. Stop at first non-digit after sign processing.

When to use

Parsing problems, state machine patterns. Tests attention to edge cases (whitespace, signs, overflow, trailing non-digits).

Complexity

Time: O(n) Space: O(1)

my_atoi ¶

my_atoi(s: str) -> int

Convert string s to a 32-bit signed integer.

my_atoi("42") 42 my_atoi(" -42") -42 my_atoi("4193 with words") 4193 my_atoi("-91283472332") -2147483648

Source code in src/algo/strings/string_to_integer_atoi.py

def my_atoi(s: str) -> int:
    """Convert string *s* to a 32-bit signed integer.

    >>> my_atoi("42")
    42
    >>> my_atoi("   -42")
    -42
    >>> my_atoi("4193 with words")
    4193
    >>> my_atoi("-91283472332")
    -2147483648
    """
    n = len(s)
    i = 0

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

    if i == n:
        return 0

    # read optional sign
    sign = 1
    if s[i] in ("+", "-"):
        if s[i] == "-":
            sign = -1
        i += 1

    # accumulate digits
    result = 0
    while i < n and s[i].isdigit():
        result = result * 10 + int(s[i])
        i += 1

    result *= sign

    # clamp to 32-bit signed range
    if result < INT_MIN:
        return INT_MIN
    if result > INT_MAX:
        return INT_MAX
    return result