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

Time Complexity: String to Integer atoi

O(n)

Understanding Time Complexity

We want to understand how the time needed 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.

function myAtoi(s) {
  let i = 0, sign = 1, result = 0;
  while (s[i] === ' ') i++;
  if (s[i] === '+' || s[i] === '-') {
    sign = s[i] === '-' ? -1 : 1;
    i++;
  }
  while (i < s.length && s[i] >= '0' && s[i] <= '9') {
    result = result * 10 + (s.charCodeAt(i) - 48);
    i++;
  }
  return sign * result;
}
    

This code converts a string to an integer by skipping spaces, checking the sign, and reading digits until a non-digit is found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two while loops that scan characters in the string.
• How many times: Each loop runs at most once over parts of the string, together scanning each character at most once.

How Execution Grows With Input

As the string length grows, the code checks each character once or twice in sequence.

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

Pattern observation: The number of steps grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

[OK] Correct: Each character is checked at most once or twice in sequence, so the total work still grows linearly, not more.

Interview Connect

Understanding this linear time complexity helps you explain how your code handles input efficiently, a key skill in interviews.

Self-Check

"What if the input string contains many non-digit characters after digits? How would the time complexity change?"

Practice

1. What is the main purpose of the atoi function in programming?

easy

A. Check if a string contains only digits

B. Convert an integer into a string

C. Sort characters in a string alphabetically

D. Convert a string representing a number into an integer

Solution

1. Step 1: Understand the function name

   atoi stands for ASCII to integer, meaning it converts strings to integers.

2. Step 2: Identify the function's purpose

   It takes a string input and returns its integer value if possible.

3. Final Answer:

   Convert a string representing a number into an integer -> Option D

4. Quick Check:

   atoi = string to integer conversion [OK]

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

Common Mistakes:

• Confusing atoi with integer to string conversion
• Thinking atoi sorts strings
• Assuming atoi validates string digits only

2. Which of the following JavaScript code snippets correctly converts the string "123" to an integer using a method similar to atoi?

easy

A. const num = Number.toString("123");

B. const num = parseInt("123");

C. const num = "123".toString();

D. const num = "123" + 0;

Solution

1. Step 1: Identify the correct conversion method

   parseInt converts a string to an integer in JavaScript, similar to atoi.

2. Step 2: Check each option

   const num = parseInt("123"); uses parseInt correctly. const num = "123".toString(); converts string to string, no change. const num = Number.toString("123"); is invalid syntax. const num = "123" + 0; concatenates string and number, resulting in a string.

3. Final Answer:

   const num = parseInt("123"); -> Option B

4. Quick Check:

   parseInt("123") = 123 [OK]

Hint: Use parseInt() to convert string to integer [OK]

Common Mistakes:

• Using toString() which returns a string
• Trying Number.toString() incorrectly
• Adding 0 to string results in string concatenation

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

function myAtoi(str) {
  let i = 0, sign = 1, result = 0;
  while (str[i] === ' ') i++;
  if (str[i] === '-' || str[i] === '+') {
    sign = str[i] === '-' ? -1 : 1;
    i++;
  }
  while (i < str.length && str[i] >= '0' && str[i] <= '9') {
    result = result * 10 + (str[i].charCodeAt(0) - '0'.charCodeAt(0));
    i++;
  }
  return sign * result;
}
console.log(myAtoi("  -42abc"));

medium

A. 0

B. 42

C. -42

D. NaN

Solution

1. Step 1: Skip leading spaces and check sign

   The function skips spaces, finds '-', sets sign to -1, moves index forward.

2. Step 2: Convert digits until non-digit

   Reads '4' and '2', converts to number 42, stops at 'a'.

3. Step 3: Apply sign and return

   Returns -1 * 42 = -42.

4. Final Answer:

   -42 -> Option C

5. Quick Check:

   myAtoi(" -42abc") = -42 [OK]

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

Common Mistakes:

• Not skipping spaces before sign
• Ignoring sign and returning positive number
• Parsing non-digit characters

4. Identify the bug in this myAtoi function implementation:

function myAtoi(str) {
  let i = 0, sign = 1, result = 0;
  while (str[i] === ' ') i++;
  if (str[i] === '-' || str[i] === '+') {
    sign = str[i] === '-' ? -1 : 1;
    i++;
  }
  while (i < str.length && str[i] >= '0' && str[i] <= '9') {
    result = result * 10 + (str[i] - '0');
    i++;
  }
  return sign * result;
}

medium

A. Subtracting characters directly without charCodeAt causes NaN

B. Missing check for empty string input

C. Sign is not applied correctly

D. Loop does not skip spaces

Solution

1. Step 1: Analyze digit conversion

   Expression str[i] - '0' tries to subtract strings, which results in NaN in JavaScript.

2. Step 2: Correct approach

   Use str[i].charCodeAt(0) - '0'.charCodeAt(0) to get numeric value of digit character.

3. Final Answer:

   Subtracting characters directly without charCodeAt causes NaN -> Option A

4. Quick Check:

   String subtraction needs charCodeAt() [OK]

Hint: Use charCodeAt() to convert char digits to numbers [OK]

Common Mistakes:

• Subtracting characters directly causing NaN
• Not handling empty or invalid input
• Ignoring sign application

5. You want to implement myAtoi that converts a string to a 32-bit signed integer. Which approach correctly handles overflow and returns the clamped value if the number is out of range?

function myAtoi(str) {
  let i = 0, sign = 1, result = 0;
  const INT_MAX = 2147483647;
  const INT_MIN = -2147483648;
  while (str[i] === ' ') i++;
  if (str[i] === '-' || str[i] === '+') {
    sign = str[i] === '-' ? -1 : 1;
    i++;
  }
  while (i < str.length && str[i] >= '0' && str[i] <= '9') {
    let digit = str[i].charCodeAt(0) - '0'.charCodeAt(0);
    if (result > Math.floor(INT_MAX / 10) || (result === Math.floor(INT_MAX / 10) && digit > INT_MAX % 10)) {
      return sign === 1 ? INT_MAX : INT_MIN;
    }
    result = result * 10 + digit;
    i++;
  }
  return sign * result;
}

hard

A. Correctly clamps overflow and returns 32-bit integer limits

B. Does not handle overflow, may return incorrect large numbers

C. Returns NaN on overflow instead of clamping

D. Ignores sign when clamping overflow values

Solution

1. Step 1: Check overflow condition

   The code checks if adding the next digit causes overflow by comparing with INT_MAX/10 and last digit.

2. Step 2: Return clamped value

   If overflow detected, returns INT_MAX or INT_MIN depending on sign, correctly clamping the value.

3. Step 3: Otherwise accumulate result

   Accumulates digits safely within 32-bit integer range.

4. Final Answer:

   Correctly clamps overflow and returns 32-bit integer limits -> Option A

5. Quick Check:

   Overflow check and clamp = correct behavior [OK]

Hint: Check overflow before multiply, clamp to INT_MAX/INT_MIN [OK]

Common Mistakes:

• Not checking overflow before multiplication
• Returning wrong values on overflow
• Ignoring sign when clamping