LeetCode 8 Solution

 

Problem Statement (LeetCode 8 - String to Integer (atoi))

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

Rules for Conversion:

1. Ignore leading whitespaces (' ').
2. Check for the sign (+ or -).
3. Process numeric digits until a non-digit is encountered.
4. Clamp the value to fit within the range [-2³¹, 2³¹ - 1] if it overflows.
5. Ignore extra characters after digits.

Function Signature

int myAtoi(string s);

---

Example Input & Output

Example 1

Input: s = "42"
Output: 42

Example 2

Input: s = "   -42"
Output: -42

Example 3

Input: s = "4193 with words"
Output: 4193

Example 4

Input: s = "words and 987"
Output: 0

Example 5 (Overflow Case)

Input: s = "-91283472332"
Output: -2147483648  (Clamped to INT_MIN)

---

Optimal Approach: Parsing with Overflow Handling (O(n) Solution)

Intuition

1. Skip leading spaces.
2. Detect sign (+/-).
3. Extract digits while checking for integer overflow.
4. Clamp the value if it exceeds INT_MAX or INT_MIN.

Time & Space Complexity

• Time Complexity: O(n) (We traverse the string once).
• Space Complexity: O(1) (Only a few integer variables).

---

LeetCode-Compatible C++ Code

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, sign = 1;
        long long num = 0;
        
        // 1. Skip leading whitespaces
        while (i < s.length() && s[i] == ' ') {
            i++;
        }

        // 2. Handle optional sign
        if (i < s.length() && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }

        // 3. Process numeric digits
        while (i < s.length() && isdigit(s[i])) {
            num = num * 10 + (s[i] - '0');

            // 4. Handle overflow
            if (num * sign >= INT_MAX) return INT_MAX;
            if (num * sign <= INT_MIN) return INT_MIN;
            
            i++;
        }

        return num * sign;
    }
};

---

Step-by-Step Explanation

Example 1: s = "42"

Step 1: Skip spaces → i = 0
Step 2: No sign → sign = 1
Step 3: Extract '4' → num = 4
Step 4: Extract '2' → num = 42
Final Output: 42

---

Example 2: s = " -42"

Step 1: Skip spaces → i = 3
Step 2: Sign detected '-' → sign = -1
Step 3: Extract '4' → num = 4
Step 4: Extract '2' → num = 42
Final Output: -42

---

Example 3: s = "4193 with words"

Step 1: No spaces
Step 2: No sign → sign = 1
Step 3: Extract '4' → num = 4
Step 4: Extract '1' → num = 41
Step 5: Extract '9' → num = 419
Step 6: Extract '3' → num = 4193
Step 7: Stop at 'w'
Final Output: 4193

---

Example 4: s = "words and 987"

Step 1: No spaces
Step 2: No sign
Step 3: First char is 'w' (not a digit) → return 0
Final Output: 0

---

Example 5: Overflow Case s = "-91283472332"

Step 1: Skip spaces
Step 2: Sign detected '-'
Step 3: Extract digits → num = 91283472332 (Exceeds INT_MIN)
Step 4: Clamp to -2147483648
Final Output: -2147483648

---

Alternative Approaches & Why Not?

1️⃣ Using stoi() Built-in Function

• Directly converts string to integer.
• ❌ Throws exceptions on invalid input.
• ❌ Doesn’t handle overflow correctly.

2️⃣ Regex-Based Extraction

• Extracts valid numbers using regular expressions.
• ❌ Unnecessary complexity.
• ❌ Slower than direct parsing.

3️⃣ Stack-Based Parsing

• Use stack to store digits, then process.
• ❌ Extra space (O(n)).
• ❌ Unnecessary for a linear problem.

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Direct Parsing (Best)	O(n)	O(1)	Handles all edge cases efficiently
Built-in stoi()	O(n)	O(1)	May throw exceptions
Regex-Based Approach	O(n)	O(n)	Overhead of regex
Stack-Based Parsing	O(n)	O(n)	Unnecessary space usage

---

Conclusion

• The direct parsing approach is the most efficient.
• Regex & stacks add unnecessary complexity.
• Handles edge cases like leading spaces, signs, invalid characters, and overflow.

---

Recommended Problems for Practice

1. Reverse Integer 🔄
2. Valid Number 📏
3. Basic Calculator II ➕➖✖️➗

---

🚀 Master String Parsing & Edge Cases!