String to Integer (atoi) medium

Problem Statement

Implement the myAtoi(String s) 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 '+'. Record this sign (either '+' or '-'). If it is not either, then this is the first digit and it is 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. Change the sign as necessary (from step 2).
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 a whitespace character.
• Do not ignore any characters other than the leading whitespace or trailing non-digit characters.

Example 1:

Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position.

^42

Read in "42". The number is 42.

Example 2:

Input: s = " -42" Output: -42 Explanation:

   ^-42

Read in "-42". The number is -42.

Steps and Explanation

The solution involves several steps:

1. Whitespace Handling: We use trim() to remove leading and trailing whitespace.
2. Sign Detection: We check the first character to determine the sign (+ or -).
3. Digit Extraction: We iterate through the string, extracting digits until a non-digit character is encountered. We use Character.isDigit() for efficient digit checking.
4. Conversion to Integer: We build the integer using result = result * 10 + digit; . This avoids string concatenation, which is less efficient.
5. Overflow Handling: We check for integer overflow before assigning the final value to ensure it stays within the 32-bit signed integer range.
6. Return Value: We return the final calculated integer, considering the sign.

Code (Java)

class Solution {
    public int myAtoi(String s) {
        s = s.trim(); //Remove leading/trailing whitespace
        if (s.isEmpty()) return 0;

        int sign = 1;
        int i = 0;

        if (s.charAt(0) == '-') {
            sign = -1;
            i++;
        } else if (s.charAt(0) == '+') {
            i++;
        }

        long result = 0; //Use long to handle potential overflow
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            result = result * 10 + digit;

            //Check for overflow before assigning to int
            if (sign == 1 && result > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            } else if (sign == -1 && result > Integer.MAX_VALUE) {
                return Integer.MIN_VALUE;
            }
            i++;
        }

        return (int) (sign * result); //Cast back to int after overflow check.
    }
}

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). We use a constant amount of extra space.