Jaspreet singh

Posted on Jun 30

String to Integer (atoi)

#algorithms #coding #computerscience #interview

leetcode.com

Problem Statement

Implement the atoi() function that converts a string to a 32-bit signed integer.

Rules:

Ignore leading whitespaces.
Handle optional + or - sign.
Read digits until a non-digit character appears.
Clamp the result within:

[-2³¹, 2³¹ - 1]

Brute Force Intuition

In an interview, you can explain it like this:

Remove leading spaces, determine the sign, extract the numeric characters into another string, and finally convert that string into an integer.

This works but requires creating extra strings and doesn't efficiently handle overflow.

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Brute Force Code

// Trim spaces
// Store digits into StringBuilder
// Convert using Integer.parseInt()
// Handle exceptions for overflow

Moving Towards the Optimal Approach

Instead of creating another string,

process each character directly.

Maintain:

Current Number

+

Current Sign

Build the answer digit by digit.

Pattern Recognition

Whenever you see:

Parse String
Convert Characters to Number
Overflow Handling

Think:

Linear String Traversal

Key Observation

For every digit:

Current number becomes:

number = number * 10 + digit;

Before updating,

check whether adding this digit would overflow.

Optimal Approach

Step 1

Skip leading spaces.

Step 2

Determine sign.

+

or

-

Step 3

Process every digit.

Update:

number = number * 10 + digit;

Before updating,

check overflow.

Step 4

Return:

sign × number

Optimal Java Solution

class Solution {

    public int myAtoi(String s) {

        int i = 0;
        int n = s.length();

        while (i < n && s.charAt(i) == ' ')
            i++;

        int sign = 1;

        if (i < n &&
           (s.charAt(i) == '+' ||
            s.charAt(i) == '-')) {

            if (s.charAt(i) == '-')
                sign = -1;

            i++;
        }

        int number = 0;

        while (i < n &&
               Character.isDigit(s.charAt(i))) {

            int digit = s.charAt(i) - '0';

            if (number >
                (Integer.MAX_VALUE - digit) / 10) {

                return sign == 1
                        ? Integer.MAX_VALUE
                        : Integer.MIN_VALUE;
            }

            number = number * 10 + digit;

            i++;
        }

        return sign * number;
    }
}

Dry Run

Input

"   -42abc"

Skip spaces.

Sign:

Read digits:

Encounter:

Stop.

Answer:

-42

Why This Works?

The number is built one digit at a time.

Overflow is checked before multiplication,

ensuring we never exceed the 32-bit integer range.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(1)

Interview One-Liner

Skip spaces, determine the sign, process digits one by one, and check for overflow before updating the current number.

Pattern Learned

String Parsing

↓

Character Traversal

↓

Overflow Check

Memory Trick