Problem Description

The problem asks you to implement a function myAtoi(string s) that converts a string to a 32-bit signed integer, similar to C/C++'s atoi function.

The conversion follows these specific rules:

1. Skip leading whitespace: Any spaces at the beginning of the string should be ignored.

2. Determine the sign: After skipping whitespace, check if the next character is '-' or '+'. If it's '-', the number will be negative. If it's '+' or neither sign is present, the number will be positive.

3. Read digits: Convert consecutive digit characters into an integer. Skip any leading zeros and stop reading when you encounter a non-digit character or reach the end of the string. If no valid digits are found, return 0.

4. Handle overflow: The result must be within the range of a 32-bit signed integer [-2^31, 2^31 - 1], which is [-2147483648, 2147483647]. If the number would overflow:

   • Numbers less than -2^31 should return -2147483648
   • Numbers greater than 2^31 - 1 should return 2147483647

For example:

• Input: "42" → Output: 42
• Input: " -42" → Output: -42 (leading spaces are ignored)
• Input: "4193 with words" → Output: 4193 (reading stops at the first non-digit)
• Input: "words and 987" → Output: 0 (first non-whitespace character is not a digit or sign)
• Input: "-91283472332" → Output: -2147483648 (the number underflows the 32-bit range)

The solution needs to carefully handle edge cases like empty strings, strings with only spaces, and integer overflow situations during the conversion process.

Intuition

The key insight is to process the string character by character in a single pass, following the exact order of operations specified in the problem. We need to handle the conversion step-by-step like a state machine.

First, we recognize that we need to skip whitespaces until we find a meaningful character. This is straightforward - just keep moving our pointer forward while we see spaces.

For the sign detection, we only need to check once after skipping whitespaces. If we see a '-' or '+', we record it and move forward. The trick here is to use a sign variable that's either 1 or -1, which we can multiply with our final result.

The core challenge is building the integer while checking for overflow. The natural approach would be to build the number as result = result * 10 + digit, but we need to check for overflow before this operation happens, not after (since after might already cause overflow in our program).

To check for overflow preemptively, we observe that the maximum 32-bit integer is 2147483647. If our current result is greater than 214748364 (which is (2^31 - 1) // 10), then multiplying by 10 would definitely overflow. If our result equals 214748364, then we need to check if the next digit is greater than 7 (the last digit of 2147483647). This way, we can detect overflow before it actually happens.

The beauty of this approach is that we handle both positive and negative overflow with the same logic - we just return the appropriate boundary value based on the sign we detected earlier. This eliminates the need for separate overflow checking logic for positive and negative numbers.

By processing the string in a single linear scan and stopping as soon as we hit a non-digit character, we achieve an efficient O(n) solution that handles all edge cases elegantly.

Solution Approach

The implementation follows a linear traversal approach, processing the string character by character from left to right.

Step 1: Handle edge cases First, check if the string is empty or has zero length. If so, return 0 immediately as there's nothing to convert.

Step 2: Skip leading whitespaces Use an index pointer i starting at 0 and increment it while s[i] is a space character. If we reach the end of the string (all characters were spaces), return 0.

Step 3: Determine the sign Check if the character at position i is '-' or '+'. Store the sign as -1 for negative or 1 for positive. If a sign character is found, increment i to move past it.

sign = -1 if s[i] == '-' else 1
if s[i] in ['-', '+']:
    i += 1

Step 4: Convert digits with overflow checking Initialize the result as 0 and calculate the overflow threshold as flag = (2**31 - 1) // 10, which equals 214748364.

While traversing the remaining characters:

• If the current character is not a digit, break the loop
• Convert the character to an integer: c = int(s[i])
• Check for overflow before adding the digit:
  • If res > flag, multiplying by 10 will definitely overflow
  • If res == flag and c > 7, adding this digit will overflow (since 2147483647 ends with 7)
  • If overflow is detected, return 2**31 - 1 for positive or -(2**31) for negative numbers
• If no overflow, update the result: res = res * 10 + c
• Move to the next character: i += 1

Step 5: Return the final result Multiply the accumulated result by the sign and return it: sign * res

The clever part of this solution is the preemptive overflow check. By comparing against (2**31 - 1) // 10 and checking the last digit separately when equal, we avoid actual integer overflow in our calculation. This ensures the algorithm works correctly even in languages with fixed integer sizes.

The time complexity is O(n) where n is the length of the string, as we traverse it at most once. The space complexity is O(1) as we only use a few variables regardless of input size.

Example Walkthrough

Let's walk through the example " -42" to illustrate the solution approach:

Initial state:

• String: " -42"
• Index i = 0
• Result res = 0

Step 1: Skip leading whitespaces

• s[0] = ' ' → increment i to 1
• s[1] = ' ' → increment i to 2
• s[2] = ' ' → increment i to 3
• s[3] = '-' → not a space, stop

Step 2: Determine the sign

• s[3] = '-' → set sign = -1
• Since we found a sign character, increment i to 4

Step 3: Convert digits with overflow checking

• Set overflow threshold: flag = 214748364

First digit:

• s[4] = '4' → it's a digit
• Check overflow: res = 0 which is less than flag, so no overflow
• Update: res = 0 * 10 + 4 = 4
• Increment i to 5

Second digit:

• s[5] = '2' → it's a digit
• Check overflow: res = 4 which is less than flag, so no overflow
• Update: res = 4 * 10 + 2 = 42
• Increment i to 6

End of string:

• i = 6 equals string length, exit loop

Step 4: Return the result

• Final result: sign * res = -1 * 42 = -42

Let's also trace through an overflow example "-91283472332":

After skipping whitespace and handling sign:

• sign = -1, i = 1, res = 0

Converting digits:

• '9': res = 9
• '1': res = 91
• '2': res = 912
• '8': res = 9128
• '3': res = 91283
• '4': res = 912834
• '7': res = 9128347
• '2': res = 91283472
• '3': res = 912834723
• '3': Now res = 912834723 > flag = 214748364
  • Overflow detected! Since sign = -1, return -2147483648

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string s. The algorithm iterates through the string at most once. Specifically:

• The first while loop skips leading whitespaces - at most n iterations
• The second while loop processes digits - at most n iterations
• Each character is visited at most once, and all operations within the loops (comparison, digit conversion, arithmetic operations) take constant time O(1)
• Therefore, the overall time complexity is linear with respect to the input string length

Space Complexity: O(1). The algorithm uses only a constant amount of extra space regardless of the input size:

• Variables i, n, sign, res, flag, and c are all primitive types that occupy constant space
• No additional data structures (arrays, lists, etc.) are created that scale with the input size
• The space used remains constant throughout the execution

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Overflow Detection Timing

One of the most common mistakes is checking for overflow after performing the multiplication and addition operations, rather than before:

Incorrect approach:

result = result * 10 + current_digit
if result > 2**31 - 1:  # Too late! Overflow may have already occurred
    return 2**31 - 1 if sign > 0 else -(2**31)

Why it fails: In languages with fixed integer sizes, the multiplication result * 10 + current_digit might already cause an overflow before you can check it, leading to undefined behavior or incorrect wraparound values.

Correct approach: Check for potential overflow before the operation:

if result > overflow_threshold or (result == overflow_threshold and current_digit > 7):
    return 2**31 - 1 if sign > 0 else -(2**31)
result = result * 10 + current_digit

2. Forgetting the Edge Case for Negative Overflow

Another pitfall is incorrectly handling the asymmetry between positive and negative 32-bit integer limits. The range is [-2^31, 2^31 - 1], meaning the minimum value (-2147483648) has a larger absolute value than the maximum (2147483647).

Incorrect approach:

if result > overflow_threshold or (result == overflow_threshold and current_digit > 7):
    return 2**31 - 1  # Always returns MAX_INT, ignoring sign

Correct approach: Consider the sign when returning overflow values:

if result > overflow_threshold or (result == overflow_threshold and current_digit > 7):
    return 2**31 - 1 if sign > 0 else -(2**31)

3. Not Handling Multiple Sign Characters

A subtle pitfall is not properly moving past the sign character, which could lead to returning 0 when encountering strings like "+123":

Incorrect approach:

sign = -1 if s[index] == '-' else 1
# Forgot to increment index past the sign character!

Correct approach:

sign = -1 if s[index] == '-' else 1
if s[index] in ['-', '+']:
    index += 1  # Move past the sign character

4. Using String Slicing Instead of Index Tracking

While tempting, using string slicing operations can lead to unnecessary string copies and potential index errors:

Inefficient approach:

s = s.strip()  # Creates a new string
if s[0] == '-':
    sign = -1
    s = s[1:]  # Another string copy

Better approach: Use index tracking to avoid creating new strings:

while index < n and s[index] == ' ':
    index += 1

These pitfalls highlight the importance of careful boundary checking, proper overflow handling, and efficient string traversal when implementing the atoi function.