Code Implementation

class Solution:
    def myAtoi(self, s: str) -> int:
        i = 0
        n = len(s)
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31

        # 1. Skip leading whitespaces
        while i < n and s[i] == ' ':
            i += 1

        # 2. Check for sign
        sign = 1
        if i < n and (s[i] == '+' or s[i] == '-'):
            if s[i] == '-':
                sign = -1
            i += 1

        # 3. Convert digits to integer
        num = 0
        while i < n and s[i].isdigit():
            digit = int(s[i])
            # 4. Check for overflow
            if num > (INT_MAX - digit) // 10:
                return INT_MAX if sign == 1 else INT_MIN
            num = num * 10 + digit
            i += 1

        return sign * num
    

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, n = s.size();
        int sign = 1;
        long num = 0;
        const int INT_MAX = 2147483647;
        const int INT_MIN = -2147483648;

        // 1. Skip leading whitespaces
        while (i < n && s[i] == ' ') i++;

        // 2. Check for sign
        if (i < n && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }

        // 3. Convert digits to integer
        while (i < n && isdigit(s[i])) {
            int digit = s[i] - '0';
            if (num > (INT_MAX - digit) / 10) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            num = num * 10 + digit;
            i++;
        }
        return sign * num;
    }
};
    

class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        int sign = 1;
        long num = 0;
        int INT_MAX = Integer.MAX_VALUE;
        int INT_MIN = Integer.MIN_VALUE;

        // 1. Skip leading whitespaces
        while (i < n && s.charAt(i) == ' ') i++;

        // 2. Check for sign
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }

        // 3. Convert digits to integer
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            if (num > (INT_MAX - digit) / 10) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            num = num * 10 + digit;
            i++;
        }
        return (int) (sign * num);
    }
}
    

var myAtoi = function(s) {
    let i = 0, n = s.length;
    let sign = 1, num = 0;
    const INT_MAX = 2 ** 31 - 1;
    const INT_MIN = -(2 ** 31);

    // 1. Skip leading whitespaces
    while (i < n && s[i] === ' ') i++;

    // 2. Check for sign
    if (i < n && (s[i] === '+' || s[i] === '-')) {
        sign = s[i] === '-' ? -1 : 1;
        i++;
    }

    // 3. Convert digits to integer
    while (i < n && s[i] >= '0' && s[i] <= '9') {
        let digit = s[i] - '0';
        if (num > (INT_MAX - digit) / 10) {
            return sign === 1 ? INT_MAX : INT_MIN;
        }
        num = num * 10 + digit;
        i++;
    }
    return sign * num;
};
    

Problem Description

The "String to Integer (atoi)" problem asks you to convert a string s to a 32-bit signed integer, following these rules:

• Ignore any leading whitespace characters until the first non-whitespace character is found.
• The first sequence of characters may be a sign ('+' or '-') followed by as many numerical digits as possible.
• Ignore any non-digit characters that come after the initial digit sequence.
• If the integer is outside the 32-bit signed integer range ([-2^31, 2^31 - 1]), clamp the value to that range.
• If no valid conversion can be performed, return 0.

The goal is to parse the string according to these rules and return the resulting integer.

Thought Process

The problem seems simple at first, but there are several edge cases to consider, such as handling whitespace, optional signs, invalid characters, and integer overflow. A naive approach might try to use built-in conversion functions, but these won't handle all the edge cases or the overflow requirements.

Instead, we need to process the string character by character, making decisions at each step. Brute-force would involve trying to convert the entire string and then checking for errors, but that's risky and may not handle all scenarios.

The optimized approach is to:

• Skip leading whitespace
• Check for an optional sign
• Read in digits, stopping at the first non-digit
• Check for overflow while constructing the number
• Return the result, clamped to the 32-bit integer range if necessary

Solution Approach

• Step 1: Skip Leading Whitespaces
  • Start from the beginning of the string and increment the index until you find a non-whitespace character.
• Step 2: Handle Optional Sign
  • If the current character is '+' or '-', record the sign and move to the next character. Default to positive if there's no sign.
• Step 3: Convert Digits to Integer
  • Iterate over the next characters while they are digits, building the integer value one digit at a time.
• Step 4: Handle Overflow
  • Before adding a new digit, check if the current number will overflow the 32-bit signed integer range. If so, return the clamped value immediately.
• Step 5: Return the Result
  • Multiply the constructed number by the sign and return it as the result.

We use simple variables to track the current position, sign, and accumulated number. Checking for overflow before adding a new digit ensures we never exceed the allowed range.

Example Walkthrough

Let's walk through the input " -42abc":

1. Skip spaces: Index moves from 0 to 3 (now at '-').
2. Identify sign: '-' detected, so sign = -1, move index to 4.
3. Read digits: '4' and '2' are digits.
   • First, num = 4.
   • Next, num = 4 * 10 + 2 = 42.
4. Next character is 'a', which is not a digit, so we stop parsing.
5. Apply sign: result = -1 * 42 = -42.
6. No overflow, so return -42.

The function returns -42, as expected.

Time and Space Complexity

• Brute-force Approach:
  • If you tried to convert the whole string and then check for errors, you might traverse the string multiple times, but still O(n) time where n is the length of the string.
  • Space complexity is O(1), as only a few variables are used.
• Optimized Approach:
  • Each character is visited at most once, so time complexity is O(n).
  • Space complexity remains O(1) because we only use a few integer variables, regardless of input size.

The optimized approach is as efficient as possible for this problem.

Summary

The "String to Integer (atoi)" problem is a classic parsing challenge that requires careful attention to edge cases. By processing the string step-by-step—skipping whitespace, checking for a sign, reading digits, and handling overflow—we ensure robust behavior. The solution is efficient (O(n) time, O(1) space), elegant, and handles all specified constraints without relying on built-in conversion utilities.