String to Integer (atoi) medium
Description
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
The algorithm:
- Read in and ignore any leading whitespace
- Check if the next character is
'-'or'+'. Read this character in if it is either. This determines if the final result is negative or positive. - Read in next characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
- Convert these digits into an integer. If no digits were read, then the integer is
0. - Clamp the integer to the 32-bit signed integer range:
[-2^31, 2^31 - 1]
Examples
> Case 1:
Input: s = "42"
Output: 42
> Case 2:
Input: s = " -42"
Output: -42
> Case 3:
Input: s = "4193 with words"
Output: 4193
> Case 4:
Input: s = "words and 987"
Output: 0
> Case 5:
Input: s = "-91283472332"
Output: -2147483648
Explanation: Clamped to INT_MIN (-2^31)Constraints
0 <= s.length <= 200sconsists of English letters, digits,' ','+','-', and'.'
Approach: Sequential Parsing
Process the string character by character, handling each edge case in order.
Explanation
This problem is really about careful edge case handling. The algorithm follows four sequential steps:
- Skip whitespace — standard trimming from the left
- Determine sign — check for
+or-(default positive) - Extract digits — multiply running result by 10 and add current digit
- Overflow protection — clamp to
[-2^31, 2^31 - 1]before overflow actually occurs
The overflow trap: In C++ and Java, checking overflow after it happens is
undefined behavior. You must check before the multiplication: if
result > INT_MAX / 10 or result == INT_MAX / 10 && digit > 7, you will
overflow. The code above uses long to avoid this issue.
Why interviewers love this problem: It tests your ability to handle messy real-world input. The algorithm is simple, but the edge cases (empty string, only whitespace, only signs, overflow) catch most candidates.
Analysis
- Time Complexity:
O(n)— single pass through the string - Space Complexity:
O(1)— only uses a few variables