String to Integer atoi in DSA Java - Time & Space Complexity

Time Complexity: String to Integer atoi

O(n)

Understanding Time Complexity

We want to understand how the time to convert a string to an integer grows as the string gets longer.

How does the number of steps change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int myAtoi(String s) {
    int i = 0, n = s.length();
    while (i < n && s.charAt(i) == ' ') i++;
    int sign = 1;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        sign = (s.charAt(i) == '-') ? -1 : 1;
        i++;
    }
    int result = 0;
    while (i < n && Character.isDigit(s.charAt(i))) {
        int digit = s.charAt(i) - '0';
        result = result * 10 + digit;
        i++;
    }
    return sign * result;
}

This code converts a string to an integer by skipping spaces, handling sign, and reading digits until non-digit or end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through characters of the string once.
• How many times: Up to n times, where n is the string length.

How Execution Grows With Input

As the string length grows, the number of characters checked grows roughly the same.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The steps increase linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows in direct proportion to the string length.

Common Mistake

[X] Wrong: "The time is constant because we stop at the first non-digit."

[OK] Correct: Sometimes the digits can be many, so the loop can run through most of the string, making time grow with input size.

Interview Connect

Understanding this linear time behavior helps you explain how your code handles input efficiently and is a common skill interviewers look for.

Self-Check

"What if the input string was guaranteed to have only digits and no spaces or signs? How would the time complexity change?"

Practice

1. What does the atoi function do when given a string input?

easy

A. Counts the number of characters in the string

B. Converts the string to a floating-point number

C. Reverses the string characters

D. Converts the string to an integer number

Solution

1. Step 1: Understand the purpose of atoi

   The atoi function stands for ASCII to integer and converts a string representing a number into an integer value.

2. Step 2: Compare options with function behavior

   Only Converts the string to an integer number matches the behavior of converting string to integer. Other options describe different operations.

3. Final Answer:

   Converts the string to an integer number -> Option D

4. Quick Check:

   atoi converts string to integer [OK]

Hint: Remember atoi means ASCII to integer conversion [OK]

Common Mistakes:

• Thinking atoi converts to float
• Confusing atoi with string length functions
• Assuming it reverses the string

2. Which of the following Java code snippets correctly converts a string s to an integer using Integer.parseInt?

easy

A. int num = parseInt.Integer(s);

B. int num = Integer.parseInt(s);

C. int num = Integer.valueOf(s).toInt();

D. int num = Integer.toString(s);

Solution

1. Step 1: Identify correct method syntax

   Java's correct method to convert string to int is Integer.parseInt(string).

2. Step 2: Check each option

   int num = Integer.parseInt(s); uses correct syntax. int num = Integer.toString(s); tries to convert int to string incorrectly. int num = Integer.valueOf(s).toInt(); uses invalid method chaining. int num = parseInt.Integer(s); has wrong method call order.

3. Final Answer:

   int num = Integer.parseInt(s); -> Option B

4. Quick Check:

   Correct Java syntax is Integer.parseInt(s) [OK]

Hint: Use Integer.parseInt(string) to convert string to int [OK]

Common Mistakes:

• Using Integer.toString instead of parseInt
• Incorrect method chaining like valueOf().toInt()
• Wrong method call order

3. What will be the output of the following Java code?

String s = "  -42abc";
int result = 0;
int i = 0;
boolean negative = false;

// Skip leading spaces
while (i < s.length() && s.charAt(i) == ' ') i++;

// Check sign
if (i < s.length() && (s.charAt(i) == '-' || s.charAt(i) == '+')) {
    negative = s.charAt(i) == '-';
    i++;
}

// Convert digits
while (i < s.length() && Character.isDigit(s.charAt(i))) {
    result = result * 10 + (s.charAt(i) - '0');
    i++;
}

if (negative) result = -result;
System.out.println(result);

medium

A. -42

B. 42

C. 0

D. NumberFormatException

Solution

1. Step 1: Skip spaces and detect sign

   The code skips leading spaces, finds '-', sets negative true, and moves index forward.

2. Step 2: Parse digits until non-digit

   It reads '4' and '2', converts to integer 42, stops at 'a'. Then applies negative sign.

3. Final Answer:

   -42 -> Option A

4. Quick Check:

   Parsed number with sign is -42 [OK]

Hint: Skip spaces, check sign, parse digits until non-digit [OK]

Common Mistakes:

• Not skipping spaces before parsing
• Ignoring sign character
• Parsing non-digit characters causing errors

4. The following code attempts to convert a string to integer but throws an exception. What is the main error?

String s = "123abc";
int num = Integer.parseInt(s);
System.out.println(num);

medium

A. parseInt method does not exist in Integer class

B. Missing import for Integer class

C. String contains non-digit characters causing NumberFormatException

D. Variable num is not declared

Solution

1. Step 1: Understand Integer.parseInt behavior

   Integer.parseInt expects a string with only digits (and optional sign). Non-digit characters cause NumberFormatException.

2. Step 2: Analyze input string

   String "123abc" contains letters after digits, causing the exception.

3. Final Answer:

   String contains non-digit characters causing NumberFormatException -> Option C

4. Quick Check:

   Non-digit chars cause NumberFormatException [OK]

Hint: parseInt fails if string has letters or symbols [OK]

Common Mistakes:

• Assuming parseInt ignores trailing letters
• Forgetting to handle exceptions
• Thinking parseInt needs imports

5. You want to implement a custom atoi function in Java that handles leading spaces, optional '+' or '-' sign, digits, and stops parsing at the first non-digit character. Which approach below correctly handles integer overflow during conversion?

hard

A. Use a long variable to accumulate and check if it exceeds Integer.MAX_VALUE or Integer.MIN_VALUE before casting

B. Ignore overflow and cast directly to int after parsing all digits

C. Use Integer.parseInt inside a try-catch block to catch overflow exceptions

D. Stop parsing digits once the number of digits exceeds 10

Solution

1. Step 1: Understand overflow risk in atoi

   Parsing digits can exceed int limits, causing incorrect results or errors.

2. Step 2: Use long to detect overflow before casting

   Accumulating in a long lets you check if value goes beyond int range, then clamp or handle accordingly.

3. Step 3: Evaluate other options

   Ignore overflow and cast directly to int after parsing all digits ignores overflow, causing wrong results. Use Integer.parseInt inside a try-catch block to catch overflow exceptions is invalid because parseInt throws NumberFormatException, not overflow exception. Stop parsing digits once the number of digits exceeds 10 is unreliable as digit count alone doesn't guarantee overflow.

4. Final Answer:

   Use a long variable to accumulate and check if it exceeds Integer.MAX_VALUE or Integer.MIN_VALUE before casting -> Option A

5. Quick Check:

   Use long to detect overflow before int cast [OK]

Hint: Use long to detect overflow before converting to int [OK]

Common Mistakes:

• Ignoring overflow and casting directly
• Relying on digit count only
• Misusing try-catch for overflow