Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
The algorithm for myAtoi(string s) is as follows:
" ").'-' or '+', assuming positivity if neither present.[-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.Return the integer as the final result.
Example 1:
Input: s = "42"
Output: 42
Explanation:
The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
Example 2:
Input: s = " -042"
Output: -42
Explanation:
Step 1: " -042" (leading whitespace is read and ignored)
^
Step 2: " -042" ('-' is read, so the result should be negative)
^
Step 3: " -042" ("042" is read in, leading zeros ignored in the result)
^
Example 3:
Input: s = "1337c0d3"
Output: 1337
Explanation:
Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
^
Example 4:
Input: s = "0-1"
Output: 0
Explanation:
Step 1: "0-1" (no characters read because there is no leading whitespace)
^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
^
Example 5:
Input: s = "words and 987"
Output: 0
Explanation:
Reading stops at the first non-digit character 'w'.
Constraints:
0 <= s.length <= 200s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.Problem Overview: Convert a string into a 32-bit signed integer following the behavior of the C/C++ atoi function. You must ignore leading whitespace, detect an optional sign, read consecutive digits, and clamp the result within the 32-bit signed integer range [-2^31, 2^31 - 1].
Approach 1: Iterative Parsing and Conversion (O(n) time, O(1) space)
This approach processes the string character by character while building the integer value. Start by skipping leading whitespace using a simple loop. Then check for a sign character (+ or -) and store the sign for later multiplication. Continue iterating through digits and convert each character using digit = ch - '0' (or equivalent in other languages). Update the result with result = result * 10 + digit while checking for overflow before the multiplication step. Overflow detection compares the current value against INT_MAX / 10 and clamps the output to INT_MAX or INT_MIN when limits are exceeded. This method works in a single pass over the string and uses only constant extra memory. It relies purely on sequential scanning and arithmetic operations, which makes it the most reliable solution in interviews and production code when parsing numeric values from a string.
Approach 2: Regular Expression Parsing (O(n) time, O(n) space)
A regular expression can isolate the valid numeric prefix before conversion. Use a pattern like ^\s*[+-]?\d+ to match optional whitespace, an optional sign, and a sequence of digits at the beginning of the string. Once the substring is extracted, convert it to an integer using the language's parsing utilities and clamp the result to the 32-bit range. This approach reduces manual parsing logic and keeps the code short, especially in Python or JavaScript where regex support is concise. However, it allocates additional memory for the match result and relies on the regex engine, which adds overhead compared to manual iteration. It still performs a linear scan internally because the regex engine processes the input sequentially.
Both approaches revolve around controlled parsing of a string while enforcing numeric limits. The core challenge is handling edge cases correctly: leading spaces, optional sign characters, early termination when a non-digit appears, and integer overflow. These conditions mimic how real parsers process user input.
Recommended for interviews: Iterative Parsing and Conversion. Interviewers expect you to manually handle whitespace, sign detection, digit accumulation, and overflow checks. Writing the parser yourself demonstrates strong understanding of string processing and low-level numeric manipulation. The regex method is concise but often considered a shortcut that hides the actual logic the problem is testing.
In this approach, we manually parse the string character by character. First, we skip any leading whitespace. Then, we determine the sign of the number by checking the next character. After we've set up the sign, we convert succeeding string characters to a number as long as they are digits, and check if the number overflows the 32-bit signed integer range. The iterative parsing continues until we encounter a non-numeric character.
The function begins by traversing any leading whitespace in the input string. If the next character is a '-' or '+', it sets the sign accordingly and moves to the next character. We update a 'result' variable as we iterate over each digit, checking against overflow conditions. This result is carefully treated as a long to avoid overflow, then cast to an int at the end. Edge cases, including overflow beyond 32-bit bounds, are also managed explicitly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string because we traverse the string once.
Space Complexity: O(1), since we only use a fixed amount of extra space.
Using regular expressions simplifies extracting the integer portion from a string. This involves defining a regular expression to match the pattern for potential number initializations, determining whether followed by valid digits until non-numeric encounters or string end, and then mathematically transforming results. While elegant, care still needs to be taken on handling sign and range boundaries.
This JavaScript function utilizes a regular expression to detect any leading spaces, an optional sign, and a sequence of digits at the start of the string. The parseInt utility parses the integer, which is tempered by limits for overflowing numbers using conditional returns.
Python
Time Complexity: O(n), regular expression parsing inspects the input sequence linearly.
Space Complexity: O(1), denoting the small constant space taken up by the quantitative calculation.
| Approach | Complexity |
|---|---|
| Iterative Parsing and Conversion | Time Complexity: O(n), where n is the length of the string because we traverse the string once. Space Complexity: O(1), since we only use a fixed amount of extra space. |
| Regular Expression Approach | Time Complexity: O(n), regular expression parsing inspects the input sequence linearly. Space Complexity: O(1), denoting the small constant space taken up by the quantitative calculation. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Parsing and Conversion | O(n) | O(1) | Best choice for interviews and production parsing when you must control whitespace, signs, and overflow behavior. |
| Regular Expression Parsing | O(n) | O(n) | Useful for quick implementations in scripting languages where regex extraction is simpler than manual parsing. |
Implement atoi | Convert string to integer • Techdose • 99,664 views views
Watch 9 more video solutions →Practice String to Integer (atoi) with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor