Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

String to Integer (atoi)

MEDIUMProblemSolveExternal Links

Description

Implement a function that converts a string to a 32-bit signed integer, similar to the C/C++ atoi function.

The conversion follows these rules in order:

  1. Whitespace: Skip any leading space characters.
  2. Sign: If the next character is '-' or '+', record the sign. If neither is present, assume the number is positive. At most one sign character is allowed.
  3. Digits: Read consecutive digit characters ('0'–'9') and form the integer. Leading zeros are valid but do not affect the result. Stop reading as soon as a non-digit character is encountered or the string ends. If no digits are read at all, the result is 0.
  4. Overflow Clamping: If the resulting integer falls outside the 32-bit signed range [-2^31, 2^31 - 1], clamp it to the nearest boundary. Values below -2147483648 become -2147483648, and values above 2147483647 become 2147483647.

Return the final integer.

Examples

Example 1

Input: s = "42"

Output: 42

Explanation: There is no leading whitespace, no sign character, and the entire string consists of digits. The characters '4' and '2' form the number 42, which is within the 32-bit range.

Example 2

Input: s = " -042"

Output: -42

Explanation: Three leading spaces are skipped. The '-' sets the sign to negative. The digits '0', '4', '2' form the number 042, which equals 42 after ignoring the leading zero. Applying the negative sign gives -42.

Example 3

Input: s = "1337c0d3"

Output: 1337

Explanation: No whitespace or sign. The digits '1', '3', '3', '7' are read. At index 4 the character 'c' is not a digit, so reading stops. The number formed from the first four characters is 1337.

Example 4

Input: s = "words and 987"

Output: 0

Explanation: The very first character 'w' is not a whitespace, sign, or digit. Since no digits can be read before encountering a non-digit character, the result is 0. The digits '987' later in the string are never reached.

Constraints

  • 0 ≤ s.length ≤ 200
  • s consists of English letters (lower-case and upper-case), digits ('0'–'9'), spaces (' '), '+', '-', and '.'.

Editorial

Brute Force - Digit String Extraction

Intuition

Think of converting a string to a number the way you learned in school. You write down a number like '042' on paper first (the digit collection step), and then you read it as the number 42 (the conversion step). The atoi function works similarly — it handles some extra messiness first (leading whitespace, a possible sign), but the core idea is: collect the digit characters, then turn them into a number.

This two-phase approach — first collect, then convert — is the most intuitive way to think about string-to-integer conversion:

  • Phase 1 (Parse): Walk through the string character by character. Skip leading spaces, note if there is a minus or plus sign, and gather every consecutive digit character into a separate string.
  • Phase 2 (Convert): Take the pure digit string, convert it to a number, apply the sign, and clamp to the 32-bit range if needed.

The downside is that building an intermediate digit string uses extra memory, and converting a potentially very long digit string can be tricky in typed languages where even 64-bit integers have a limit.

Step-by-Step Explanation

Let's trace through with s = " -042":

Step 1: Start at index 0. s[0] = ' ' (space). This is whitespace — skip it. Move to index 1.

Step 2: s[1] = '-'. This is a sign character. Record sign = -1 (negative). Move to index 2.

Step 3: s[2] = '0'. This is a digit. Append '0' to our digit string. digit_str = "0". Move to index 3.

Step 4: s[3] = '4'. Another digit. Append '4'. digit_str = "04". Move to index 4.

Step 5: s[4] = '2'. Another digit. Append '2'. digit_str = "042". We have reached the end of the string, so digit collection is complete.

Step 6: Convert digit_str "042" to the integer 42. Leading zeros are naturally dropped during numeric conversion.

Step 7: Apply the sign: 42 × (-1) = -42. Check if -42 is within [-2147483648, 2147483647]. It is. Return -42.

Digit String Extraction — Collect Then Convert — Watch how we scan the input character by character, collect digit characters into a separate string, and then convert that string to a number with the appropriate sign.

Algorithm

  1. Initialize index i = 0 and sign = 1
  2. Skip whitespace: While s[i] is a space, increment i
  3. Read sign: If s[i] is '+' or '-', set sign accordingly and increment i
  4. Collect digits: While s[i] is a digit ('0'–'9'), append s[i] to a digit string and increment i
  5. Convert: If the digit string is empty, return 0. Otherwise convert the digit string to a number
  6. Apply sign: Multiply the number by sign
  7. Clamp: If the result is less than -2^31, return -2^31. If greater than 2^31 - 1, return 2^31 - 1
  8. Return the result

Code

#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, n = s.size();
        
        // Phase 1: Skip leading whitespace
        while (i < n && s[i] == ' ') i++;
        
        // Phase 2: Determine sign
        int sign = 1;
        if (i < n && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }
        
        // Phase 3: Collect digit characters into a string
        string digits;
        while (i < n && isdigit(s[i])) {
            digits += s[i];
            i++;
        }
        
        if (digits.empty()) return 0;
        
        // Phase 4: Convert digit string to number using long long
        long long result = 0;
        for (char c : digits) {
            result = result * 10 + (c - '0');
            // Stop early if already beyond int range
            if (result > (long long)INT_MAX + 1) break;
        }
        
        result *= sign;
        
        // Phase 5: Clamp to 32-bit signed integer range
        if (result < INT_MIN) return INT_MIN;
        if (result > INT_MAX) return INT_MAX;
        return (int)result;
    }
};
class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        i, n = 0, len(s)
        
        # Phase 1: Skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1
        
        # Phase 2: Determine sign
        sign = 1
        if i < n and s[i] in ('+', '-'):
            sign = -1 if s[i] == '-' else 1
            i += 1
        
        # Phase 3: Collect digits into a string
        digit_str = ""
        while i < n and s[i].isdigit():
            digit_str += s[i]
            i += 1
        
        if not digit_str:
            return 0
        
        # Phase 4: Convert string to number
        result = int(digit_str) * sign
        
        # Phase 5: Clamp to 32-bit range
        if result < INT_MIN:
            return INT_MIN
        if result > INT_MAX:
            return INT_MAX
        return result
class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        
        // Phase 1: Skip whitespace
        while (i < n && s.charAt(i) == ' ') i++;
        
        // Phase 2: Determine sign
        int sign = 1;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }
        
        // Phase 3: Collect digits into a StringBuilder
        StringBuilder digits = new StringBuilder();
        while (i < n && Character.isDigit(s.charAt(i))) {
            digits.append(s.charAt(i));
            i++;
        }
        
        if (digits.length() == 0) return 0;
        
        // Phase 4: Convert to number using long
        long result = 0;
        for (int j = 0; j < digits.length(); j++) {
            result = result * 10 + (digits.charAt(j) - '0');
            if (result > (long) Integer.MAX_VALUE + 1) break;
        }
        
        result *= sign;
        
        // Phase 5: Clamp
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        return (int) result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make one pass through the string to skip whitespace, read the sign, and collect digits (up to n characters). Then we make a second pass over the collected digit string to convert it to a number. Both passes are O(n) in the worst case, giving O(n) total.

Space Complexity: O(n)

The digit string stores up to n characters when the entire input consists of digits. This intermediate string is extra memory proportional to the input size.

Why This Approach Is Not Efficient

While the brute force runs in O(n) time, it has two notable weaknesses:

1. Extra Space for the Digit String — O(n):
The approach builds an intermediate string of digits before converting. If the input is 200 characters of digits, the digit string also uses 200 characters of memory. This O(n) extra space is unnecessary because we could build the number directly.

2. Fragile Overflow Handling:
In typed languages like C++ and Java, converting a very long digit string to a number is risky. A 200-digit number exceeds even a 64-bit long long (which holds at most ~19 digits). The brute force relies on early-break heuristics or language-specific big-integer support, making it fragile and non-portable.

The key insight is that we can build the integer digit-by-digit in a single pass, checking for overflow before each multiplication. This eliminates the digit string entirely (O(1) space), handles overflow precisely without needing larger integer types, and processes the string in exactly one pass.

Optimal Approach - Single-Pass with Overflow Detection

Intuition

Instead of collecting digits into a string and converting later, what if we built the number as we scanned each digit? Think of how you naturally read a multi-digit number: when you see '4' followed by '2', you do not memorize the characters '4' and '2' separately — your brain immediately computes 4, then updates to 42 (4 × 10 + 2).

This one-pass approach eliminates the intermediate digit string entirely. At each digit character, we multiply the running result by 10 and add the new digit value. No extra string is ever created.

The critical challenge is overflow detection. Since we work with a standard 32-bit integer directly, we must detect whether the next multiplication-and-addition would push us past the boundary — before it happens. The check is elegant:

  • If result > INT_MAX / 10, then result * 10 would already overflow.
  • If result == INT_MAX / 10 and the new digit exceeds INT_MAX % 10 (which is 7), the addition would overflow.

In either case, we immediately return the clamped boundary value (INT_MAX for positive, INT_MIN for negative) without ever performing the overflowing operation. This guarantees correctness without needing 64-bit types or big integers.

Step-by-Step Explanation

Let's trace through with s = " -042":

Step 1: i=0, s[0] = ' ' (space). This is leading whitespace — skip it. Advance i to 1. result = 0.

Step 2: i=1, s[1] = '-'. This is a sign character. Set sign = -1. Advance i to 2.

Step 3: i=2, s[2] = '0' (digit 0). Overflow check: Is result (0) > INT_MAX/10 (214748364)? No. Safe to proceed. result = 0 × 10 + 0 = 0.

Step 4: i=3, s[3] = '4' (digit 4). Overflow check: Is result (0) > 214748364? No. result = 0 × 10 + 4 = 4.

Step 5: i=4, s[4] = '2' (digit 2). Overflow check: Is result (4) > 214748364? No. result = 4 × 10 + 2 = 42.

Step 6: End of string. Apply sign: 42 × (-1) = -42. The number was built incrementally without any intermediate string. Return -42.

Single-Pass Parsing with Inline Overflow Detection — Watch how the integer is built digit by digit in a single pass. At each digit, an overflow check runs BEFORE the multiplication, ensuring we never exceed the 32-bit boundary.

Algorithm

  1. Initialize index i = 0, result = 0, sign = 1
  2. Skip whitespace: While s[i] is a space, increment i
  3. Read sign: If s[i] is '+' or '-', set sign accordingly and increment i
  4. Parse digits with overflow detection: While s[i] is a digit:
    a. Compute digit = s[i] - '0'
    b. Overflow check: If result > INT_MAX / 10, or result == INT_MAX / 10 and digit > 7, return INT_MAX (if positive) or INT_MIN (if negative)
    c. Update result = result × 10 + digit
    d. Increment i
  5. Return result × sign

Code

#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, n = s.size();
        
        // Skip leading whitespace
        while (i < n && s[i] == ' ') i++;
        
        // Determine sign
        int sign = 1;
        if (i < n && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }
        
        // Parse digits with inline overflow detection
        int result = 0;
        while (i < n && isdigit(s[i])) {
            int digit = s[i] - '0';
            
            // Check for overflow BEFORE updating result
            if (result > INT_MAX / 10 ||
                (result == INT_MAX / 10 && digit > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            
            result = result * 10 + digit;
            i++;
        }
        
        return result * sign;
    }
};
class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        i, n = 0, len(s)
        
        # Skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1
        
        # Determine sign
        sign = 1
        if i < n and s[i] in ('+', '-'):
            sign = -1 if s[i] == '-' else 1
            i += 1
        
        # Parse digits with inline overflow detection
        result = 0
        while i < n and s[i].isdigit():
            digit = int(s[i])
            
            # Check for overflow before updating
            if (result > INT_MAX // 10 or
                    (result == INT_MAX // 10 and digit > INT_MAX % 10)):
                return INT_MAX if sign == 1 else INT_MIN
            
            result = result * 10 + digit
            i += 1
        
        return result * sign
class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        
        // Skip leading whitespace
        while (i < n && s.charAt(i) == ' ') i++;
        
        // Determine sign
        int sign = 1;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }
        
        // Parse digits with inline overflow detection
        int result = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            
            // Check overflow BEFORE updating
            if (result > Integer.MAX_VALUE / 10 ||
                (result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
            i++;
        }
        
        return result * sign;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the string exactly once from left to right. Each character is examined at most once — whitespace characters are skipped in a loop, the sign character is read in O(1), and each digit character triggers a constant-time overflow check and arithmetic update. The total number of operations is proportional to the string length n.

Space Complexity: O(1)

We use only a fixed number of integer variables (result, sign, i, digit) regardless of the input length. No intermediate strings, arrays, or other data structures are created. This is a genuine improvement over the brute force, which needed O(n) space for the digit string.

String to Integer (atoi) | CodePeet