Implement Atoi (String to Integer Conversion)

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❯

To convert a string into an integer (like the atoi function), we need to carefully interpret the string one character at a time. It's not just about parsing digits — we must also think about signs, spaces, invalid characters, and potential overflows.

Let’s break it down for a beginner:

1. Ignore leading whitespaces: The first thing we do is skip any space characters at the beginning of the string. These should not affect the result.

2. Check for optional '+' or '-' sign: After trimming spaces, if the first character is '+' or '-', we store this to determine the final sign of our number.

3. Convert following digits: Next, we move character by character and as long as we see digits (0-9), we build the number by multiplying the existing result by 10 and adding the new digit.

4. Stop on invalid character: If we hit a character that's not a digit (e.g., letter, punctuation, space), we stop immediately. Only the valid prefix of the string is considered.

5️⃣ Handle overflow: While building the number, if at any point it goes beyond the limits of a 32-bit signed integer, we stop and clamp the result to:

  • 2147483647 if the number is too large (positive overflow)
  • -2147483648 if the number is too small (negative overflow)

6️⃣ Empty or invalid string: If after removing spaces and optional sign we find nothing to convert, or the string starts with something invalid, we simply return 0.

Example thoughts:

  • "42" → clean numeric string, converts to 42.
  • " -42" → spaces skipped, '-' sign handled, digits converted → -42.
  • "words and 987" → starts with non-digit → invalid → return 0.
  • "91283472332" → valid number but too large → clamp to 2147483647.
  • "" or " " → empty after trimming → return 0.

This approach ensures correctness and protects against errors, making it suitable for real-world use cases like parsing user input.

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

Java
Python
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
public class AtoiConverter {
    public static int myAtoi(String s) {
        if (s == null || s.isEmpty()) return 0;
        s = s.trim(); // remove leading/trailing spaces
        if (s.isEmpty()) return 0;

        int sign = 1, i = 0, result = 0;
        int INT_MAX = Integer.MAX_VALUE;
        int INT_MIN = Integer.MIN_VALUE;

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

        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';

            if (result > (INT_MAX - digit) / 10) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }

            result = result * 10 + digit;
            i++;
        }

        return result * sign;
    }

    public static void main(String[] args) {
        String input = "   -42";
        System.out.println("Converted Integer: " + myAtoi(input));
    }
}

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.