String to Integer Conversion Algorithm

The string to integer conversion problem requires parsing numeric strings while handling whitespace, signs, and integer overflow conditions according to 32-bit signed integer constraints.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the maximum expected input string length? (This affects overflow handling and memory considerations)
2. Should we handle strings with leading/trailing whitespace, or assume clean input?
3. Do we need to support negative numbers? What about positive signs?
4. How should we handle overflow conditions? Should we return Integer.MAX_VALUE or Integer.MIN_VALUE?
5. Can we mutate the input string, or must we work with an immutable copy?

Restatement of the problem in my own words:

Implement a function that converts a string to a 32-bit signed integer (similar to C's atoi function). The function should:

• Ignore leading whitespace
• Handle optional '+' or '-' sign
• Read digits until a non-digit character is encountered
• Stop parsing at the first non-digit character or end of string
• Clamp values to 32-bit signed integer range [-2³¹, 2³¹ - 1]

Clarification of inputs, outputs, and constraints:

• Input: A string that may contain letters, digits, spaces, and signs
• Output: Integer value in the range [-2147483648, 2147483647]
• Constraints: String length can be up to 200 characters, and we must handle integer overflow correctly

Assumptions I'm making:

1. The input string is valid and will not be null (as per typical FAANG expectations)
2. We only care about the first valid integer in the string
3. The conversion should stop at the first non-digit character after the sign or digits
4. We're implementing standard atoi behavior with proper overflow handling

Data shape and hidden structure:

The input is a sequence of characters that can be categorized into:

• Leading whitespace (ignored)
• Optional sign (+ or -)
• Numeric digits (0-9) that form the integer value
• Any remaining characters after the numeric portion are ignored

The hidden structure is that we're parsing a string as if it were a mathematical integer expression, where the numeric portion forms the actual value to be returned. The challenge lies in proper state management and overflow detection during parsing.

2. Pattern Recognition

Identifying the most likely pattern or patterns

This problem follows the String Parsing and State Machine patterns. The core challenge is to convert a string representation of a number into an integer while handling various edge cases and constraints.

Wording that signals the pattern

The key phrases that signal this pattern:

• "Implement atoi" - This is a classic string parsing problem that requires converting characters to numeric values
• "whitespace characters" - Indicates we need to handle leading whitespace as part of parsing
• "sign character" - Signals we need to detect and process +/- signs in the string
• "numeric characters" - Indicates we're looking for digit sequences that form numbers
• "32-bit signed integer range" - This signals we need to handle overflow conditions and clamping

Why this problem fits that pattern

This is a canonical string-to-integer conversion problem that requires:

1. Sequential character-by-character parsing of input
2. State tracking (whitespace, sign, digits)
3. Overflow detection and handling within 32-bit integer constraints
4. Proper termination when encountering invalid characters

The problem structure mirrors typical parsing problems where we process input sequentially while maintaining state and applying transformation rules.

Core insight needed to solve it

The key insight is that we need to process the string character-by-character while maintaining a running total, but we must:

1. Handle leading whitespace by skipping it
2. Detect and apply sign (+/-) appropriately
3. Convert digits to numeric values while building the result
4. Check for overflow before it happens (since we're dealing with 32-bit integer limits)
5. Stop parsing when encountering invalid characters or reaching end of string

This requires careful state management and overflow prevention, which makes it a classic example of parsing with boundary condition handling.

3. Approach Evolution

My first instinct is to parse the string character by character and build up the integer value, but that's O(n²) in the worst case if I keep converting substrings to integers. Let me think about how to optimize this.

The key insight is that I can process the string in one pass, maintaining a running total and handling overflow checks at each step. I notice that if I maintain the invariant that my running result never exceeds Integer.MAX_VALUE during processing, I can detect overflow early and return the appropriate boundary value.

Let me think about this more systematically:

First, I'll handle edge cases like leading whitespace and sign detection. Then I'll iterate through the digits, updating my result by multiplying by 10 and adding the new digit. The critical optimization is checking for overflow before updating the result.

I notice that if I maintain the invariant that my running result is always within valid integer bounds, I can reduce it to O(n) time complexity by processing each character exactly once. The key insight is that I should check for overflow before updating, not after.

The approach I'll use:

1. Skip leading whitespace
2. Handle optional sign character
3. Process digits one by one, checking for overflow at each step
4. Return appropriate boundary values when overflow occurs

This is better than a brute force approach because:

• It's linear time O(n) instead of potentially quadratic
• It handles overflow gracefully without requiring extra space for intermediate strings
• It processes input once with no redundant operations

Here's my optimized approach:

First, I'll implement a brute force solution that converts to integer at each step - this is O(n²) because string conversion is O(n) and we do it n times. Then I'll optimize to process one digit at a time, checking overflow conditions.

The key optimization is that we can detect overflow before it happens by checking if (result * 10 + digit) would exceed Integer.MAX_VALUE. If it would, we return the appropriate boundary value immediately.

The final approach will be:

1. Skip leading whitespace
2. Read sign character if present
3. Process digits one by one, maintaining running total
4. Check overflow condition at each step before updating result
5. Return bounded result when overflow occurs

This approach ensures O(n) time and O(1) space complexity while handling all edge cases correctly.

4. Data Structure Choice

For the string to integer conversion problem, I'll use a combination of primitive data types and standard Java collections:

Primary Data Structures:

1. char[] or String - The input string is the primary data structure. I'll use char[] for direct character access as it's more efficient than String operations in this context.

2. int variables - For tracking the result, current digit, and index position. These are sufficient since we're only processing one integer at a time.

3. StringBuilder - Used temporarily to build the numeric portion of the string, though I'll likely avoid this in favor of direct character processing for efficiency.

Why These Choices:

The char[] provides O(1) random access to characters, which is essential for parsing through the string sequentially. Using primitive int variables avoids unnecessary object creation overhead and provides O(1) operations for arithmetic.

Space Considerations:

The space complexity is O(1) as we only use a fixed number of variables regardless of input size. We don't need additional data structures like hash maps or stacks for this problem.

Helper Structures:

I'll use a simple int variable to track the current position in the string and another to accumulate the result. No complex helper structures are needed since we're processing linearly from left to right.

The simplicity of these data structures aligns with the problem's requirements - we just need to parse and convert a string representation of an integer into its numeric form, maintaining proper overflow handling.

5. Algorithm Walkthrough

Let me trace through the algorithm with the example input " -42words321":

Step 1: Skip leading whitespace

• Process characters: ' ', ' ', ' '
• Position advances to index 3 where '-' is found
• No change to result value yet

Step 2: Handle sign detection

• Current character is '-' at index 3
• Set sign = -1
• Advance position to index 4

Step 3: Process digits

• Index 4: '4' → result = 0 * 10 + 4 = 4
• Index 5: '2' → result = 4 * 10 + 2 = 42
• Index 6: 'w' → Not a digit, so we stop processing

Step 4: Apply sign and clamp to 32-bit range

• result = -1 * 42 = -42
• Clamp to [-2^31, 2^31 - 1] = [-2147483648, 2147483647]
• -42 is within range, so final result = -42

Key invariants maintained:

• result never exceeds 32-bit integer bounds during calculation
• Sign is applied only once and after whitespace/digits are processed
• Processing stops immediately when non-digit character is encountered
• Leading zeros are naturally handled by the multiplication/accumulation logic

Edge case handling:

• When input is " +0042" → leading zeros are ignored in accumulation, result = 42
• When input is " -0042words" → same as above, result = -42
• When input is " 999999999999" → clamps to 2147483647 due to overflow
• When input is " -999999999999" → clamps to -2147483648 due to underflow

6. Java Solution

public class Solution {
    public int myAtoi(String s) {
        // Handle null or empty string
        if (s == null || s.isEmpty()) {
            return 0;
        }
        
        int index = 0;
        int sign = 1;
        int result = 0;
        
        // Step 1: Skip leading whitespace
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }
        
        // Step 2: Check for sign
        if (index < s.length()) {
            char c = s.charAt(index);
            if (c == '+') {
                sign = 1;
                index++;
            } else if (c == '-') {
                sign = -1;
                index++;
            }
        }
        
        // Step 3: Convert digits to integer
        while (index < s.length()) {
            char c = s.charAt(index);
            
            // If not a digit, stop conversion
            if (c < '0' || c > '9') {
                break;
            }
            
            int digit = c - '0';
            
            // Check for integer overflow
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
            index++;
        }
        
        return sign * result;
    }
}

This solution handles the string-to-integer conversion according to the standard atoi specification, including proper handling of whitespace, signs, and integer overflow conditions. The implementation processes the string character by character while maintaining the sign and building the result incrementally.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the input string. The algorithm processes each character at most once in a single pass through the string. Each operation within the loop (character checking, arithmetic operations, overflow checks) takes constant time.

Space Complexity: O(1) - only using a fixed amount of extra space regardless of input size. The variables result, sign, and i are all scalar values that don't scale with input size.

Why these bounds are correct:

• The time complexity is linear because we iterate through the string exactly once, and all operations inside the loop are O(1)
• The space complexity is constant because we only maintain a few integer variables and do not use any data structures that grow with input size
• The solution is optimal for this problem since we must examine each character at least once to determine the integer value

The solution is near-optimal as we cannot do better than O(n) for parsing a string of length n to convert it to an integer, since we must read each character to determine the final result.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Should return 0, not throw an exception
• Single character: Must handle '0', '+', '-', and digit cases correctly
• Only whitespace: Should return 0, not throw an exception

Duplicate Values and Repeated States

• Leading zeros: "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000## 8. Edge Cases & Pitfalls

Empty and minimal inputs: The function must handle empty strings gracefully, returning 0. Single character inputs like "42" or "-42" should work correctly.

Duplicate values and repeated states: The algorithm handles duplicate digits by processing them sequentially. Repeated leading zeros should be treated as part of the number parsing.

Boundary conditions: The most critical edge case is integer overflow. When parsing "2147483647" (max int), the result should be Integer.MAX_VALUE. For "-2147483648" (min int), it should return Integer.MIN_VALUE. Any overflow beyond these bounds must be handled properly.

Common implementation mistakes:

1. Not handling leading whitespace correctly - some implementations fail to skip all leading spaces before parsing
2. Overflow detection timing - checking overflow too late can cause Integer overflow exceptions in intermediate calculations
3. Incorrect handling of signs - failing to properly recognize and apply the sign when it appears after whitespace
4. Missing validation of valid digit characters - allowing non-digit characters to be processed as part of the number
5. Not properly handling the case where the string contains only whitespace or invalid characters

9. Alternative Approaches

Alternative approach: A two-pass solution where we first validate the entire string and then parse it. This would involve:

1. First pass: Check for valid format (whitespace, optional sign, digits only)
2. Second pass: Convert to integer with overflow checks

Trade-offs: This approach is more readable but has higher space complexity due to storing the cleaned string and requires two passes through the input. The chosen solution is more efficient with O(1) space and single pass.

When to prefer alternatives: The two-pass approach might be preferred in scenarios where readability is more important than micro-optimization, or when the input validation logic is complex and needs to be separated from parsing.

10. Test Cases

Sample test cases:

• "42" → 42
• "-42" → -42
• " +42" → 42
• "4193 with words" → 4193
• "words and 987" → 0
• "-91283472332" → Integer.MIN_VALUE (-2147483648)
• "91283472332" → Integer.MAX_VALUE (2147483647)
• " -0012a42" → -12

Tricky case: " +001234567890" → 2147483647 (overflow case) Boundary case: " -2147483648" → -2147483648 (exact min value)

11. Final Summary

The solution uses a single pass through the input string while maintaining proper state tracking to handle whitespace, signs, and overflow conditions. It efficiently converts valid numeric strings to integers within the 32-bit signed integer range, handling all edge cases including overflow and invalid input gracefully.

The key insight is to process characters sequentially while maintaining the current numeric value, checking for overflow conditions at each step before updating the accumulated result. This ensures correctness without requiring additional space or multiple passes through the input data.

9. Alternative Approaches

There are several alternative approaches to implementing the string-to-integer conversion, each with different trade-offs:

1. Using Built-in Integer.parseInt() with Exception Handling

public int myAtoi(String s) {
    try {
        return Integer.parseInt(s.trim());
    } catch (NumberFormatException e) {
        // Handle overflow cases
        return s.trim().startsWith("-") ? Integer.MIN_VALUE : Integer.MAX_VALUE;
    }
}

This approach is the most concise but has significant drawbacks. It relies on exception handling for overflow detection, which is inefficient and not idiomatic for production code. The built-in method also doesn't handle all edge cases like leading zeros or whitespace properly in the context of this problem.

2. State Machine Approach A finite state machine can model the parsing process with states like "start", "sign", "number", and "end". This is more complex but provides clean separation of concerns and makes the parsing logic explicit.

3. Two-Pointer Approach with Manual Parsing Instead of using charAt(), we could use a two-pointer technique where we maintain indices to track the current position and parse segments incrementally. This is more complex for this specific problem but can be useful in scenarios where we're processing multiple strings.

4. Regular Expression-Based Solution Using regex patterns like ^[+-]?\\d+ to match the integer portion. However, this is inefficient for parsing and doesn't provide better control over edge case handling.

The chosen solution is preferred because it's more readable, handles overflow explicitly with clear bounds checking, and provides better performance than exception-based approaches. The direct character-by-character parsing is more efficient than regex or built-in methods for this specific use case, and it's easier to reason about the edge cases and overflow conditions.

10. Test Cases

public class Solution {
    public int myAtoi(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        int index = 0;
        int sign = 1;
        int result = 0;
        
        // Skip leading whitespace
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }
        
        // Handle sign
        if (index < s.length()) {
            if (s.charAt(index) == '-') {
                sign = -1;
                index++;
            } else if (s.charAt(index) == '+') {
                sign = 1;
                index++;
            }
        }
        
        // Convert digits
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            int digit = s.charAt(index) - '0';
            
            // Check for overflow before updating result
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
            index++;
        }
        
        return sign * result;
    }
}

Sample Test Cases

// Test case 1: Basic conversion
String input1 = "42";
// Expected output: 42

// Test case 2: Negative number
String input2 = "   -42";
// Expected output: -42

// Test case 3: Leading zeros
String input3 = "   +1234567890";
// Expected output: 1234567890

// Test case 4: Overflow
String input4 = "2147483647"; // Integer.MAX_VALUE
// Expected output: 2147483647

// Test case 5: Overflow with positive sign
String input5 = "2147483648"; // Integer.MAX_VALUE + 1
// Expected output: 2147483647 (overflow to max)

// Test case 6: Underflow
String input6 = "-2147483649"; // Integer.MIN_VALUE - 1
// Expected output: -2147483648 (overflow to min)

// Test case 7: Invalid input with letters after digits
String input7 = "4193 with words";
// Expected output: 4193

// Test case 8: Empty string
String input8 = "";
// Expected output: 0

// Test case 9: Only whitespace
String input9 = "   ";
// Expected output: 0

// Test case 10: Only signs
String input10 = "+";
// Expected output: 0

// Test case 11: Leading zeros
String input11 = "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000## 10. Test Cases

```java
public class Solution {
    public int myAtoi(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        int index = 0;
        int sign = 1;
        int result = 0;
        
        // Step 1: Skip leading whitespace
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }
        
        // Step 2: Check for sign
        if (index < s.length()) {
            if (s.charAt(index) == '-') {
                sign = -1;
                index++;
            } else if (s.charAt(index) == '+') {
                index++;
            }
        }
        
        // Step 3: Convert digits to integer
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            int digit = s.charAt(index) - '0';
            
            // Check for overflow before updating result
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
            index++;
        }
        
        return sign * result;
    }
}

Sample Test Cases:

1. Basic case: "42" → 42
2. With sign: "-42" → -42
3. Leading whitespace: " 42" → 42
4. Overflow case: "999999999999" → 2147483647 (Integer.MAX_VALUE)
5. Underflow case: "-999999999999" → -2147483648 (Integer.MIN_VALUE)
6. Invalid input: "words and 987" → 0 (stops at first non-digit)
7. Leading zeros: "00000000000000123456" → 123456
8. Empty string: "" → 0
9. Only whitespace: " " → 0
10. Sign with no digits: "+-12" → 0 (invalid format)

Tricky Edge Cases:

• Leading zeros followed by digits: `"000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000## 10. Test Cases

public class Solution {
    public int myAtoi(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        int index = 0;
        int sign = 1;
        int result = 0;
        
        // Step 1: Skip leading whitespace
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }
        
        // Step 2: Check for sign
        if (index < s.length()) {
            if (s.charAt(index) == '-') {
                sign = -1;
                index++;
            } else if (s.charAt(index) == '+') {
                sign = 1;
                index++;
            }
        }
        
        // Step 3: Convert digits
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            int digit = s.charAt(index) - '0';
            
            // Check for overflow before updating result
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
            index++;
        }
        
        return sign * result;
    }
}

Sample Test Cases:

1. Normal case: "42" → 42
2. With sign: "-42" → -42
3. Leading whitespace: " 42" → 42
4. Overflow case: "999999999999" → 2147483647 (Integer.MAX_VALUE)
5. Underflow case: "-999999999999" → -2147483648 (Integer.MIN_VALUE)
6. Invalid input: "words and 987" → 0
7. Empty string: "" → 0
8. Only whitespace: " " → 0
9. Leading zeros: "000000000000001" → 1
10. Sign after digits: "42-" → 42

11. Final Summary

The solution uses a single pass through the string with O(1) space complexity, handling all edge cases including overflow conditions by checking bounds before arithmetic operations. The key insight is to process characters sequentially while maintaining the sign and building the result incrementally, with overflow checks that prevent integer overflow during computation.

The approach is optimal because:

• Time complexity is O(n) where n is the length of input string
• Space complexity is O(1)
• It handles all edge cases in one pass without requiring additional data structures
• The overflow check prevents incorrect results by detecting overflow before it occurs

11. Final Summary

The core idea is to convert a string to an integer by processing characters sequentially while maintaining overflow bounds and handling edge cases like leading whitespace, signs, and invalid characters. This solution works efficiently by using a single pass with careful boundary checking to prevent integer overflow, making it optimal for the given constraints.

The solution is efficient because it processes each character at most once (O(n) time complexity) and uses only constant extra space (O(1) space complexity). The key insight is to validate numeric characters and handle overflow conditions during processing rather than after conversion, which avoids potential issues with intermediate large values.

This approach is optimal for the problem as it meets all requirements: handles edge cases properly, maintains correctness under integer overflow constraints, and achieves linear time complexity with minimal space usage. The solution demonstrates strong understanding of string parsing, integer boundary conditions, and robust error handling in production-level code.