LeetCode 8: String to Integer (atoi) - Medium

Mastering LeetCode 8: String to Integer (atoi)

A Simple and Efficient Solution

LeetCode's String to Integer (atoi) is a classic medium-difficulty coding problem that challenges you to convert a string representation of a number into an actual integer. While it sounds straightforward, the problem comes with a few twists: you need to handle leading whitespace, account for positive or negative signs, and ensure the result stays within the 32-bit signed integer range.

In this post, I'll walk you through a highly efficient solution that achieves:

• 0ms runtime (beating 100% of submissions)
• 41.85MB of memory (better than 50% of submissions)

Understanding the Problem

The goal is to take a string, such as " -42", "4193 with words", or "+123", and convert it into an integer, like -42, 4193, or 123. Here are the key requirements

• Ignore leading whitespace: Skip any spaces at the start of the string.

• Handle signs: Recognise + or - to determine if the number is positive or negative.

• Stop at invalid characters: If you encounter a non-digit (other than the initial sign), stop processing.

• Respect 32-bit integer bounds: If the result exceeds the 32-bit signed integer range (-2^31 to 2^31 - 1), return the appropriate boundary value (-2^31 or 2^31 - 1).

• Default to 0: If the string is empty or contains no valid digits, return 0.

My Approach: Simple and Fast

I designed a solution that prioritises efficiency by working directly with the string's characters and using indexing to avoid unnecessary operations. Here's the step-by-step approach:

• Check for Empty Input: If the string is null or empty, return 0.

• Skip Whitespace: Loop through the string to bypass leading spaces, avoiding methods like .Trim() to reduce overhead.

• Handle the Sign: Assume the number is positive by default (sign = 1). If a + or - is found, update the sign variable and move to the next character.

• Build the Number: Process each digit character, converting it to its numeric value and building the result incrementally. Stop if a non-digit is encountered.

• Check Bounds: As the number is built, ensure it stays within the 32-bit integer limits, clamping to int.MaxValue or int.MinValue if necessary.

• Apply the Sign: Multiply the result by the sign to get the correct positive or negative value.

This approach is clean, avoids heavy string operations, and handles all edge cases efficiently.

The Code

class Solution
{
    public int MyAtoi(string s)
    {
        // Handle null or empty string
        if (string.IsNullOrEmpty(s)) return 0;

        int idx = 0, end = s.Length;

        // Skip leading whitespace
        while (idx < end && s[idx] == ' ') idx++;
        if (idx == end) return 0; // Return 0 if only whitespace

        // Check for sign
        int sign = 1; // Default to positive
        if (s[idx] == '+' || s[idx] == '-')
        {
            sign = (s[idx] == '-') ? -1 : 1; // Set sign based on + or -
            idx++;
        }

        int result = 0;
        // Process digits
        while (idx < end && char.IsDigit(s[idx]))
        {
            // Convert character to digit (e.g., '5' -> 5)
            int digit = s[idx] - '0';

            // Check for overflow before adding digit
            if (result > (int.MaxValue - digit) / 10)
            {
                return sign == 1 ? int.MaxValue : int.MinValue;
            }

            // Build number: multiply by 10 and add new digit
            result = result * 10 + digit;
            idx++;
        }

        // Apply sign to get final positive or negative result
        return result * sign;
    }
}

How It Works

Whitespace Handling: The while (idx < end && s[idx] == ' ') loop skips leading spaces. If the string contains only whitespace, we return 0.

Sign Detection: We default to sign = 1 (positive). If a + or - is found, we set sign to 1 or -1 and advance the index (so the index will be at the first character).

Number Building: For each digit, we convert the character to its numeric value (e.g., '5' - '0' = 5). We build the number by multiplying the current result by 10 and adding the new digit (e.g., for "123", we do 0*10 + 1 = 1, 1*10 + 2 = 12, 12*10 + 3 = 123).

Overflow Check: Before adding a digit, we check if result * 10 + digit would exceed int.MaxValue. If so, we return int.MaxValue or int.MinValue based on the sign.

Final Sign Application: Multiplying result by sign ensures the correct positive or negative output (e.g., 123 * -1 = -123).

Hope this has helped, as always give me a follow, or drop me a line on twitter/x