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 treat it as a positive number.
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.
6. Return the integer as the result.

Example 1

Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position. Step 1: "42" (no leading whitespace) ^ Step 2: "+42" (no sign) ^ Step 3: "42" ("42" is read in) ^ Step 4: 42 (no sign) Step 5: 42 (in range) Step 6: 42

Example 2

Input: s = " -42" Output: -42 Explanation: Step 1: " -42" (leading whitespace is read and ignored) ^ Step 2: " -42" ('-' is read, so the result should be negative) ^ Step 3: " -42" ("42" is read in) ^ Step 4: -42 (the result is negated) Step 5: -42 (in range) Step 6: -42

Steps and Explanation

1. Whitespace Handling: We use TrimStart() to remove leading whitespace efficiently.

2. Sign Handling: We check the first character after trimming whitespace. If it's '+' or '-', we record the sign and move past it. Otherwise, we assume a positive sign.

3. Digit Extraction: We iterate through the remaining string, extracting digits until we encounter a non-digit character or reach the end. We use char.IsDigit() for efficient digit checking.

4. Integer Conversion: We build the integer using a long to handle potential overflow before clamping. We multiply by 10 in each iteration to build the number from its digits and add the current digit.

5. Overflow Handling: After building the integer, we check if it's outside the 32-bit signed integer range. If it's too large, we clamp it to int.MaxValue; if it's too small, we clamp it to int.MinValue.

6. Sign Application: Finally, we apply the recorded sign to the integer.

Code

public class Solution {
    public int MyAtoi(string s) {
        s = s.TrimStart(); // Remove leading whitespace
        if (string.IsNullOrEmpty(s)) return 0;

        long result = 0;
        int sign = 1;

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

        while (i < s.Length && char.IsDigit(s[i])) {
            result = result * 10 + (s[i] - '0');
            if (result * sign > int.MaxValue) return int.MaxValue;
            if (result * sign < int.MinValue) return int.MinValue;
            i++;
        }

        return (int)(result * sign); 
    }
}

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.