Coding Interview Questions | String to Integer

January 31st, 2024

String to Integer Problem Introduction:

This summary will talk about my solution to the string to integer problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer
(similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace.

Check if the next character (if not already at the end of the string) is '-' or '+'.
Read this character in if it is either. This determines if the final result is negative or positive respectively.
Assume the result is positive if neither is present.

Read the next characters in until the next non-digit character or the end of the input is reached.
The rest of the string is ignored.

Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read,
then the integer is 0. Change the sign as necessary (from step 2).

If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer
so that it remains in the range. Specifically, integers less than -231 should be clamped to -231,
and integers greater than 231 - 1 should be clamped to 231 - 1.

Return the integer as the final result.

How do you solve the String to Integer Problem in O(n) time complexity?

Solution:

function myAtoi(s: string): number {
  let foundNum = false;
  let output = "";
  let sign = 1;

  for (const char of s) {
    // Remove whitespace
    if (char === " " && !foundNum) {
      continue;
    }

    // Handle signs
    if (!foundNum && (char === "-" || char === "+")) {
      sign = char === "-" ? -1 : 1;
      foundNum = true;
      continue;
    }

    // Handle digits
    const digit = parseInt(char, 10);
    if (isNaN(digit)) {
      break; // Stop at the first non-digit character
    }

    foundNum = true;
    output += digit;
  }

  if (output === "") {
    return 0;
  }

  const result = sign * parseInt(output);

  // Overflow handling
  if (result < -1 * 2 ** 31) {
    return -1 * 2 ** 31;
  } else if (result > 2 ** 31 - 1) {
    return 2 ** 31 - 1;
  }

  return result;
}

String to Integer Solution Summary:

Below is a breakdown of the key aspects of the solution for the string to integer problem as described above:

1. Whitespace Handling: The algorithm iterates through the input string, ignoring leading whitespace until the first non-whitespace character is encountered.

2. Sign Detection: It checks for a sign (+ or -) after the leading whitespace, determining the sign of the final result. If no sign is present, it assumes a positive result.

3. Digit Parsing: The algorithm reads digits until the first non-digit character or the end of the input, converting these digits into an integer. It breaks the loop at the first non-digit character.

4. Result Calculation: The algorithm calculates the final result by considering the sign and converting the accumulated digits into an integer.

5. Overflow Handling: It ensures the result is within the 32-bit signed integer range [-2^31, 2^31 - 1]. If the result exceeds this range, it clamps the result to the closest boundary.

Complexities:

1. Time Complexity: The time complexity is O(n), where n is the length of the input string. The algorithm iterates through the string once.

2. Space Complexity: The space complexity is O(1). The algorithm uses a constant amount of space for variables, and the output string does not scale with the input.