String to Integer (atoi) – LeetCode 8 C++ Solution & Dry Run

1. Introduction

Writing a function to convert a string to an integer might sound trivial at first glance. After all, most programming languages have a built-in method like parseInt() or std::stoi() that does this instantly. However, implementing myAtoi (LeetCode 8) is a rite of passage in software engineering interviews for a reason: it is not a test of algorithmic complexity, but a rigorous examination of state management, edge case handling, and hardware constraints.

In backend engineering, data inputs from user forms, external APIs, or legacy databases are inherently untrusted and often malformed. Your system must parse this text robustly without crashing. Furthermore, this problem introduces a strict constraint: you are operating within a 32-bit environment. You cannot simply use a 64-bit integer (like long long in C++) as a safety net to catch overflows. You must detect mathematical overflow before it physically happens in memory.

In this article, we will break down the anatomy of a string parser and build a deterministic, production-ready myAtoi function.

2. Problem Statement

Description

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm follows a strict sequence of operations:

1. Whitespace: Read in and ignore any leading whitespace (" ").
2. Signedness: 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. Assume the result is positive if neither is present.
3. Conversion: Read in characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer. If no digits were read, the integer is 0.
4. Rounding (Overflow/Underflow): If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], round the integer to remain in the range. Specifically:
   • Values less than -2^31 should be clamped to -2^31 (Underflow).
   • Values greater than 2^31 - 1 should be clamped to 2^31 - 1 (Overflow).

Input

• A string s consisting of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Constraints

• 0 <= s.length <= 200

Examples

Example 1:

• Input: s = "42"
• Output: 42

Example 2:

• Input: s = " -042"
• Output: -42 (Explanation: Leading spaces are ignored. The '-' sign is read. Leading zeros are ignored).

Example 3:

• Input: s = "1337c0d3"
• Output: 1337 (Explanation: Parsing stops at 'c' because it is a non-digit).

Example 4:

• Input: s = "0-1"
• Output: 0 (Explanation: Parsing stops at '-' because a sign character is only valid at the very beginning).

Example 5:

• Input: s = "-91283472332"
• Output: -2147483648 (Explanation: The number is smaller than the 32-bit signed integer minimum, so it is clamped to -2147483648).

Approach 1: The "Cheat" Method (Using 64-bit Integers)

Intuition

When candidates first see this problem, the easiest way to handle the 32-bit overflow constraint is to bypass it entirely by using a 64-bit integer (long long in C++). You accumulate the digits into this massive 64-bit container, and if it exceeds the 32-bit limits, you simply clamp it and cast it back to an int.

Algorithm

1. Skip spaces.
2. Check for + or -.
3. Loop through characters. If it's a digit, add it to a long long accumulator.
4. If the accumulator exceeds INT_MAX (2147483647), return INT_MAX. If it drops below INT_MIN (-2147483648), return INT_MIN.

Why This Fails in Interviews

A strict interviewer will immediately flag this. The problem implicitly tests your ability to operate within a 32-bit environment (mimicking older hardware or strict memory-constrained embedded systems). Relying on a 64-bit data type is considered a "cheat."

If you accumulate into a standard 32-bit int and it overflows, C++ triggers Undefined Behavior (UB). The value might wrap around to a negative number, or the compiler might optimize out your checks entirely. Therefore, we must detect overflow before we perform the multiplication and addition.

Approach 2: Single-Pass Iteration with Pre-Emptive Overflow Checking (Optimal Solution)

Intuition

We need a deterministic approach that processes the string from left to right exactly once. We will use a while loop with an index pointer that advances through the string, moving through the distinct phases: Whitespace $\rightarrow$ Sign $\rightarrow$ Digits.

The hardest part is the Pre-Emptive Overflow Check.

We build the number digit by digit using the formula:

result = (result * 10) + current_digit

To prevent Undefined Behavior, we cannot execute this line if it's going to cause an overflow.

The 32-bit maximum is 2147483647.

Before we multiply result by 10 and add the current_digit, we check two conditions:

1. Is result already greater than 214748364 (which is INT_MAX / 10)?If yes, multiplying by 10 will definitely overflow, regardless of what the next digit is.
2. Is result exactly equal to 214748364?If yes, then multiplying by 10 gives 2147483640. Adding any digit greater than 7 will push it past 2147483647 (Overflow).

By applying this mathematical check before modifying our accumulator, we safely operate strictly within 32-bit constraints.

Algorithm

1. Initialize: index = 0, sign = 1, result = 0.
2. Whitespace: Advance index while s[index] == ' '.
3. Sign: If s[index] is '+' or '-', update the sign variable and advance index by 1. (Only check this once!).
4. Digit Accumulation: Loop while index < s.length() and s[index] is a valid digit ('0' to '9').
   • Extract the integer value of the character: digit = s[index] - '0'.
   • Overflow Check: If result > INT_MAX / 10 OR (result == INT_MAX / 10 && digit > 7):
     • If sign == 1, return INT_MAX.
     • If sign == -1, return INT_MIN.
   • Accumulate: result = (result * 10) + digit.
   • Advance index.
5. Return result * sign.

Dry Run

Input: s = " -42"

C++ Code

#include <iostream>
#include <string>
#include <climits>
#include <cctype>   // For isdigit()

using namespace std;

class Solution {
public:
    int myAtoi(string s) {

        // Pointer used to traverse the string.
        int i = 0;

        // Store the length of the string.
        int n = s.length();

        // Assume the number is positive initially.
        int sign = 1;

        // Variable to store the integer being built.
        int result = 0;

        // =====================================================
        // Phase 1: Skip all leading whitespace characters.
        // Example:
        // "   -42"  ---> "-42"
        // =====================================================
        while (i < n && s[i] == ' ') {
            i++;
        }

        // If the string contains only spaces,
        // there is no number to parse.
        if (i == n)
            return 0;

        // =====================================================
        // Phase 2: Check whether the number is
        // positive or negative.
        //
        // '+'  -> Positive
        // '-'  -> Negative
        //
        // Examples:
        // "+42"
        // "-42"
        // =====================================================
        if (s[i] == '-' || s[i] == '+') {

            // Update sign accordingly.
            sign = (s[i] == '-') ? -1 : 1;

            // Move to the next character.
            i++;
        }

        // =====================================================
        // Phase 3: Read consecutive digits.
        //
        // Stop immediately if a non-digit
        // character is encountered.
        //
        // Example:
        // "123abc"
        //
        // Reads only:
        // 123
        // =====================================================
        while (i < n && isdigit(s[i])) {

            // Convert character into integer.
            //
            // Example:
            // '7' - '0'
            // 55  - 48 = 7 (ASCII values)
            int digit = s[i] - '0';

            // =================================================
            // Phase 4: Overflow / Underflow Check
            //
            // Before computing:
            //
            // result = result * 10 + digit;
            //
            // verify that the operation is safe.
            //
            // INT_MAX = 2147483647
            //
            // If:
            //
            // result > 214748364
            //
            // then multiplying by 10 will overflow.
            //
            // If:
            //
            // result == 214748364
            //
            // then only digits up to 7 are safe.
            //
            // Example:
            //
            // 214748364 * 10 + 8
            //
            // becomes:
            //
            // 2147483648 (Overflow)
            // =================================================
            if (result > INT_MAX / 10 ||
                (result == INT_MAX / 10 && digit > 7)) {

                // Clamp the value within
                // 32-bit signed integer limits.
                return (sign == 1) ? INT_MAX : INT_MIN;
            }

            // =================================================
            // Safe to append the current digit.
            //
            // Example:
            //
            // result = 42
            // digit  = 5
            //
            // result = 42 * 10 + 5
            //        = 425
            // =================================================
            result = result * 10 + digit;

            // Move to the next character.
            i++;
        }

        // =====================================================
        // Phase 5: Apply the sign.
        //
        // Examples:
        //
        // result = 42
        // sign = -1
        //
        // answer = -42
        // =====================================================
        return result * sign;
    }
};

Complexity Analysis

• Time Complexity: $O(n)$, where $n$ is the length of the string. We iterate through the string exactly once.
• Space Complexity: $O(1)$. We only use a few integer variables (i, sign, result, digit), requiring constant extra space.

Alternative Approach: This problem can also be solved using a Deterministic Finite Automaton (DFA), where each parsing stage (whitespace, sign, digits, end) is represented as a state. While this makes the parser easier to extend for more complex input formats, the iterative solution presented here is simpler and is the approach most commonly used in coding interviews.

Interview Tips

• Vocalize the Constraints: Before writing a single line of code, explicitly ask the interviewer: "Can I assume a 64-bit integer is available for overflow checking, or should I strictly operate within a 32-bit environment?" Even if they allow 64-bit, demonstrating that you know the difference earns massive points.
• Explain the Magic Number 7: When writing digit > 7 in the overflow check, explain why. INT_MAX is 2147483647. The last digit is 7. INT_MIN is -2147483648. The last digit is 8.
  • Wait, doesn't digit > 7 fail for negative numbers ending in 8?
  • Actually, no! If the sign is negative and the string represents -2147483648, the digit processed will be 8. The condition digit > 7 evaluates to true, triggering the overflow return block: return (sign == 1) ? INT_MAX : INT_MIN;. Since sign is -1, it brilliantly returns INT_MIN (-2147483648), which is exactly the correct, mathematically accurate answer! This is a beautiful quirk of the algorithm you should highlight.
• Use Standard Library Helpers: Don't write if (s[i] >= '0' && s[i] <= '9') manually. Use #include <cctype> and the isdigit(s[i]) function. It shows you know the standard library.

Key Takeaways

1. Parsing is sequential. A robust parser follows strict phases (Whitespace $\rightarrow$ Sign $\rightarrow$ Digits). Do not mix these phases using complicated if statements inside a single for loop.
2. Prevent, don't react. In low-level programming, you must prevent memory thresholds from being crossed. Checking for overflow after math operations is too late.
3. Keep state minimal. We solved a complex edge-case problem using only three variables (i, sign, result), demonstrating optimal memory efficiency.

code link:

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

video link: