Implement Atoi (String to Integer Conversion) - Visualization

Strings

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

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 ([-231, 231-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❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#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❯

CaseTime ComplexityExplanation
Best CaseO(1)When the string is empty or contains only whitespaces, the function exits early.
Average CaseO(n)Where n is the number of characters to parse through until a non-digit or end is encountered.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...