Implement Atoi (String to Integer Conversion)

Problem Statement❯

You are given a string that may contain a number. Your task is to convert this string into a valid integer, just like the C/C++ function atoi() does.

However, the conversion should follow these rules:

Ignore leading whitespaces.
The first non-whitespace character may be '+' or '-' to indicate sign.
Only read the digits after the optional sign.
If any non-digit character appears after the digits, stop reading further.
If the converted number exceeds the 32-bit signed integer range ([-2³¹, 2³¹-1]), clamp it to the nearest bound.

If the string does not contain a valid number, return 0.

Examples❯

Input String	Output	Description
"42"	42	Normal case with valid positive number
" -42"	-42	Leading spaces and negative sign handled
"4193 with words"	4193	Number ends before non-digit characters
"words and 987"	0	Invalid as it doesn't start with a number
"+123"	123	Valid positive number with explicit sign
"-91283472332"	-2147483648	Below 32-bit signed int range, clamped to INT_MIN
"91283472332"	2147483647	Above 32-bit signed int range, clamped to INT_MAX
""	0	Empty string returns 0
" "	0	Whitespace only returns 0
"-"	0	Only sign with no digits returns 0
"+0 123"	0	Only 0 is read before space, rest ignored

Solution❯

Understanding the Problem

We are given a string, and our goal is to convert it into an integer — similar to the C-style atoi function. However, this isn’t as simple as it sounds. The string might have:

Leading whitespaces
Optional '+' or '-' signs
Digits that form the number
Trailing or interleaved invalid characters
Very large or very small values that cause overflow

We must carefully extract a valid integer from the string, character by character, while following strict rules. If the string doesn't begin with a valid number after skipping whitespace, we must return 0.

Step-by-Step Solution with Example

step 1: Skip leading whitespaces

We start scanning from the beginning of the string and ignore all spaces. These don’t affect the number.

Example: For input " -42", we skip the three spaces and move to '-'.

step 2: Handle optional '+' or '-' sign

After whitespace, the first character might be a '+' or '-'. This sets the sign of the final result.

Example: In " -42", we detect '-', so the number will be negative.

step 3: Convert consecutive digits into a number

Now we read digits (0 to 9) one by one. For each digit, we multiply the current number by 10 and add the digit.

Example: From "-42", we convert '4' and '2' into the number 42. Since the sign was '-', the final result becomes -42.

step 4: Stop at the first non-digit character

If we encounter a non-digit (like a letter or symbol), we stop parsing there. We only consider the valid numeric prefix.

Example: In "4193 with words", we stop reading at the space before "with" → result is 4193.

step 5: Clamp the value to fit within 32-bit signed integer range

The valid range is from -2147483648 to 2147483647. If the number exceeds this, we must cap it to the closest boundary.

Example: For "91283472332", the value exceeds 2147483647, so we return 2147483647.

step 6: Return 0 if nothing can be converted

If there's no valid digit after trimming spaces and signs, we simply return 0.

Example: For " " or "words and 987", no conversion is possible → result is 0.

Edge Cases

Empty string: "" → nothing to parse → return 0.
Only spaces: " " → becomes empty after trim → return 0.
Starts with letters: "abc123" → no digits at start → return 0.
Only sign: "+" or "-" with no digits → return 0.
Overflow: "9999999999" → exceeds max → return 2147483647.
Underflow: "-9999999999" → exceeds min → return -2147483648.

Finally

This problem teaches us how to break a real-world task into safe, logical steps. By handling each character carefully and accounting for edge cases like signs, invalid input, and overflow, we make our solution reliable and beginner-friendly. Always remember: start small, handle edge cases, and test with multiple scenarios.

Algorithm Steps❯

Trim leading whitespaces from the input string
Check if the next character is '+' or '-'. Store the sign
Iterate through each character:
→ If it's a digit, convert and add to result
→ If not a digit, break the loop
→ Before each step, check if result will overflow/underflow
Return result multiplied by sign

Code

C++

Python

Java

Rust

Kotlin

#include <stdio.h>
#include <limits.h>
#include <ctype.h>

int myAtoi(const char* s) {
    while (isspace(*s)) s++;

    int sign = 1;
    int result = 0;

    if (*s == '+' || *s == '-') {
        sign = (*s == '-') ? -1 : 1;
        s++;
    }

    while (isdigit(*s)) {
        int digit = *s - '0';
        if (result > (INT_MAX - digit) / 10)
            return (sign == 1) ? INT_MAX : INT_MIN;
        result = result * 10 + digit;
        s++;
    }

    return result * sign;
}

int main() {
    const char* input = "   -42";
    printf("Converted Integer: %d\n", myAtoi(input));
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	When the string is empty or contains only whitespaces, the function exits early.
Average Case	O(n)	Where n is the number of characters to parse through until a non-digit or end is encountered.
Worst Case	O(n)	Involves scanning through the entire valid digit portion of the string for parsing.

Space Complexity❯

O(1)

Explanation: Only a fixed number of variables are used for computation, regardless of input size.

⬅ Previous TopicConvert Integer to Roman Numeral - Step-by-Step for Beginners

Next Topic ⮕Count Number of Substrings in a String - Explanation with Formula

Comments

Loading comments...