12. Integer to Roman

📝 Problem Details

• Title: 12. Integer to Roman
• **Link:**https://leetcode.com/problems/integer-to-roman/
• Difficulty: Medium
• Tags/Categories: Greedy Hashmap Strings

💡 Explanation of Solution

To convert an integer to a Roman numeral, we follow a greedy approach. We match the largest Roman numeral value possible from the input number and keep subtracting it until the number becomes 0. Roman numeral rules:

• Basic symbols: I(1), V(5), X(10), L(50), C(100), D(500), M(1000)
• Special subtractive cases: IV(4), IX(9), XL(40), XC(90), CD(400), CM(900)

Key idea:

• Use a list of value-symbol pairs ordered from largest to smallest.
• Iterate over the list and subtract the value from the input number while appending the corresponding symbol to the result string.

⌛ Complexity Analysis

Time Complexity: O(1)
- The number of Roman numeral mappings is constant.
- The number of iterations is limited since the maximum input is 3999.

Space Complexity: O(1)
- We use a constant-size array of mappings and build a result string with a small, bounded number of characters.

💻 Implementation of Solution

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> valueSymbols = {
            {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;
 
        for (const auto& [value, symbol] : valueSymbols) {
            while (num >= value) {
                result += symbol;
                num -= value;
            }
        }
 
        return result;
    }
};