8. String to Integer (atoi) – Solution [Brute-Force to Best]

8. String to Integer (atoi) 8. String to Integer (atoi) 8. String to Integer (atoi) 8. String to Integer (atoi)

Here’s the question link on LeetCode 8. String to Integer (atoi):

https://leetcode.com/problems/string-to-integer-atoi/description

Brute Force

We might think of using stoi() to convert the string into an integer.

int ans = stoi(s);

But this doesn’t handle all the requirements:

  • We need to ignore leading spaces and stop at the first non-digit.
  • We need to handle optional signs.
  • The number might overflow, and we need to clamp it instead of throwing an exception.

So let’s implement the conversion ourselves.

Optimal: Traverse the String – O(n)

We can solve this in a single traversal.

There are three main steps:

1. Skip leading spaces and determine the sign.

First, move past all leading spaces. Then check whether the next character is + or -.

while(i < n && s[i] == ' ')
    i++;

int sign = 1;

if(i < n && s[i] == '-') {
    sign = -1;
    i++;
}
else if(i < n && s[i] == '+') {
    i++;
}

2. Convert digits into a number.

We keep building our number using:

ans = ans * 10 + digit;

For example, "123":

  • 0 * 10 + 1 = 1
  • 1 * 10 + 2 = 12
  • 12 * 10 + 3 = 123

We continue until we encounter a non-digit.

3. Handle integer overflow.

This is the tricky part.

A 32-bit signed integer can store values between:

\[ -2147483648 \text{ and } 2147483647 \]

Before adding another digit, we need to check whether the next multiplication and addition would cause overflow.

We can use:

if(ans > INT_MAX / 10 ||
   (ans == INT_MAX / 10 && digit > 7))

Why 7?

Because INT_MAX is 2147483647, and its last digit is 7.

For a negative number, the absolute value can reach 2147483648, so we use 8 as the last digit limit.

If overflow happens, directly return INT_MAX or INT_MIN depending on the sign.

class Solution {
public:
    int myAtoi(string s) {
        int n = s.size();
        int i = 0;

        // Skip leading spaces
        while(i < n && s[i] == ' ')
            i++;

        // Determine sign
        int sign = 1;

        if(i < n && s[i] == '-') {
            sign = -1;
            i++;
        }
        else if(i < n && s[i] == '+') {
            i++;
        }

        long long ans = 0;

        // Convert digits
        while(i < n && s[i] >= '0' && s[i] <= '9') {
            long long digit = s[i] - '0';

            // Check overflow before multiplying
            if(ans > INT_MAX / 10 ||
               (ans == INT_MAX / 10 && digit > (sign == 1 ? 7 : 8))) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }

            ans = ans * (long long) 10 * 1LL + digit;
            i++;
        }

        return ans * sign;
    }
};
8. String to Integer (atoi) Optimal Solution

Leave a Reply