LeetCode 8: String to Integer (atoi)

Problem Restatement

We are given a string s.

We need to implement myAtoi(s), which converts the beginning of the string into a signed 32-bit integer.

The parsing follows these rules:

1. Ignore leading spaces.
2. Read an optional sign, either + or -.
3. Read digits until a non-digit character appears.
4. If no digits are read, return 0.
5. Clamp the result into the signed 32-bit integer range.

The signed 32-bit range is:

[-2147483648, 2147483647]

If the value is smaller than -2147483648, return -2147483648.

If the value is larger than 2147483647, return 2147483647.

The current LeetCode statement uses these parsing and clamping rules.

Input and Output

Example function shape:

def myAtoi(s: str) -> int:
    ...

Examples

Example 1:

s = "42"

There are no leading spaces and no sign.

Read digits:

42

Output:

42

Example 2:

s = "   -042"

Ignore spaces.

Read sign:

-

Read digits:

042

The numeric value is 42.

Apply the sign:

-42

Output:

-42

Example 3:

s = "1337c0d3"

Read digits until the first non-digit:

1337

Stop at:

c

Output:

1337

Example 4:

s = "words and 987"

The first non-space character is not a sign or digit.

No conversion can be made.

Output:

0

Example 5:

s = "-91283472332"

The parsed value is less than -2147483648.

So we clamp it.

Output:

-2147483648

First Thought: Use Built-in Conversion

In Python, one might try to clean the string and call int.

But this quickly becomes messy because atoi does not parse the whole string.

For example:

"1337c0d3"

should return:

1337

But direct integer conversion would fail because the string contains letters.

The problem is mainly about implementing the parser manually.

Key Insight

We can read the string once from left to right.

The parser has four phases:

While reading digits, build the number using:

result = result * 10 + digit

For example:

"4193"

is built as:

0
4
41
419
4193

Algorithm

1. Set i = 0.
2. Skip leading spaces.
3. Read optional sign.
4. Initialize result = 0.
5. While i is inside the string and s[i] is a digit:
   • Convert s[i] into a digit.
   • Update result.
   • Clamp early if the value becomes too large.
6. Return sign * result.

Correctness

The algorithm skips exactly the leading spaces before parsing.

After spaces, it reads at most one sign. If no sign exists, the sign remains positive.

Then it reads consecutive digits only. The moment a non-digit appears, parsing stops, which matches the required atoi behavior.

During digit parsing, each new digit is appended to the right side of the current value:

result = result * 10 + digit

So after reading k digits, result equals the integer represented by exactly those k digits.

If no digits are read, result remains 0, so the function returns 0.

If the parsed value exceeds the signed 32-bit range, the algorithm returns the correct boundary value.

Therefore the algorithm returns exactly the integer defined by the parsing rules.

Complexity

Implementation

class Solution:
    def myAtoi(self, s: str) -> int:
        MIN_INT = -2**31
        MAX_INT = 2**31 - 1

        n = len(s)
        i = 0

        while i < n and s[i] == " ":
            i += 1

        sign = 1

        if i < n and s[i] in ["+", "-"]:
            if s[i] == "-":
                sign = -1
            i += 1

        result = 0

        while i < n and s[i].isdigit():
            digit = ord(s[i]) - ord("0")
            result = result * 10 + digit

            if sign == 1 and result > MAX_INT:
                return MAX_INT

            if sign == -1 and -result < MIN_INT:
                return MIN_INT

            i += 1

        return sign * result

Code Explanation

Define the integer boundaries:

MIN_INT = -2**31
MAX_INT = 2**31 - 1

Use an index to scan the string:

i = 0

Skip leading spaces:

while i < n and s[i] == " ":
    i += 1

Read the optional sign:

if i < n and s[i] in ["+", "-"]:
    if s[i] == "-":
        sign = -1
    i += 1

Build the integer digit by digit:

digit = ord(s[i]) - ord("0")
result = result * 10 + digit

Clamp overflow:

if sign == 1 and result > MAX_INT:
    return MAX_INT

if sign == -1 and -result < MIN_INT:
    return MIN_INT

Finally apply the sign:

return sign * result

Testing

def run_tests():
    s = Solution()

    assert s.myAtoi("42") == 42
    assert s.myAtoi("   -042") == -42
    assert s.myAtoi("1337c0d3") == 1337
    assert s.myAtoi("0-1") == 0
    assert s.myAtoi("words and 987") == 0
    assert s.myAtoi("-91283472332") == -2147483648
    assert s.myAtoi("91283472332") == 2147483647
    assert s.myAtoi("+1") == 1
    assert s.myAtoi("+-12") == 0
    assert s.myAtoi("   +0 123") == 0

    print("all tests passed")

run_tests()