8. String to Integer (atoi)

Problem description

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(string s) 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 respectively. Assume the result is positive if neither is present.
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, "0032" -> 32). 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 [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
6. Return the integer as the final result.

---

Solution

The task of converting a string to a 32-bit signed integer is a common problem that arises in many programming languages. This is where the myAtoi(string s) function comes into play. Similar to the atoi function in C/C++, this function helps in converting a string to a signed integer. In this blog post, we’ll be discussing the algorithm for the myAtoi(string s) function and how to implement it.

Algorithm

1. Read in and ignore any leading whitespace The first step of the algorithm is to ignore any leading whitespaces present in the string. This is done to prevent any unnecessary errors that may arise due to such whitespaces.
2. Check for ‘-‘ or ‘+’ sign The next step is to determine the sign of the final result. If the next character (after ignoring any leading whitespaces) is ‘-‘ or ‘+’, we need to read in this character. If the character is ‘-‘, the final result will be negative. If the character is ‘+’, the final result will be positive. If neither is present, we can assume the result to be positive.
3. Read in the digits The next step is to read in the next set of digits present in the string. The digits are read until a non-digit character or the end of the input is reached. Any other remaining characters in the string are ignored.
4. Convert digits to integer Once the digits are read, we need to convert them into an integer. For example, the string “123” will be converted to 123, and the string “0032” will be converted to 32. If no digits were read, then the integer is 0. Also, the sign (from step 2) must be applied to the final result.
5. Clamping the integer In the final step, we need to ensure that the integer is within the 32-bit signed integer range [-231, 231 – 1]. If the integer falls outside this range, it must be clamped to the respective limit. For example, integers less than -231 should be clamped to -231, and integers greater than 231 – 1 should be clamped to 231 – 1.

The final result is the integer obtained after performing the above steps.

Code solution

C#

public int myAtoi(string s) {
    int i = 0, sign = 1, result = 0;
    while (i < s.Length && s[i] == ' ') { i++; }
    if (i < s.Length && (s[i] == '-' || s[i] == '+')) {
        sign = s[i] == '-' ? -1 : 1;
        i++;
    }
    while (i < s.Length && Char.IsDigit(s[i])) {
        int digit = s[i] - '0';
        if (result > (int.MaxValue - digit) / 10) {
            return sign == 1 ? int.MaxValue : int.MinValue;
        }
        result = result * 10 + digit;
        i++;
    }
    return sign * result;
}

Java

public int myAtoi(String s) {
    int i = 0, sign = 1, result = 0;
    while (i < s.length() && s.charAt(i) == ' ') { i++; }
    if (i < s.length() && (s.charAt(i) == '-' || s.charAt(i) == '+')) {
        sign = s.charAt(i) == '-' ? -1 : 1;
        i++;
    }
    while (i < s.length() && Character.isDigit(s.charAt(i))) {
        int digit = s.charAt(i) - '0';
        if (result > (Integer.MAX_VALUE - digit) / 10) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        result = result * 10 + digit;
        i++;
    }
    return sign * result;
}

C++

public:
    int myAtoi(string s) {
        int i = 0, sign = 1, result = 0;
        while (i < s.length() && s[i] == ' ') { i++; }
        if (i < s.length() && (s[i] == '-' || s[i] == '+')) {
            sign = s[i] == '-' ? -1 : 1;
            i++;
        }
        while (i < s.length() && isdigit(s[i])) {
            int digit = s[i] - '0';
            if (result > (INT_MAX - digit) / 10) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            result = result * 10 + digit;
            i++;
        }
        return sign * result;
    }

JS

function myAtoi(str) {
  let sign = 1, base = 0, i = 0;
  while (str[i] === ' ') { i++; }
  if (str[i] === '-' || str[i] === '+') {
    sign = str[i++] === '-' ? -1 : 1;
  }
  while (str[i] >= '0' && str[i] <= '9') {
    if (base >  2147483647 / 10 || (base === 2147483647 / 10 && str[i] - '0' > 7)) {
      if (sign === 1) return 2147483647;
      else return -2147483648;
    }
    base  = base * 10 + (str[i++] - '0');
  }
  return base * sign;
}

Python

def myAtoi(str):
    INT_MIN = -2147483648
    INT_MAX = 2147483647
    sign = 1
    base = i = 0
    while i < len(str) and str[i] == ' ':
        i += 1
    if i < len(str) and str[i] == '-':
        sign = -1
        i += 1
    elif i < len(str) and str[i] == '+':
        i += 1
    while i < len(str) and str[i].isdigit():
        base = base * 10 + int(str[i])
        if base > INT_MAX:
            return INT_MAX if sign > 0 else INT_MIN
        i += 1
    return sign * base

Conclussion

In conclusion, the time and space complexity of the problem “String to Integer (atoi)” function is O(n), where n is the length of the input string. This is because we loop through the string to ignore leading whitespaces, read in the sign and digits, and convert them into the final integer.

The space complexity is O(1) because we only need a constant amount of memory to store the final result and intermediate variables.

It is worth noting that the solution is efficient and optimized, as it only loops through the input string once and uses constant memory. This ensures that the function can handle large inputs without taking up excessive resources. The myAtoi(string s) function is a simple yet powerful tool for converting a string to a 32-bit signed integer.