algoadvance

Leetcode 8. String to Integer (atoi)

Problem Statement

The problem “String to Integer (atoi)” requires us to implement a function that converts a string to a 32-bit signed integer (similar to the C/C++ atoi function).

The function should handle the following cases:

  1. Discard all leading whitespaces.
  2. Sign of the number.
  3. Overflow and underflow of 32-bit signed integer range.
  4. Invalid input characters after the numerical part should be ignored.

The range for 32-bit signed integer is [-2³¹, 2³¹ − 1] which translates to [-2147483648, 2147483647].

Clarifying Questions

  1. Input:
    • Can the input string be empty? (Yes, return 0 in that case)
    • Can the string contain leading and trailing spaces? (Yes, leading spaces should be discarded)
    • Can the string have non-numeric characters? (Yes, stop at first non-numeric character)
  2. Output:
    • What should be returned if the resultant integer is outside the range of 32-bit signed integer? (Return Integer.MAX_VALUE or Integer.MIN_VALUE accordingly)

Strategy

  1. Trimming: Remove leading whitespaces from the string.
  2. Sign Handling: Check for the sign of the number (optional ‘+’ or ‘-‘ character).
  3. Conversion: Convert the following numerical part into an integer until a non-numeric character is found or end of the string is reached.
  4. Validation: Handle overflow and underflow; return appropriate constants if limits are exceeded.

Code

public class Solution {
    public int myAtoi(String s) {
        // Step 1: Trim whitespaces
        s = s.trim();
        if (s.isEmpty()) return 0;

        // Step 2: Handle sign
        int sign = 1;
        int startIndex = 0;
        if (s.charAt(0) == '-') {
            sign = -1;
            startIndex = 1;
        } else if (s.charAt(0) == '+') {
            startIndex = 1;
        }

        // Step 3: Convert digits to number
        long result = 0;
        for (int i = startIndex; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!Character.isDigit(c)) break;
            result = result * 10 + (c - '0');

            // Step 4: Check overflow and underflow conditions
            if (sign * result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            if (sign * result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        }
        
        return (int)(sign * result);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // Example tests
        System.out.println(solution.myAtoi("42")); // Output: 42
        System.out.println(solution.myAtoi("   -42")); // Output: -42
        System.out.println(solution.myAtoi("4193 with words")); // Output: 4193
        System.out.println(solution.myAtoi("words and 987")); // Output: 0
        System.out.println(solution.myAtoi("-91283472332")); // Output: -2147483648 (Integer.MIN_VALUE)
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI