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.
5. 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. Specifically, integers less than -2³¹ should be clamped to -2³¹, and integers greater than 2³¹ - 1 should be clamped to 2³¹ - 1.
6. Return the integer as the result.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only hold 32-bit signed integers. When the numerical value of the integer is out of the range of a 32-bit signed integer, return 2³¹ - 1 if it is positive, and -2³¹ if it is negative.

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 and Explanation

1. Whitespace Removal: The code first iterates through the input string to skip any leading whitespace characters.

2. Sign Determination: It then checks for an optional '+' or '-' sign. The sign is stored to determine the final sign of the integer.

3. Digit Extraction: The code iterates through the remaining characters, extracting digits until a non-digit character is encountered or the end of the string is reached.

4. Integer Conversion: The extracted digits are converted to an integer using a running total. We multiply the current total by 10 and add the next digit. This is efficient and avoids string concatenation.

5. Clamp to 32-bit Range: The resulting integer is checked against the limits of a 32-bit signed integer (-2³¹ to 2³¹ - 1). If it's outside this range, it's clamped to the appropriate boundary.

Code

def myAtoi(str):
    """
    Converts a string to a 32-bit signed integer.
    """
    str = str.strip()  # Remove leading/trailing whitespace
    if not str:
        return 0

    sign = -1 if str[0] == '-' else 1
    if str[0] in ['-', '+']:
        str = str[1:]

    result = 0
    for char in str:
        if not char.isdigit():
            break
        result = result * 10 + int(char)

    result *= sign
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    return max(min(result, INT_MAX), INT_MIN)

Complexity

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