Scale Engineer

String to Integer (atoi)

Med
#0008Time: O(n)Space: O(n)16 companies
Data structures
String
Companies
AdobeAmazonAppleBloomberg

Prompt

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

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

  1. Whitespace: Ignore any leading whitespace (" ").
  2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present.
  3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
  4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

 

Example 1:

Input: s = "42"

Output: 42

Explanation:

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^

Example 2:

Input: s = " -042"

Output: -42

Explanation:

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros ignored in the result)
               ^

Example 3:

Input: s = "1337c0d3"

Output: 1337

Explanation:

Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
         ^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
             ^

Example 4:

Input: s = "0-1"

Output: 0

Explanation:

Step 1: "0-1" (no characters read because there is no leading whitespace)
         ^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
          ^

Example 5:

Input: s = "words and 987"

Output: 0

Explanation:

Reading stops at the first non-digit character 'w'.

 

Constraints:

  • 0 <= s.length <= 200
  • s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses built-in string manipulation functions and the standard library's number parsing capabilities to simplify the implementation. It first cleans the input string by trimming whitespace, then identifies the sign and the numeric part. It uses Long.parseLong to convert the numeric string, which simplifies overflow detection, and then clamps the result to the 32-bit integer range. While functionally correct, this method is less efficient in terms of space compared to a single-pass approach.

Algorithm

  1. Use the trim() method to remove leading and trailing whitespace from the input string s. This may create a new string.
  2. If the trimmed string is empty, return 0.
  3. Initialize sign = 1 and startIndex = 0 to parse the number.
  4. Check the first character of the trimmed string. If it's '-', set sign = -1 and startIndex = 1. If it's '+', set startIndex = 1.
  5. Find the end of the continuous block of digits starting from startIndex. Let this be endIndex.
  6. Extract the numeric part of the string using substring(startIndex, endIndex).
  7. If the numeric string is empty (e.g., input was "+" or "-"), return 0.
  8. Use a try-catch block to parse the numeric string into a long using Long.parseLong(). Using long helps to detect overflows beyond the int range easily.
  9. If NumberFormatException is caught, it means the number is too large even for a long, so it must be clamped. Return Integer.MAX_VALUE or Integer.MIN_VALUE based on the sign.
  10. Multiply the parsed long value by sign.
  11. Clamp the result to the 32-bit signed integer range. If it's greater than Integer.MAX_VALUE, return Integer.MAX_VALUE. If it's less than Integer.MIN_VALUE, return Integer.MIN_VALUE.
  12. Cast the clamped long to int and return.

Walkthrough

The core idea is to break down the problem into distinct string processing steps. First, we handle the whitespace by calling s.trim(). Then, we manually inspect the first one or two characters to determine the sign of the number. After identifying the sign, we locate the substring that contains only the numerical digits. This substring is then passed to Long.parseLong(). We use long as an intermediate type because its range is much larger than int, making it easy to see if the number read from the string exceeds the int limits. After parsing, we apply the sign and then check if the resulting long value falls outside the [Integer.MIN_VALUE, Integer.MAX_VALUE] range. If it does, we return the appropriate clamped value; otherwise, we cast the long to an int and return it.

class Solution {    public int myAtoi(String s) {        s = s.trim();        if (s.isEmpty()) {            return 0;        }         int sign = 1;        int startIndex = 0;        if (s.charAt(0) == '-') {            sign = -1;            startIndex = 1;        } else if (s.charAt(0) == '+') {            startIndex = 1;        }         int endIndex = startIndex;        while (endIndex < s.length() && Character.isDigit(s.charAt(endIndex))) {            endIndex++;        }         String numStr = s.substring(startIndex, endIndex);        if (numStr.isEmpty()) {            return 0;        }         long result = 0;        try {            result = Long.parseLong(numStr);        } catch (NumberFormatException e) {            // The number is too large for a long, so it's definitely out of int range.            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;        }         result *= sign;         if (result > Integer.MAX_VALUE) {            return Integer.MAX_VALUE;        }        if (result < Integer.MIN_VALUE) {            return Integer.MIN_VALUE;        }         return (int) result;    }}

Complexity

Time

O(n)

Space

O(n)

Trade-offs

Pros

  • The logic can be easier to follow by separating concerns: trimming, sign detection, and number parsing.

  • Leverages robust, built-in library functions, potentially reducing bugs in the core number conversion logic.

Cons

  • Creates intermediate strings (trim(), substring()), leading to O(n) space complexity in the worst case.

  • Relies on built-in parsing functions (Long.parseLong()) and exception handling, which might not be permitted in an interview context that aims to test your ability to implement the parsing logic from scratch.

  • The overhead of creating new strings and handling exceptions can make it slightly slower in practice than a direct, index-based approach.

Solutions

// https://leetcode.com/problems/string-to-integer-atoi/ public partial class Solution { public int MyAtoi ( string str ) { int i = 0 ; long result = 0 ; bool minus = false ; while ( i < str . Length && char . IsWhiteSpace ( str [ i ])) { ++ i ; } if ( i < str . Length ) { if ( str [ i ] == '+' ) { ++ i ; } else if ( str [ i ] == '-' ) { minus = true ; ++ i ; } } while ( i < str . Length && char . IsDigit ( str [ i ])) { result = result * 10 + str [ i ] - '0' ; if ( result > int . MaxValue ) { break ; } ++ i ; } if ( minus ) result = - result ; if ( result > int . MaxValue ) { result = int . MaxValue ; } if ( result < int . MinValue ) { result = int . MinValue ; } return ( int ) result ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem