# String to Integer (atoi)
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/string-to-integer-atoi)
Canonical: https://scaleengineer.com/dsa/problems/string-to-integer-(atoi)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Databricks](https://scaleengineer.com/companies/databricks), [Niantic](https://scaleengineer.com/companies/niantic), [Valve](https://scaleengineer.com/companies/valve)
---
## Problem
Implement the `myAtoi(string s)` function, which converts a string to a 32-bit signed integer.

The algorithm for `myAtoi(string s)` is as follows:

1. **Whitespace**: Ignore any leading whitespace (`" "`).
2. **Signedness**: Determine the sign by checking if the next character is `'-'` or `'+'`, assuming positivity if neither present.
3. **Conversion**: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
4. **Rounding**: If the integer is out of the 32-bit signed integer range `[-231, 231 - 1]`, then round the integer to remain in the range. Specifically, integers less than `-231` should be rounded to `-231`, and integers greater than `231 - 1` should be rounded to `231 - 1`.

Return the integer as the final result.

**Example 1:**

**Input:** s = "42"

**Output:** 42

**Explanation:**

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^

**Example 2:**

**Input:** s = " -042"

**Output:** \-42

**Explanation:**

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros ignored in the result)
               ^

**Example 3:**

**Input:** s = "1337c0d3"

**Output:** 1337

**Explanation:**

Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
         ^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
             ^

**Example 4:**

**Input:** s = "0-1"

**Output:** 0

**Explanation:**

Step 1: "0-1" (no characters read because there is no leading whitespace)
         ^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
          ^

**Example 5:**

**Input:** s = "words and 987"

**Output:** 0

**Explanation:**

Reading stops at the first non-digit character 'w'.

**Constraints:**

* `0 <= s.length <= 200`
* `s` consists of English letters (lower-case and upper-case), digits (`0-9`), `' '`, `'+'`, `'-'`, and `'.'`.

# Approaches
## Pre-processing with Library Functions
This approach uses built-in string manipulation functions and the standard library's number parsing capabilities to simplify the implementation. It first cleans the input string by trimming whitespace, then identifies the sign and the numeric part. It uses `Long.parseLong` to convert the numeric string, which simplifies overflow detection, and then clamps the result to the 32-bit integer range. While functionally correct, this method is less efficient in terms of space compared to a single-pass approach.
**Time:** O(n) · **Space:** O(n)
**Pros:** The logic can be easier to follow by separating concerns: trimming, sign detection, and number parsing.; Leverages robust, built-in library functions, potentially reducing bugs in the core number conversion logic.
**Cons:** Creates intermediate strings (`trim()`, `substring()`), leading to O(n) space complexity in the worst case.; Relies on built-in parsing functions (`Long.parseLong()`) and exception handling, which might not be permitted in an interview context that aims to test your ability to implement the parsing logic from scratch.; The overhead of creating new strings and handling exceptions can make it slightly slower in practice than a direct, index-based approach.
### Explanation
The core idea is to break down the problem into distinct string processing steps. First, we handle the whitespace by calling `s.trim()`. Then, we manually inspect the first one or two characters to determine the sign of the number. After identifying the sign, we locate the substring that contains only the numerical digits. This substring is then passed to `Long.parseLong()`. We use `long` as an intermediate type because its range is much larger than `int`, making it easy to see if the number read from the string exceeds the `int` limits. After parsing, we apply the sign and then check if the resulting `long` value falls outside the `[Integer.MIN_VALUE, Integer.MAX_VALUE]` range. If it does, we return the appropriate clamped value; otherwise, we cast the `long` to an `int` and return it.

```java
class Solution {
    public int myAtoi(String s) {
        s = s.trim();
        if (s.isEmpty()) {
            return 0;
        }

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

        int endIndex = startIndex;
        while (endIndex < s.length() && Character.isDigit(s.charAt(endIndex))) {
            endIndex++;
        }

        String numStr = s.substring(startIndex, endIndex);
        if (numStr.isEmpty()) {
            return 0;
        }

        long result = 0;
        try {
            result = Long.parseLong(numStr);
        } catch (NumberFormatException e) {
            // The number is too large for a long, so it's definitely out of int range.
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }

        result *= sign;

        if (result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (result < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return (int) result;
    }
}
```
### Algorithm
1. Use the `trim()` method to remove leading and trailing whitespace from the input string `s`. This may create a new string.
2. If the trimmed string is empty, return 0.
3. Initialize `sign = 1` and `startIndex = 0` to parse the number.
4. Check the first character of the trimmed string. If it's `'-'`, set `sign = -1` and `startIndex = 1`. If it's `'+'`, set `startIndex = 1`.
5. Find the end of the continuous block of digits starting from `startIndex`. Let this be `endIndex`.
6. Extract the numeric part of the string using `substring(startIndex, endIndex)`.
7. If the numeric string is empty (e.g., input was `"+"` or `"-"`), return 0.
8. Use a `try-catch` block to parse the numeric string into a `long` using `Long.parseLong()`. Using `long` helps to detect overflows beyond the `int` range easily.
9. If `NumberFormatException` is caught, it means the number is too large even for a `long`, so it must be clamped. Return `Integer.MAX_VALUE` or `Integer.MIN_VALUE` based on the sign.
10. Multiply the parsed `long` value by `sign`.
11. Clamp the result to the 32-bit signed integer range. If it's greater than `Integer.MAX_VALUE`, return `Integer.MAX_VALUE`. If it's less than `Integer.MIN_VALUE`, return `Integer.MIN_VALUE`.
12. Cast the clamped `long` to `int` and return.

## Single Pass Simulation
This approach simulates the process described in the problem statement by iterating through the string a single time. It uses a few variables to keep track of the current position, the sign of the number, and the accumulated result. By processing the string character by character and building the number incrementally, it avoids creating any intermediate strings, making it highly efficient in terms of memory. The main challenge lies in correctly handling the integer overflow check before each digit is added to the result.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal space complexity of O(1) as it doesn't require creating new data structures or strings.; Optimal time complexity of O(n) as it only requires a single pass through the input string.; Directly implements the logic required by the problem without relying on library functions for the core conversion.
**Cons:** The logic for checking integer overflow (`result > Integer.MAX_VALUE / 10 || ...`) can be tricky to formulate correctly and is a common point of error.
### Explanation
This is the most optimal solution, achieving linear time complexity with constant extra space. We use a pointer, `index`, to scan the string from left to right. The algorithm follows the states specified in the problem description sequentially.

First, we advance the `index` to skip all leading whitespace. 

Second, we check the character at the current `index` for a sign (`'+'` or `'-'`). If a sign is found, we record it in a `sign` variable and advance the `index` again. 

Third, we enter a loop that continues as long as we encounter digits. Inside this loop, we perform the core logic. For each digit, we must first check if incorporating it into our current `result` will cause an overflow. The condition `result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)` cleverly checks this without needing to use a `long`. If this condition is met, we know the number is out of the 32-bit signed integer range, and we immediately return the clamped value (`Integer.MAX_VALUE` or `Integer.MIN_VALUE`). Otherwise, it's safe to update our result with `result = result * 10 + digit`. 

Finally, after the loop terminates, we apply the determined sign to the accumulated `result` and return it.

```java
class Solution {
    public int myAtoi(String s) {
        int index = 0;
        int sign = 1;
        int result = 0;
        int n = s.length();

        // 1. Skip leading whitespace
        while (index < n && s.charAt(index) == ' ') {
            index++;
        }

        // 2. Handle sign
        if (index < n && (s.charAt(index) == '+' || s.charAt(index) == '-')) {
            sign = (s.charAt(index) == '-') ? -1 : 1;
            index++;
        }

        // 3. Convert digits and handle overflow
        while (index < n && Character.isDigit(s.charAt(index))) {
            int digit = s.charAt(index) - '0';

            // Check for overflow before modifying result
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            result = result * 10 + digit;
            index++;
        }

        // 4. Apply sign and return
        return result * sign;
    }
}
```
### Algorithm
1. Initialize an index `i = 0`, `sign = 1`, and `result = 0`.
2. **Skip Whitespace:** Iterate through the string, incrementing `i` as long as the character at `s.charAt(i)` is a space.
3. **Check for Sign:** If `i` is still within the string's bounds, check if `s.charAt(i)` is `'+'` or `'-'`. If it is, update `sign` accordingly (`-1` for `'-'`) and increment `i`.
4. **Convert Number:** Iterate while `i` is within bounds and `s.charAt(i)` is a digit.
   a. Get the integer value of the digit: `digit = s.charAt(i) - '0'`.
   b. **Check for Overflow:** Before updating `result`, check if `result * 10 + digit` would exceed `Integer.MAX_VALUE`. The check is: `if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7))`. 
   c. If an overflow is detected, return `Integer.MAX_VALUE` if `sign` is `1`, or `Integer.MIN_VALUE` if `sign` is `-1`.
   d. If no overflow, update the result: `result = result * 10 + digit`.
   e. Increment `i`.
5. **Final Result:** Once the loop finishes (either by reaching the end of the string or a non-digit character), return `result * sign`.

# Solutions
### CSharp

```csharp
// https://leetcode.com/problems/string-to-integer-atoi/ public partial class Solution { public int MyAtoi ( string str ) { int i = 0 ; long result = 0 ; bool minus = false ; while ( i < str . Length && char . IsWhiteSpace ( str [ i ])) { ++ i ; } if ( i < str . Length ) { if ( str [ i ] == '+' ) { ++ i ; } else if ( str [ i ] == '-' ) { minus = true ; ++ i ; } } while ( i < str . Length && char . IsDigit ( str [ i ])) { result = result * 10 + str [ i ] - '0' ; if ( result > int . MaxValue ) { break ; } ++ i ; } if ( minus ) result = - result ; if ( result > int . MaxValue ) { result = int . MaxValue ; } if ( result < int . MinValue ) { result = int . MinValue ; } return ( int ) result ; } }
```

### Java

```java
class Solution {
public
  int myAtoi(String s) {
    if (s == null)
      return 0;
    int n = s.length();
    if (n == 0)
      return 0;
    int i = 0;
    while (s.charAt(i) == ' ') {
      if (++i == n)
        return 0;
    }
    int sign = 1;
    if (s.charAt(i) == '-')
      sign = -1;
    if (s.charAt(i) == '-' || s.charAt(i) == '+')
      ++i;
    int res = 0, flag = Integer.MAX_VALUE / 10;
    for (int j = i; j < n; ++j) {
      if (s.charAt(j) < '0' || s.charAt(j) > '9')
        break;
      if (res > flag || (res == flag && s.charAt(j) > '7'))
        return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
      res = res * 10 + (s.charAt(j) - '0');
    }
    return sign * res;
  }
}

```

### JavaScript

```javascript
const myAtoi = function ( str ) { str = str . trim (); if ( ! str ) return 0 ; let isPositive = 1 ; let i = 0 , ans = 0 ; if ( str [ i ] === ' + ' ) { isPositive = 1 ; i ++ ; } else if ( str [ i ] === ' - ' ) { isPositive = 0 ; i ++ ; } for (; i < str . length ; i ++ ) { let t = str . charCodeAt ( i ) - 48 ; if ( t > 9 || t < 0 ) break ; if ( ans > 2147483647 / 10 || ans > ( 2147483647 - t ) / 10 ) { return isPositive ? 2147483647 : - 2147483648 ; } else { ans = ans * 10 + t ; } } return isPositive ? ans : - ans ; };
```

### CPP

```cpp
class Solution {
public:
  int myAtoi(string s) {
    int i = 0, n = s.size();
    while (i < n && s[i] == ' ')
      ++i;
    int sign = 1;
    if (i < n && (s[i] == '-' || s[i] == '+')) {
      sign = s[i] == '-' ? -1 : 1;
      ++i;
    }
    int res = 0;
    while (i < n && isdigit(s[i])) {
      int digit = s[i] - '0';
      if (res > INT_MAX / 10 || (res == INT_MAX / 10 && digit > INT_MAX % 10)) {
        return sign == 1 ? INT_MAX : INT_MIN;
      }
      res = res * 10 + digit;
      ++i;
    }
    return res * sign;
  }
};

```

### Python

```python
class Solution:
    # only contains blank space if i == n : return 0 sign = - 1 if s [ i ] == '-' else 1 if s [ i ] in [ '-' , '+' ]: i += 1 res , flag = 0 , ( 2 ** 31 - 1 ) // 10 while i < n : # not a number, exit the loop if not s [ i ]. isdigit (): break c = int ( s [ i ]) # if overflows if res > flag or ( res == flag and c > 7 ): return 2 ** 31 - 1 if sign > 0 else - ( 2 ** 31 ) res = res * 10 + c i += 1 return sign * res
    def myAtoi(self, s: str) -> int: if not s: return 0 n = len(s) if n == 0: return 0 i = 0 while s[i] == ' ': i += 1

```