LeetCode Solution: 8. String to Integer (atoi)

Cracking atoi: How to Convert Strings to Integers with LeetCode 8

Hey everyone! 👋 Aaradhya here, diving into another exciting LeetCode challenge. Today, we're tackling problem 8: "String to Integer (atoi)". This one sounds simple – just convert a string to a number, right? Well, as we'll see, atoi is famous for its sneaky edge cases and makes for a fantastic exercise in robust parsing!

🧐 Problem Explanation: The atoi Gauntlet

Imagine you're building a calculator app, and users input numbers as text (like "123" or "-42"). Your job is to take that string and turn it into an actual integer your program can use for calculations. That's exactly what myAtoi(string s) asks us to do!

But it's not just a straightforward conversion. LeetCode throws in a few crucial rules that make this problem interesting:

1. Whitespace Whisperer: First things first, ignore any leading spaces. Think of it like trimming a string before you start reading the juicy bits.
   • Example: " -42" should become "-42" after ignoring spaces.
2. Sign Detective: After the spaces, look for a '-' or '+'. This determines if your number is negative or positive. If neither is present, assume it's a positive number.
   • Example: " -042" the '-' tells us it's negative. "42" is positive by default.
3. Digit Dynamo: Now, start reading digits (0-9) one by one. Keep going until you hit a character that isn't a digit, or you reach the end of the string.
   • Important: If you don't find any digits after handling whitespace and sign, the result is 0.
   • Example: "1337c0d3" becomes 1337 because c isn't a digit. "words and 987" becomes 0 because w isn't a digit.
4. Range Ranger (Clamping): The final integer must fit within the 32-bit signed integer range, which is [-2^31, 2^31 - 1].
   • INT_MAX is 2147483647.
   • INT_MIN is -2147483648.
   • If your number is too small (e.g., -99999999999), it gets "rounded" (clamped) to INT_MIN.
   • If your number is too big (e.g., 99999999999), it gets clamped to INT_MAX.

Let's quickly look at an example to tie it all together:

Input: s = " -042"

• Step 1 (Whitespace): " -042" -> We ignore the three leading spaces. Our reading starts at '-'.
• Step 2 (Signedness): "-042" -> We see '-', so our number will be negative.
• Step 3 (Conversion): "-042" -> We read 0, then 4, then 2. The 0 is a leading zero, so it doesn't change the value 42. We stop after 2 as the string ends.
• Step 4 (Rounding): The number is -42. This is well within INT_MIN and INT_MAX.
• Output: -42

See? There are quite a few rules to follow meticulously!

💡 Intuition: It's a State Machine!

My "aha!" moment for atoi usually comes when I realize it's not just one big transformation, but a sequence of small, specific steps. It's like a little state machine:

1. State 1: Looking for non-whitespace.
2. State 2: Looking for a sign (+ or -).
3. State 3: Accumulating digits.
4. State 4: Done, apply final checks.

The key insight is that we need to process the string character by character, making decisions and updating our current state (like the sign and the number we've built so far). And the most crucial "gotcha" to watch out for is integer overflow! Since result * 10 can quickly exceed INT_MAX, we need a way to detect and handle this before it actually overflows our int variable.

🚀 Approach: A Step-by-Step Breakdown

Let's break down how we can implement myAtoi in a robust, step-by-step manner. We'll use an iterative approach, which is generally cleaner for managing the sequential steps and overflow checks in this problem.

Step 0: Essential Tools and Constants

We'll need INT_MAX (2,147,483,647) and INT_MIN (-2,147,483,648) from the <climits> header to perform our range checks. We'll also use long long for our intermediate number to prevent overflow before we clamp it to int limits.

Step 1: Skip Leading Whitespace

We'll use an index i to iterate through the string. The first thing we do is advance i past any ' ' characters.

int i = 0;
while (i < s.length() && s[i] == ' ') {
    i++; // Move past the space
}

Step 2: Determine the Sign

After skipping spaces, the next non-space character (if any) could be a sign (+ or -).

• Initialize sign = 1 (defaulting to positive).
• If we find '-', set sign = -1.
• If we find '+', sign remains 1.
• In either case, increment i to move past the sign character.

int sign = 1; // Assume positive initially
if (i < s.length() && (s[i] == '-' || s[i] == '+')) {
    sign = (s[i] == '-') ? -1 : 1; // If it's '-', sign is -1, else 1
    i++; // Move past the sign character
}

Step 3: Convert Digits and Handle Overflow (The Heart of the Problem)

This is where we build our number and constantly check if it's getting too big or too small.

• We'll use a long long variable, let's call it result, initialized to 0. This is crucial because the number might temporarily exceed INT_MAX before we clamp it.
• We'll loop while i is within bounds and s[i] is a digit.
• Inside the loop:
  1. Extract the digit: int digit = s[i] - '0'; (e.g., '5' - '0' gives 5).
  2. Update result: result = result * 10 + digit; (This is how you build a number from digits).
  3. Perform Overflow Checks! This is the most critical part. We need to check at each step if result (even though it's long long) indicates that the final clamped int would go out of range.
     • For Positive Numbers: If sign is 1 and our result (which is always positive here) has already surpassed INT_MAX, we know the final answer must be INT_MAX. We can return INT_MAX immediately.
     • For Negative Numbers: If sign is -1 and our result (its absolute value) has surpassed the magnitude of INT_MIN (2147483648), we know the final answer must be INT_MIN. Remember INT_MIN's absolute value is INT_MAX + 1. So, if result > (long long)INT_MAX + 1, we return INT_MIN.
  4. Increment i to move to the next character.

long long result = 0; // Use long long to handle potentially large intermediate values

while (i < s.length() && isdigit(s[i])) { // Loop while we have digits
    int digit = s[i] - '0'; // Convert character digit to integer

    result = result * 10 + digit; // Build the number

    // Overflow check for positive numbers
    if (sign == 1 && result > INT_MAX) {
        return INT_MAX;
    }
    // Overflow check for negative numbers
    // Note: INT_MIN is -2147483648, while INT_MAX is 2147483647.
    // So, for negative numbers, the absolute value can be one larger than INT_MAX.
    if (sign == -1 && result > (long long)INT_MAX + 1) { 
        return INT_MIN;
    }

    i++; // Move to the next digit
}

Step 4: Apply Sign and Return

Finally, once we're done parsing all digits (or ran into a non-digit), we apply the determined sign to our result and cast it back to an int. Since we handled all overflows during step 3, this final cast will safely return the correct, clamped 32-bit integer.

return (int)(sign * result);

Combining all these steps gives us a complete and robust atoi function!

💻 Code: My atoi Implementation

#include <string>   // For std::string
#include <climits>  // For INT_MAX, INT_MIN
#include <cctype>   // For isdigit (good practice to include explicitly)

class Solution {
public:
    int myAtoi(std::string s) {
        int i = 0;

        // Step 1: Skip leading whitespace
        while (i < s.length() && s[i] == ' ') {
            i++;
        }

        // Step 2: Determine sign
        int sign = 1; // Assume positive initially
        if (i < s.length() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i] == '-') ? -1 : 1; // If it's '-', sign is -1, else 1
            i++; // Move past the sign character
        }

        // Step 3: Convert digits and handle overflow
        long long result = 0; // Use long long to handle potentially large intermediate values

        // Loop while we have characters and they are digits
        while (i < s.length() && std::isdigit(s[i])) { 
            int digit = s[i] - '0'; // Convert character digit to integer

            result = result * 10 + digit; // Build the number

            // Critical Overflow Checks!
            // If the number is positive and exceeds INT_MAX
            if (sign == 1 && result > INT_MAX) {
                return INT_MAX;
            }
            // If the number is negative and its absolute value exceeds the magnitude of INT_MIN
            // The magnitude of INT_MIN (-2147483648) is 2147483648, which is INT_MAX + 1.
            if (sign == -1 && result > (long long)INT_MAX + 1) { 
                return INT_MIN;
            }

            i++; // Move to the next digit
        }

        // Step 4: Apply sign and return the final integer
        return (int)(sign * result);
    }
};

⏱️ Time & Space Complexity Analysis

• Time Complexity: O(N)
  • We iterate through the input string s at most once. Each character is processed a constant number of times (whitespace skip, sign check, digit conversion). N is the length of the string.
• Space Complexity: O(1)
  • We only use a few constant-size variables (i, sign, result, digit). No additional data structures are created that depend on the input size.

✨ Key Takeaways

Solving atoi is more than just converting a string to a number; it's a masterclass in:

1. Careful Parsing: Breaking down a complex problem into sequential, manageable steps.
2. Edge Case Handling: Systematically addressing scenarios like leading spaces, signs, non-digit characters, and empty inputs.
3. Overflow Prevention: Understanding integer limits (INT_MAX, INT_MIN) and using a long long for intermediate calculations to proactively prevent data type overflows, followed by precise clamping.
4. Clarity: An iterative approach often makes the "state changes" and decision points clearer for problems like atoi.

This problem is a fantastic way to sharpen your attention to detail and write robust code. Keep practicing, and you'll be parsing strings like a pro in no time! Happy coding!

---

Author Account: aaradhyanegi009
Publishing Time: 2026-05-18 06:32:19