We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

String to Integer (atoi)

Number: 8

Difficulty: Medium

Paid? No

Companies: Meta, Bloomberg, Apple, Google, Goldman Sachs, Microsoft, Niantic, Databricks, Amazon, Adobe, Nvidia, Samsung, Uber

Problem Description

Implement the myAtoi function that converts a string into a 32-bit signed integer. The conversion follows these rules: ignore any leading whitespace, read an optional '+' or '-' sign to determine the integer's sign, convert the subsequent digits into an integer, and stop at the first non-digit character. Finally, clamp the integer value within the range [-2^31, 2^31 - 1].

Key Insights

  • Skip leading spaces in the string.
  • Detect and handle the optional sign indicator ('+' or '-').
  • Read and convert digit characters until a non-digit is encountered.
  • Handle cases with no digits or leading zeros.
  • Clamp the result to fit within the 32-bit signed integer range.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(1) as only a constant amount of extra space is used.

Solution

We iterate through the string to first eliminate any leading whitespace. Next, we check for a sign character to determine if the resulting integer should be negative. We then convert each consecutive digit into an integer, all the while updating the result and checking for potential overflow. If an overflow is detected, we immediately return the appropriate maximum or minimum 32-bit signed integer boundary value. This approach ensures that we strictly follow the conversion rules and efficiently handle edge cases.

Code Solutions

# Python solution for the myAtoi problem.
def myAtoi(s: str) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    i, n = 0, len(s)
    # Skip leading whitespace.
    while i < n and s[i] == ' ':
        i += 1
        
    # Handle sign.
    sign = 1
    if i < n and (s[i] == '+' or s[i] == '-'):
        if s[i] == '-':
            sign = -1
        i += 1
    
    result = 0
    # Convert digits and build the integer.
    while i < n and s[i].isdigit():
        digit = int(s[i])
        # Check for overflow or underflow.
        if result > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        result = result * 10 + digit
        i += 1
        
    return sign * result

# Example usage:
print(myAtoi("42"))
print(myAtoi(" -042"))
print(myAtoi("1337c0d3"))
print(myAtoi("0-1"))
print(myAtoi("words and 987"))
← Back to All Questions