String to Integer atoi in DSA Typescript - 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.

Specifically, 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: string): number {
  let 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 && 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 for a sign, and then 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 through parts of the string.
• How many times: Each loop runs at most once over the string characters, together covering the string length.

How Execution Grows With Input

As the input string gets longer, the code checks each character once or twice in sequence.

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

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 grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "The function runs in constant time because it stops once digits end."

[OK] Correct: The function may need to scan many characters before digits start or after, so in the worst case it checks every character.

Interview Connect

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

Self-Check

"What if we changed the code to parse the string backwards? How would the time complexity change?"

Practice

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

easy

A. Converts the string to a floating-point number

B. Reverses the string characters

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 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 correctly describes this conversion. Other options describe different operations unrelated to atoi.

3. Final Answer:

   Converts the string to an integer number -> Option C

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 reversal
• Assuming atoi counts characters

2. Which of the following TypeScript function signatures correctly represents a simple atoi function?

easy

A. function atoi(str: string): number

B. function atoi(num: number): string

C. function atoi(str: number): string

D. function atoi(): void

Solution

1. Step 1: Identify input and output types for atoi

   atoi takes a string input and returns a number (integer).

2. Step 2: Match function signature with correct types

   function atoi(str: string): number matches this: input is string, output is number. Other options have wrong input/output types or no parameters.

3. Final Answer:

   function atoi(str: string): number -> Option A

4. Quick Check:

   Input string, output number [OK]

Hint: atoi input is string, output is number [OK]

Common Mistakes:

• Swapping input and output types
• Using no parameters
• Using wrong parameter types

3. What is the output of the following TypeScript code?

function atoi(str: string): number {
  let i = 0, num = 0, sign = 1;
  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') {
    num = num * 10 + (str.charCodeAt(i) - 48);
    i++;
  }
  return num * sign;
}
console.log(atoi("  -42abc"));

medium

A. -42

B. 42

C. 0

D. NaN

Solution

1. Step 1: Skip leading spaces and detect sign

   The code skips spaces, finds '-', so sign = -1, index moves past '-'.

2. Step 2: Parse digits until non-digit

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

3. Step 3: Apply sign and return

   Returns 42 * -1 = -42.

4. Final Answer:

   -42 -> Option A

5. Quick Check:

   Parsed number with sign = -42 [OK]

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

Common Mistakes:

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

4. The following TypeScript atoi implementation has a bug. What is the bug?

function atoi(str: string): number {
  let num = 0;
  let i = 0;
  while (i < str.length && str[i] === ' ') i++;
  for (; i < str.length; i++) {
    if (str[i] < '0' || str[i] > '9') break;
    num = num * 10 + (str.charCodeAt(i) - 48);
  }
  return num;
}

medium

A. Returns string instead of number

B. Does not handle leading spaces

C. Does not stop parsing at non-digit characters

D. Does not handle negative or positive signs

Solution

1. Step 1: Check for sign handling

   The code does not check for '+' or '-' signs before parsing digits.

2. Step 2: Verify other behaviors

   It skips leading spaces, stops parsing at first non-digit and returns number, so no issue there. The main bug is missing sign handling.

3. Final Answer:

   Does not handle negative or positive signs -> Option D

4. Quick Check:

   Missing sign handling in atoi [OK]

Hint: Check if signs '+' or '-' are handled [OK]

Common Mistakes:

• Assuming spaces are main bug
• Thinking it parses non-digit characters
• Confusing return type

5. You want to extend the atoi function to handle integer overflow by clamping the result between INT_MIN = -2147483648 and INT_MAX = 2147483647. Which code snippet correctly clamps the value before returning?

const INT_MIN = -2147483648;
const INT_MAX = 2147483647;

function atoi(str: string): number {
  let i = 0, num = 0, sign = 1;
  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') {
    num = num * 10 + (str.charCodeAt(i) - 48);
    i++;
  }
  num = num * sign;
  // Clamp here
  // ???
  return num;
}

hard

A. if (num > INT_MIN) return INT_MIN; if (num < INT_MAX) return INT_MAX;

B. if (num < INT_MIN) return INT_MIN; if (num > INT_MAX) return INT_MAX;

C. if (num < INT_MAX) return INT_MIN; if (num > INT_MIN) return INT_MAX;

D. if (num === INT_MIN) return INT_MAX; if (num === INT_MAX) return INT_MIN;

Solution

1. Step 1: Understand clamping logic

   If number is less than INT_MIN, return INT_MIN; if greater than INT_MAX, return INT_MAX.

2. Step 2: Match correct condition and return

   if (num < INT_MIN) return INT_MIN; if (num > INT_MAX) return INT_MAX; correctly checks and returns clamped values. Other options have incorrect comparisons or swap min/max.

3. Final Answer:

   if (num < INT_MIN) return INT_MIN; if (num > INT_MAX) return INT_MAX; -> Option B

4. Quick Check:

   Clamp below min and above max correctly [OK]

Hint: Clamp with if less than min or greater than max [OK]

Common Mistakes:

• Swapping INT_MIN and INT_MAX in conditions
• Using equality instead of inequality
• Returning wrong clamp value