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 .
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;
0if no valid number is parsed from a sequence of non-digits after skipping leading whitespace.
Implicit Constraints & Edge Cases:
- Leading Whitespace: Must be skipped before checking for signs or digits. If only whitespace remains, return
0. - 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. - Digit Parsing: Stop reading as soon as a non-digit is encountered (e.g.,
.or space). This means"4193 with words"becomes4193, not an error, but stops at' '. - Overflow/Underflow: If the parsed number exceeds , clamp to that value. If it is less than , clamp to that value. Python handles large integers automatically, so we must manually enforce these bounds at the end of parsing.
- No Digits: If a sign or whitespace exists but no digits follow (e.g.,
" +"), return0.
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:
- We need to track our position (index) through the string.
- State transitions are deterministic: Skip whitespace -> Check Sign -> Accumulate Digits -> Stop at non-digit or end of string.
- Since we must handle overflow manually, we should accumulate the integer value and check bounds against
INT_MAX() andINT_MIN().
We can iterate through the characters once using an index pointer. This ensures 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:
- Initialize: Set
result = 0,sign = 1. Define integer limits (INT_MAXandINT_MIN). - Skip Whitespace: Iterate while the current character is
' '. If we reach the end of string here, return0. - Handle Sign: Check if the current char is
'+'or'-'. Updatesignaccordingly (1for positive,-1for 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.
- Correction: Actually, strictly following the prompt: “Read this character in if it is either.” If neither
- Accumulate Digits: While current char is a digit (
0-9):- Update result:
result = result * 10 + int(char). - Increment index.
- Update result:
- 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: , where 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: . 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
whileloop skips whitespace. If index reaches end (i >= n) before finding a sign or digit, it returns0. - 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,
resultremains0, and we return0. - 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_MINat 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 returns123.