String to Integer atoi in DSA C# - Time & Space Complexity

Time Complexity: String to Integer atoi

O(n)

Understanding Time Complexity

We want to know 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, sign = 1, result = 0;
    while (i < s.Length && s[i] == ' ') i++;
    if (i < s.Length && (s[i] == '+' || s[i] == '-')) {
        sign = (s[i] == '-') ? -1 : 1;
        i++;
    }
    while (i < s.Length && char.IsDigit(s[i])) {
        int digit = s[i] - '0';
        result = result * 10 + digit;
        i++;
    }
    return sign * result;
}
    

This code converts a string to an integer by skipping spaces, checking sign, and reading digits one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through characters of the string to skip spaces and then to read digits.
• How many times: Each character is visited at most once in sequence.

How Execution Grows With Input

As the string length grows, the number of characters to check grows linearly.

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

Pattern observation: The steps grow directly in proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "The function checks every character multiple times, so it is slower than linear."

[OK] Correct: Each character is checked only once in order, so the time grows linearly, not more.

Interview Connect

Understanding this linear time complexity helps you explain how your code handles input efficiently and prepares you for similar string parsing problems.

Self-Check

"What if we added a nested loop to check each digit against all previous digits? How would the time complexity change?"

Practice

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

easy

A. Reverses the string characters

B. Converts the string to a floating-point number

C. Converts the string to an integer number

D. Counts the number of characters in the string

Solution

1. Step 1: Understand the purpose of atoi

   The atoi function is designed to convert a string that represents a number into an integer type.

2. Step 2: Differentiate from other string operations

   It does not reverse or count characters, nor convert to floating-point; it specifically converts to integer.

3. Final Answer:

   Converts the string to an integer number -> Option C

4. Quick Check:

   atoi converts string to integer [OK]

Hint: atoi always converts string digits to integer number [OK]

Common Mistakes:

• Thinking atoi converts to float
• Confusing atoi with string reversal
• Assuming atoi counts characters

2. Which of the following C# code snippets correctly converts a string "1234" to an integer using atoi logic?

easy

A. int num = Convert.ToString(1234);

B. int num = "1234".ToInt();

C. int num = int.ToString("1234");

D. int num = int.Parse("1234");

Solution

1. Step 1: Identify correct C# method for string to int

   int.Parse(string) converts a numeric string to an integer correctly.

2. Step 2: Check other options for syntax errors

   "1234".ToInt() and int.ToString("1234") are invalid methods; Convert.ToString(1234) converts int to string, not string to int.

3. Final Answer:

   int num = int.Parse("1234"); -> Option D

4. Quick Check:

   int.Parse converts string to int [OK]

Hint: Use int.Parse to convert string digits to int in C# [OK]

Common Mistakes:

• Using invalid method names like ToInt()
• Confusing Convert.ToString with conversion to int
• Trying to call ToString on string input

3. What is the output of the following C# code?

string s = "  -42abc";
int result = MyAtoi(s);
Console.WriteLine(result);

int MyAtoi(string str) {
    int i = 0, sign = 1, num = 0;
    while (i < str.Length && str[i] == ' ') i++;
    if (i < str.Length && (str[i] == '+' || str[i] == '-')) {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }
    while (i < str.Length && char.IsDigit(str[i])) {
        num = num * 10 + (str[i] - '0');
        i++;
    }
    return sign * num;
}

medium

A. Exception thrown

B. -42

C. 42

D. 0

Solution

1. Step 1: Skip leading spaces and detect sign

   The code skips spaces, finds '-', sets sign to -1, then moves to digits.

2. Step 2: Parse digits until non-digit

   It reads '4' and '2', stops at 'a', so number is 42, multiplied by sign -1 gives -42.

3. Final Answer:

   -42 -> Option B

4. Quick Check:

   Parsed number with sign = -42 [OK]

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

Common Mistakes:

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

4. Identify the bug in this MyAtoi function and select the fix:

int MyAtoi(string str) {
    int i = 0, sign = 1, num = 0;
    while (str[i] == ' ') i++;
    if (str[i] == '+' || str[i] == '-') {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }
    while (char.IsDigit(str[i])) {
        num = num * 10 + (str[i] - '0');
        i++;
    }
    return sign * num;
}

medium

A. Add boundary checks for index i before accessing str[i]

B. Remove the sign check to simplify code

C. Change char.IsDigit to char.IsLetter

D. Initialize num to -1 instead of 0

Solution

1. Step 1: Check for index out of range errors

   The code accesses str[i] without checking if i < str.Length, risking runtime error.

2. Step 2: Fix by adding boundary checks in all loops

   Adding conditions like i < str.Length in while loops prevents out-of-range exceptions.

3. Final Answer:

   Add boundary checks for index i before accessing str[i] -> Option A

4. Quick Check:

   Always check index bounds before accessing string [OK]

Hint: Always check string length before accessing characters [OK]

Common Mistakes:

• Ignoring string length checks causing exceptions
• Removing sign check breaks negative numbers
• Using char.IsLetter instead of char.IsDigit

5. Given the input string "+-12", what should a robust atoi implementation return according to standard rules?

hard

A. 0

B. -12

C. 12

D. Exception thrown

Solution

1. Step 1: Analyze sign characters in input

   The string starts with '+' followed immediately by '-', which is invalid for atoi parsing.

2. Step 2: According to atoi rules, invalid sign sequence returns 0

   Parsing stops at invalid sequence, so result is 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Invalid sign sequence returns 0 [OK]

Hint: Invalid sign sequences return 0 in atoi [OK]

Common Mistakes:

• Parsing multiple signs as valid
• Returning partial number ignoring invalid signs
• Throwing exceptions instead of returning 0