LeetCode Solution: 8. String to Integer (atoi)

#leetcode #dsa #programming #tutorial

From Characters to Numbers: Cracking LeetCode's "String to Integer (atoi)"

Welcome, future coding wizards! 👋 Today, we're diving into a classic LeetCode problem that might seem straightforward at first glance but hides a surprising number of tricky edge cases: Problem 8, "String to Integer (atoi)".

If you've ever used a parseInt() function in JavaScript, int() in Python, or stoi() in C++, you know the basic idea: convert a string of digits into a numerical integer. LeetCode's myAtoi asks us to implement this ourselves, but with a precise set of rules that mimic how these functions often work internally. Let's break it down!

The Problem: More Than Just Converting Digits

Imagine you're building a calculator app, and users might type in numbers like "42", " -042", or even "1337c0d3". Your app needs to convert these strings into actual numbers, but also handle unexpected inputs gracefully.

The myAtoi(string s) function needs to perform the conversion following these specific steps:

Whitespace: First, skip any leading spaces (' ') until you hit a non-space character.
Signedness: Check the very next character. Is it '-'? Then the number is negative. Is it '+'? Then the number is positive. If neither, assume it's positive. After checking, move past this sign character.
Conversion: Now, read all consecutive digits ('0' through '9'). Stop when you encounter a non-digit character or reach the end of the string.
- Crucially, ignore any leading zeros during this conversion (e.g., "042" becomes 42).
- If no digits were read at all after the sign (or lack thereof), the result is 0.
Rounding (Clamping): Since we're dealing with a 32-bit signed integer, the final number must fit within its range: [-2^31, 2^31 - 1]. That's roughly [-2,147,483,648, 2,147,483,647].
- If your calculated number is smaller than -2^31, it becomes -2^31.
- If it's larger than 2^31 - 1, it becomes 2^31 - 1.

Finally, return the integer!

Let's look at a few examples:

Input: "42"
- No leading whitespace.
- No sign.
- Reads "42" -> 42.
- Within range. Output: 42
Input: " -042"
- Skips " ".
- Sees '-', so negative.
- Reads "042" -> 42.
- Applies sign: -42.
- Within range. Output: -42
Input: "1337c0d3"
- No leading whitespace or sign.
- Reads "1337". Stops at 'c'.
- Within range. Output: 1337
Input: "words and 987"
- No leading whitespace.
- No sign.
- First character 'w' is not a digit. No digits read.
- Output: 0

Intuition: A State-Machine in Disguise 🧠

At its core, myAtoi isn't just a single conversion step; it's a parsing process. Think of it like a mini-robot reading the string, changing its behavior based on what character it sees next. This kind of problem often benefits from thinking about it as a sequence of distinct states or phases:

Skipping Phase: "I'm looking for the first meaningful character."
Sign Phase: "Now I need to know if this number is positive or negative."
Number Building Phase: "Okay, now I'm collecting digits to build the number."
Finalization Phase: "I'm done reading digits; let's check if it fits and return."

The "aha!" moment comes when you realize that each step of the problem description directly maps to one of these phases. The biggest challenge isn't the basic conversion (char to int), but meticulously handling the order of operations, the edge cases (like empty strings or no digits), and especially, preventing integer overflow/underflow!

Our Step-by-Step Approach

Let's break down how we'll implement this myAtoi function using a clear, methodical approach. We'll use an indx (index) to keep track of our current position in the string.

Initialization:
- Get the length of the string, n.
- Initialize our indx to 0.
- Set sign to 1 (assuming positive by default).
- Initialize a result variable to 0. This result will hold the numerical value we're building. Crucially, use a long long for result to temporarily store numbers larger than INT_MAX or smaller than INT_MIN before we clamp them. This helps us detect overflow accurately.
Skip Leading Whitespace:
- Use a while loop: while (indx < n && s[indx] == ' ').
- Inside the loop, simply increment indx. This moves our pointer past all leading spaces.
Determine Signedness:
- After skipping spaces, check if indx is still within bounds (indx < n).
- If s[indx] is '+' or '-', we've found a sign.
- If s[indx] is '-', set sign to -1.
- In either case (+ or -), increment indx to move past the sign character.
Convert Digits and Handle Overflow:
- Now, we enter a while loop that continues as long as indx is within bounds AND s[indx] is a digit (isdigit(s[indx])).
- Inside the loop:
  - Extract the digit: int digit = s[indx] - '0'; (e.g., '5' - '0' gives 5).
  - THE OVERFLOW CHECK (This is the trickiest part!): Before adding the new digit to result, we need to check if result * 10 + digit would cause an overflow.
    - For positive numbers: INT_MAX is 2,147,483,647.
      - If result (our current positive magnitude) is already greater than INT_MAX / 10 (which is 214,748,364), then multiplying by 10 will definitely overflow.
      - If result equals INT_MAX / 10, then digit can be at most 7 (INT_MAX's last digit). If digit is 8 or 9, it will overflow.
      - So, if result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7), return INT_MAX.
    - For negative numbers: INT_MIN is -2,147,483,648. Its absolute value (magnitude) is 2,147,483,648.
      - We are building result as a positive magnitude. So, we check if this magnitude would exceed abs(INT_MIN).
      - If result is already greater than INT_MAX / 10 (which is 214,748,364), or if result equals INT_MAX / 10 and digit is greater than 8 (because abs(INT_MIN) ends in 8), then it will overflow negatively.
      - So, if result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 8), return INT_MIN.
  - Update result: result = result * 10 + digit;
  - Increment indx.
Return Final Result:
- Once the digit reading loop finishes, multiply result by sign to apply the determined sign.
- Cast the long long result back to int and return it. The clamping logic in step 4 ensures it's already within int range.

The Code ✨

Here's the C++ implementation following our approach:

#include <string>   // For std::string
#include <climits>  // For INT_MAX, INT_MIN
#include <cctype>   // For isdigit

class Solution {
public:
    int myAtoi(std::string s) {
        int n = s.length();
        int indx = 0;
        int sign = 1;         // Default sign is positive
        long long result = 0; // Use long long to handle potential overflow before clamping

        // 1. Skip leading whitespace
        while (indx < n && s[indx] == ' ') {
            indx++;
        }

        // 2. Determine sign
        if (indx < n && (s[indx] == '+' || s[indx] == '-')) {
            if (s[indx] == '-') {
                sign = -1;
            }
            indx++; // Move past the sign character
        }

        // 3. Convert digits and handle overflow
        while (indx < n && isdigit(s[indx])) {
            int digit = s[indx] - '0'; // Convert char digit to int value

            // 4. Clamping (Overflow check)
            // If sign is positive, check against INT_MAX (2147483647)
            if (sign == 1) {
                // If result is already greater than INT_MAX / 10,
                // or if it's equal and the current digit would push it over INT_MAX
                if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
                    return INT_MAX;
                }
            }
            // If sign is negative, check against abs(INT_MIN) (2147483648)
            else { // sign == -1
                // Here, 'result' is the positive magnitude being built.
                // We compare it against the maximum positive magnitude possible (which is 2147483648 for INT_MIN).
                if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 8)) {
                    return INT_MIN;
                }
            }

            result = result * 10 + digit; // Accumulate the number
            indx++;
        }

        // 5. Return final result after applying the sign
        return (int)(sign * result);
    }
};

Time and Space Complexity Analysis

Time Complexity: O(N)
- We iterate through the input string s a maximum of one time (for skipping spaces, checking sign, and then collecting digits). Each character is visited at most once. N is the length of the string.
Space Complexity: O(1)
- We only use a few variables (n, indx, sign, result) whose space requirements do not depend on the input string's length. This is constant space.

Key Takeaways

Read Problem Carefully: LeetCode problems, especially those with many rules, demand meticulous attention to detail. Each sentence in the description often translates to a specific code block or condition.
State-Based Thinking: For parsing problems, mentally (or physically!) breaking down the process into distinct states (like "skipping whitespace," "reading sign," "reading digits") can simplify complex logic.
Edge Case Mastery: Handling an empty string, a string with only spaces, a string with only a sign, or a string where digits don't appear after the sign are all crucial. Our indx < n checks protect against out-of-bounds access.
The Overflow Trap: Integer overflow/underflow is a classic trap in competitive programming. Using a larger data type (long long) for intermediate calculations and performing pre-checks before accumulation (result * 10 + digit) is a robust strategy. Remember the specific INT_MAX / 10 and digit > X conditions!

This problem is a fantastic exercise in rigorous implementation and careful consideration of all possibilities. Keep practicing, and you'll master these tricky string problems in no time! Happy coding! 🚀

^{Author Account: Vansh2710 | Published: 2026-03-28 00:22:06}