Domain 2MediumCORE

String to Integer (atoi)

The task is to implement a string-to-integer converter that mimics the behavior of C/C++'s atoi function, but with specific parsing rules defined in Python. We are given an input string s. The output must be a 32-bit signed integer within the range $[-2^{31}, 2^{31} - 1]$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#String

8. String to Integer (atoi)

Model: qwen3.5:9b
Topics: Math,String
FAANG asked: 1
Acceptance rate: 15.7%


Problem Breakdown

The task is to implement a string-to-integer converter that mimics the behavior of C/C++‘s atoi function, but with specific parsing rules defined in Python. We are given an input string s. The output must be a 32-bit signed integer within the range [−231,231−1][-2^{31}, 2^{31} - 1].

Key Inputs & Outputs:

  • Input: A string containing digits, whitespace, signs (+, -), and other characters. Length up to 200.
  • Output: An integer clamped to the valid range if it exceeds limits; 0 if no valid number is parsed from a sequence of non-digits after skipping leading whitespace.

Implicit Constraints & Edge Cases:

  1. Leading Whitespace: Must be skipped before checking for signs or digits. If only whitespace remains, return 0.
  2. Sign Handling: A sign (+/-) can appear immediately after the first non-whitespace character. No other characters (like letters) are allowed between the start and the number sequence once parsing begins.
  3. Digit Parsing: Stop reading as soon as a non-digit is encountered (e.g., . or space). This means "4193 with words" becomes 4193, not an error, but stops at ' '.
  4. Overflow/Underflow: If the parsed number exceeds 231−12^{31} - 1, clamp to that value. If it is less than −231-2^{31}, clamp to that value. Python handles large integers automatically, so we must manually enforce these bounds at the end of parsing.
  5. No Digits: If a sign or whitespace exists but no digits follow (e.g., " +"), return 0.

Intuition

A naive approach might be to use Python’s built-in conversion like int(s), which fails immediately because it doesn’t respect the specific parsing rules regarding leading whitespace, signs, and stopping at non-digits. For example, int("42 words") raises a ValueError in standard logic or parses incorrectly depending on implementation details compared to C-style behavior.

The core insight is that this problem requires a state machine approach implemented via iteration:

  1. We need to track our position (index) through the string.
  2. State transitions are deterministic: Skip whitespace -> Check Sign -> Accumulate Digits -> Stop at non-digit or end of string.
  3. Since we must handle overflow manually, we should accumulate the integer value and check bounds against INT_MAX (231−12^{31} - 1) and INT_MIN (−231-2^{31}).

We can iterate through the characters once using an index pointer. This ensures O(N)O(N) time complexity without needing complex data structures like stacks or regexes, keeping memory usage minimal.

Approach

I will use a single pass over the string with an explicit index variable to manage state transitions clearly:

  1. Initialize: Set result = 0, sign = 1. Define integer limits (INT_MAX and INT_MIN).
  2. Skip Whitespace: Iterate while the current character is ' '. If we reach the end of string here, return 0.
  3. Handle Sign: Check if the current char is '+' or '-'. Update sign accordingly (1 for positive, -1 for negative). Move index forward only if a sign was found; otherwise stay on next character (which must be checked as digit in step 4).
    • Correction: Actually, strictly following the prompt: “Read this character in if it is either.” If neither + nor -, we proceed to read digits. So check for sign first after whitespace skip.
  4. Accumulate Digits: While current char is a digit (0-9):
    • Update result: result = result * 10 + int(char).
    • Increment index.
  5. Apply Sign & Clamp: Multiply by sign. Check if the final value exceeds limits and clamp it to valid range before returning.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string s. We iterate through each character at most once (skipping whitespace or reading digits). Once we hit a non-digit after starting digit parsing, we stop immediately; subsequent characters are ignored but not processed. In worst case (all digits), it’s linear scan.
  • Space Complexity: O(1)O(1). We use a fixed number of variables (result, sign, index limits) regardless of input size.

Solution

class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        
        i = 0
        n = len(s)
        
        # Step 1: Skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1
            
        if i >= n:
            return 0
            
        sign = 1
        start_index = i
        
        # Step 2: Check for optional '+' or '-'
        if s[i] in ['+', '-']:
            sign = -1 if s[i] == '-' else 1
            i += 1
        
        result = 0
        
        # Step 3 & 4: Read digits until non-digit is found
        while i < n and '0' <= s[i] <= '9':
            digit = int(s[i])
            
            # Check for overflow before multiplication to prevent creating huge ints unnecessarily, 
            # though Python handles them. We check bounds at the end anyway per spec logic.
            result = result * 10 + digit
            
            i += 1
        
        # Step 5: Apply sign and clamp
        final_result = sign * result
        
        if final_result > INT_MAX:
            return INT_MAX
        elif final_result < INT_MIN:
            return INT_MIN
            
        return final_result

Edge Cases Handled

  • Empty String / Only Whitespace: The initial while loop skips whitespace. If index reaches end (i >= n) before finding a sign or digit, it returns 0.
  • No Valid Number Found (e.g., “words”): After skipping whitespace, if the first non-whitespace char is not a sign/digit, the digit accumulation loop doesn’t run, result remains 0, and we return 0.
  • Sign Without Digits (e.g., ”+”, “-123a” -> 123): If only a sign exists followed by non-digits or end of string, result is calculated as sign * 0 = 0. Wait, strictly speaking if input is "+", loop for digits doesn’t run. Result stays 0. Correct behavior per spec (“If no digits were read… integer is 0”).
  • Overflow (e.g., “-91283472332”): The code calculates the full large number in Python, then clamps it to INT_MIN at return logic. This matches C/C++ behavior where overflow results in defined limits rather than wrapping around silently.
  • Leading Zeros (e.g., “00123”): Logic treats them as digits accumulating value (result = 0 -> 0 -> ... -> 123). Correctly returns 123.