LeetCode 13 Solution

Problem Statement (LeetCode 13 - Roman to Integer)

Given a Roman numeral, convert it to an integer.

Roman Numeral System

The Roman numeral system uses the following symbols:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

Special combinations like IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, and CM = 900 are also used to avoid repeating symbols.

---

Optimal Approach: Greedy Approach with Subtraction Rule

Intuition

1. Traverse the Roman numeral string from left to right.
2. If the current Roman numeral is smaller than the next one, subtract the current value from the next one (this handles cases like IV = 4 or IX = 9).
3. Otherwise, add the current value to the total sum.

Why This Approach Works

• The Roman numeral system uses a combination of addition and subtraction. The greedy approach allows us to handle both scenarios:
  • Addition: When a smaller numeral precedes a larger one (e.g., VI = 6), we add the values.
  • Subtraction: When a smaller numeral precedes a larger one (e.g., IV = 4), we subtract the smaller value.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    int romanToInt(string s) {
        // Define the value of each Roman numeral
        unordered_map<char, int> roman_map = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        
        int result = 0;
        
        // Traverse the string
        for (int i = 0; i < s.size(); ++i) {
            // If the current character's value is less than the next character's value, subtract it
            if (i + 1 < s.size() && roman_map[s[i]] < roman_map[s[i + 1]]) {
                result -= roman_map[s[i]];
            } else {
                result += roman_map[s[i]];
            }
        }
        
        return result;
    }
};

---

Step-by-Step Explanation of Code

1. Define a Map for Roman Numerals:
   We create an unordered map (roman_map) to store the Roman numeral characters (I, V, X, etc.) and their corresponding integer values.

2. Initialize Result Variable:
   The result variable is initialized to 0 to accumulate the final integer value.

3. Traverse the Roman Numeral String:
   We loop through each character in the input string s:

   • If the current character's value is smaller than the next character's value (e.g., I before V in IV), we subtract its value from result (since Roman numerals like IV represent 4).
   • Otherwise, we simply add its value to the result.

4. Return the Result:
   After the loop, result contains the integer equivalent of the Roman numeral, which is returned.

---

Dry Run with Example

Input: s = "IX"

Step 1: i = 0, s[i] = 'I', s[i+1] = 'X'
        roman_map['I'] = 1, roman_map['X'] = 10
        Since 1 < 10, subtract 1 from result: result = -1
Step 2: i = 1, s[i] = 'X'
        roman_map['X'] = 10
        Add 10 to result: result = 9
Final result: 9

✅ Output: 9

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (String Manipulation)	O(n)	O(1)	This approach could involve multiple string manipulations which are inefficient.
Greedy with Map (Best)	O(n)	O(1)	Optimal approach that processes the string in one pass using a map for constant time lookups.
Dynamic Programming	O(n)	O(n)	DP is unnecessary for this problem, as we do not need to store intermediate results.

---

Why Greedy Approach is the Best

1. Time Complexity is Linear: We only need one pass through the string, which results in O(n) time complexity.
2. Space Complexity is Constant: We only use an unordered map for lookups and a few variables, resulting in O(1) space complexity.
3. Simple and Efficient: The greedy approach handles both addition and subtraction cases in constant time.

---

Complexity Analysis

• Time Complexity: O(n)
  We traverse the string once, and each lookup in the unordered map is O(1).

• Space Complexity: O(1)
  The space complexity is constant since we only use an unordered map and a result variable.

---

Conclusion

✅ Best approach: Greedy Approach with Map
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
✅ Optimal Solution for the Problem

Recommended Problems for Practice

1. Integer to Roman 🏛️
2. Roman to Integer (Alternative) 📝
3. Additive Number 🔢

🚀 Master the Greedy Algorithm for Optimal Solutions!