String to Integer (atoi) medium

Problem Statement

Implement the myAtoi(str) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '+' or '-'. Read this character in if it is either. This determines if the final result is negative or positive.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e., "123" -> 123). If no digits were read, then the integer is 0. If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ - 1], then clamp the integer so that it remains in the range.
5. If the string is empty or contains only whitespace characters, the integer is 0.

Example 1:

Input: str = "42" Output: 42 Explanation: The underlined characters are what is read in, and the result is 42.

Example 2:

Input: str = " -42" Output: -42 Explanation: The underlined characters are what is read in, and the result is -42.

Steps

1. Whitespace Removal: Trim leading and trailing whitespace from the input string.
2. Sign Detection: Check the first character. If it's '+' or '-', store the sign and move to the next character. Otherwise, assume a positive sign.
3. Digit Extraction: Iterate through the string, extracting digits until a non-digit character is encountered.
4. Conversion and Validation: Convert the extracted digits to a number. Check for overflow/underflow. Clamp the result to the 32-bit signed integer range.

Explanation

The TypeScript code carefully handles each step of the algorithm. It uses regular expressions to efficiently remove whitespace and extract digits. Error handling ensures that the function gracefully manages invalid inputs and prevents integer overflow. The clamping logic ensures the final result always fits within the 32-bit signed integer range.

Code

function myAtoi(str: string): number {
    str = str.trim(); // Remove leading/trailing whitespace
    if (str.length === 0) return 0;

    let sign = 1;
    let i = 0;

    if (str[i] === '-') {
        sign = -1;
        i++;
    } else if (str[i] === '+') {
        i++;
    }

    let result = 0;
    while (i < str.length && !isNaN(Number(str[i]))) {
        const digit = parseInt(str[i]);
        if (result > Math.floor(Number.MAX_SAFE_INTEGER / 10) || (result === Math.floor(Number.MAX_SAFE_INTEGER / 10) && digit > 7)) {
            return sign === 1 ? Number.MAX_SAFE_INTEGER : Number.MIN_SAFE_INTEGER; // Handle overflow
        }
        result = result * 10 + digit;
        i++;
    }

    return result * sign;
}

Complexity

• Time Complexity: O(n), where n is the length of the input string. This is because we iterate through the string at most once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input string size.