LeetCode 12 Solution

Problem Statement (LeetCode 12 - Integer to Roman)

Given an integer, convert it to a Roman numeral.

Constraints

• 1 <= num <= 3999

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.

---

Examples

Example 1

Input: num = 58
Output: "LVIII"
Explanation: 58 = 50 + 5 + 3 = "LVIII".

Example 2

Input: num = 1994
Output: "MCMXCIV"
Explanation: 1994 = 1000 + 900 + 90 + 4 = "MCMXCIV".

---

Optimal Approach: Greedy Approach

Intuition

1. Predefine Roman symbols in a sorted order (from largest to smallest). This allows us to convert the number greedily from the highest value down.
2. Iterate through the sorted Roman numeral values, and for each, subtract it from num as many times as possible while appending the corresponding Roman symbol to the result string.
3. Stop when the number becomes zero.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    string intToRoman(int num) {
        // Predefined values and their corresponding Roman numerals
        vector<pair<int, string>> values = {
            {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
            {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
            {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
        };
        
        string result = "";
        
        // Process each value pair
        for (const auto& [value, symbol] : values) {
            while (num >= value) {
                result += symbol;  // Add Roman numeral symbol to the result
                num -= value;  // Subtract the value from num
            }
        }
        
        return result;
    }
};

---

Step-by-Step Explanation of Code

1. Define Roman Numeral Mappings:

   • We use a vector of pairs where each pair consists of a value and the corresponding Roman numeral.
   • The values are sorted in descending order to allow for greedy processing from the largest value down.

2. Iterate Through the Mappings:

   • For each value-symbol pair, we check if the current num is greater than or equal to the value.
   • If it is, we append the symbol to the result string and subtract the value from num.
   • This process is repeated until num becomes zero.

3. Return the Result:

   • The final result string contains the Roman numeral representation of the input integer.

---

Dry Run with Example

Input: num = 1994

Step 1: Check value 1000, num = 1994 >= 1000, append "M", num = 994
Step 2: Check value 900, num = 994 >= 900, append "CM", num = 94
Step 3: Check value 90, num = 94 >= 90, append "XC", num = 4
Step 4: Check value 4, num = 4 >= 4, append "IV", num = 0
Final result: "MCMXCIV"

✅ Output: "MCMXCIV"

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (String Manipulation)	O(n)	O(1)	Inefficient for large numbers due to multiple string manipulations
Greedy Approach (Best)	O(1) (constant time)	O(1)	Optimal and runs in constant time because the number of possible symbols is fixed.

---

Why Greedy Approach is the Best

1. Time Complexity is Constant: The number of possible Roman numeral symbols is fixed and does not depend on the size of the number.
2. Space Complexity is Constant: We are only using a few variables and an array of fixed size for the symbols.
3. Greedy Approach is Direct and Efficient: Each step directly handles a part of the number, ensuring that we handle the largest possible values first.

---

Complexity Analysis

• Time Complexity: O(1)
  The time complexity is constant because we are iterating over a fixed number of Roman numeral symbols (13 in total).

• Space Complexity: O(1)
  We only use a fixed amount of space to store the Roman numeral symbols and the result string.

---

Conclusion

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

Recommended Problems for Practice

1. Roman to Integer 🏛️
2. Integer to English Words 📝
3. Additive Number 🔢

🚀 Master the Greedy Algorithm for Optimal Solutions!