Problem Statement in English

You’re given a string s which represents a number.

You need to convert this string into an integer, following the rules of the atoi function.

  • The function should handle leading whitespace, optional signs, and should stop parsing when it encounters a non-digit character.
  • If the parsed integer is out of the 32-bit signed integer range, it should return the appropriate limit.

Approach

We can solve this problem by following these steps:

  • Skip leading whitespace
  • Check for an optional sign
  • Read digits and convert to an integer
  • Handle overflow conditions

Finally , return the integer value.

And we’re done!

Solution in Python


class Solution:
    def myAtoi(self, s: str) -> int:
        if not s:
            return 0
        
        # Constants for 32-bit signed integer range
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        
        i = 0
        n = len(s)
        
        # Step 1: Skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1
        
        # Check if we've reached the end
        if i == n:
            return 0
        
        # Step 2: Check for sign
        sign = 1
        if s[i] == '+':
            i += 1
        elif s[i] == '-':
            sign = -1
            i += 1
        
        # Step 3: Read digits and convert
        res = 0
        while i < n and s[i].isdigit():
            digit = int(s[i])
            res = res * 10 + digit
            
            if sign * res <= INT_MIN:
                return INT_MIN
            if sign * res >= INT_MAX:
                return INT_MAX
            
            i += 1
        
        # Step 4: Apply sign and return
        return res * sign

Complexity

  • Time: $O(n)$
    Since we are iterating through the string once, where n is the length of the string.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables, the space complexity is constant.

And we are done.