LeetCode 8: String to Integer (atoi)

Problem Statement

LeetCode 8, String to Integer (atoi), is a medium-level challenge where you convert a string s into a 32-bit signed integer, following specific rules similar to the atoi function in C. You start reading the string, skip leading whitespace, handle an optional sign (+ or -), then convert digits until a non-digit appears or the end is reached. The result must fit within the 32-bit signed integer range (-2³¹ to 2³¹ - 1, or -2,147,483,648 to 2,147,483,647), returning the boundary value if it overflows.

Constraints

0 <= s.length <= 200: String length is between 0 and 200.
s contains English letters, digits, spaces, and signs (+, -, .).
Output must be a 32-bit signed integer.

Example

Input: s = "42"
Output: 42
Explanation: Read "42" as the integer 42.

Input: s = "   -42"
Output: -42
Explanation: Skip spaces, read "-" and "42", so -42.

Input: s = "4193 with words"
Output: 4193
Explanation: Read "4193", stop at "w" since it’s not a digit.

Input: s = "words and 987"
Output: 0
Explanation: Start with "w", not a digit or sign, so return 0.

Understanding the Problem

Think of this as turning a messy string into a clean number. For " -42", you skip the spaces, note the minus sign, read "42", and get -42. Rules include:

Skip leading whitespace.
Look for an optional + or - sign, then digits.
Stop at the first non-digit after digits start.
If no digits come after whitespace or sign, or if the string starts with something else, return 0.
Cap the result at 32-bit bounds if it’s too big.

We’ll use:

Iterative Parsing: Process the string step by step.

Solution: Iterative Parsing

Explanation

This method walks through the string character by character, building the number while following the rules. We track the sign, collect digits, and check bounds.

Handle Empty String.

If the string is empty, return 0.

2. Skip Whitespace.

Move past any leading spaces to find the start.

3. Determine Sign.

Check for + or -, set the sign, and move forward. If no sign, assume positive.

4. Parse Digits.

Collect digits into a number, stopping at a non-digit or the end.

5. Check Overflow.

Ensure the result fits 32-bit bounds, adjusting to min or max if needed.

6. Return Result.

Apply the sign and return the final integer.

Step-by-Step Example

Example 1: s = "42"

We have the string "42" and want to turn it into the number 42.

Goal: Convert "42" to an integer.
Result for reference: 42, within 32-bit bounds.
Start: Set result to 0, sign to +1, position at 0.
Step 1: Check if empty.

"42" has characters, so keep going.

Step 2: Skip whitespace.

No spaces at the start, stay at position 0.

Step 3: Look for sign.

First character "4" isn’t + or -, so sign stays +1.

Step 4: Read digits.

"4" is a digit. Result = 0 * 10 + 4 = 4, move to position 1.
"2" is a digit. Result = 4 * 10 + 2 = 42, move to position 2.
End of string, stop.

Step 5: Check bounds.

42 is between -2,147,483,648 and 2,147,483,647, so it’s fine.

Step 6: Apply sign.

Sign is +1, so 42 * 1 = 42.

Finish: Return 42.

Matches the expected number.

Example 2: s = " -42"

Now, the string is " -42", and we want -42.

Goal: Convert " -42" to an integer.
Result for reference: -42, within bounds.
Start: Result at 0, sign at +1, position at 0.
Step 1: Not empty, proceed.
Step 2: Skip whitespace.

Position 0 is " ", move to 1.
Position 1 is " ", move to 2.
Position 2 is " ", move to 3.
Position 3 is "-", no more spaces.

Step 3: Check sign.

"-" at position 3, set sign to -1, move to 4.

Step 4: Read digits.

"4" at 4, Result = 0 * 10 + 4 = 4, move to 5.
"2" at 5, Result = 4 * 10 + 2 = 42, move to 6.
End of string, stop.

Step 5: Check bounds.

42 is fine, no overflow.

Step 6: Apply sign.

Sign is -1, so 42 * -1 = -42.

Finish: Return -42.

Correctly handles spaces and sign.

Example 3: s = "4193 with words"

For "4193 with words", we want 4193.

Goal: Get the number part before words.
Result for reference: 4193, within bounds.
Start: Result at 0, sign at +1, position at 0.
Step 1: Not empty.
Step 2: No spaces, stay at 0.
Step 3: "4" isn’t a sign, sign stays +1.
Step 4: Read digits.

"4", Result = 0 * 10 + 4 = 4, move to 1.
"1", Result = 4 * 10 + 1 = 41, move to 2.
"9", Result = 41 * 10 + 9 = 419, move to 3.
"3", Result = 419 * 10 + 3 = 4193, move to 4.
" " (space) isn’t a digit, stop.

Step 5: 4193 is within bounds.
Step 6: Sign is +1, so 4193 * 1 = 4193.
Finish: Return 4193.

Stops at the first non-digit.

Example 4: s = "words and 987"

For "words and 987", we want 0.

Goal: Convert, but check what starts the string.
Result for reference: 0, since it starts with letters.
Start: Result at 0, sign at +1, position at 0.
Step 1: Not empty.
Step 2: No spaces, stay at 0.
Step 3: Check sign or digit.

"w" at 0 isn’t a sign or digit, stop here.

Step 4: No digits read yet, so result stays 0.
Step 5: 0 is within bounds.
Step 6: Sign doesn’t apply, still 0.
Finish: Return 0.

Nothing valid at the start, so 0.

Code

def myAtoi(s: str) -> int:
    if not s:
        return 0

    # Skip whitespace
    i = 0
    while i < len(s) and s[i].isspace():
        i += 1

    # Check if we’re at the end
    if i >= len(s):
        return 0

    # Handle sign
    sign = 1
    if s[i] == '-':
        sign = -1
        i += 1
    elif s[i] == '+':
        i += 1

    # Parse digits
    result = 0
    while i < len(s) and s[i].isdigit():
        digit = int(s[i])
        # Check overflow before adding
        if result > 2**31 // 10 or (result == 2**31 // 10 and digit > 7):
            return 2**31 - 1 if sign == 1 else -2**31
        result = result * 10 + digit
        i += 1

    # Apply sign and final overflow check
    result *= sign
    if result > 2**31 - 1:
        return 2**31 - 1
    if result < -2**31:
        return -2**31

    return result

Complexity

Time Complexity: O(n) – One pass through the string, where n is its length.
Space Complexity: O(1) – Uses only a few variables.

Efficiency Notes

This is efficient, processing each character once and checking overflow inline, making it practical and fast.

Alternative: Regular Expression (Brief Mention)

Explanation

You could use a regex to extract the first valid number part (e.g., r'^\s*[-+]?\d+'), then convert it to an integer and check bounds. It’s shorter but less intuitive and slower due to regex overhead, so we prefer the iterative method.

Additional Example

For s = "2147483648":

Goal: Convert to integer, check overflow.
Reference: 2,147,483,648 exceeds 2,147,483,647, so 2,147,483,647.
Steps:

No spaces, sign +1.
Digits: 2, 1, 4, ..., 8.
Build: 2, 21, ..., 214748364.
Next digit 8 overflows (214748364 > 214748364), stop.

Result: Return 2,147,483,647 (max 32-bit).

Edge Cases

Empty: s = "" – Returns 0.
Overflow: s = "2147483648" – Returns 2,147,483,647.
Negative Overflow: s = "-2147483649" – Returns -2,147,483,648.
Invalid Start: s = "abc" – Returns 0.

Final Thoughts

Iterative Parsing: Clear, fast, and handles all rules well.
Practice Value: Teaches string parsing and boundary checking, key for real-world conversions.