Integer to Roman

LeetCode 12: Integer to Roman Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a greedy strategy by iterating through a predefined list of Roman values (including subtraction pairs like "IV") from largest to smallest, appending symbols to the result string while reducing the input number.

The Integer to Roman problem asks us to convert a given integer num (ranging from 1 to 3999) into its Roman numeral string representation. Standard Roman numerals are additive (e.g., III is 1+1+1), but specific cases involve subtraction (e.g., IV is 5-1). The solution for LeetCode 12 requires handling these rules efficiently to construct the correct string sequence.

Brute Force Approach for Integer to Roman

A naive or brute force approach to Integer to Roman often involves attempting to decompose the number digit by digit using extensive conditional logic (nested if-else or switch statements).

For example, one might try to handle the thousands place, then the hundreds place, then the tens, and finally the ones, writing unique logic for every possible digit (0-9) at every position.

Pseudo-code for Naive Approach:

function intToRoman(num):
    result = ""
    thousands = num / 1000
    if thousands == 1: result += "M"
    if thousands == 2: result += "MM"
    if thousands == 3: result += "MMM"
    
    hundreds = (num % 1000) / 100
    if hundreds == 1: result += "C"
    if hundreds == 4: result += "CD"
    // ... extensive checks for 2, 3, 5, 6, 7, 8, 9 ...
    
    // Repeat for tens and ones...
    return result

Time Complexity: $O(1)$ (since the input is bounded, the operations are constant, though the code is long). Why it fails: While this approach doesn't technically exceed the time limit due to the small input constraint (3999), it fails engineering standards. It results in "spaghetti code" that is difficult to read, maintain, or debug. It treats a mathematical pattern as a series of unrelated hardcoded cases, increasing the likelihood of typos and logic errors.

Algorithm Strategy: String Manipulation Patterns

1. Define Mappings: Create two lists (or a list of pairs) representing the 13 unique Roman numeral cases. These must be ordered from highest value (1000) to lowest value (1).
2. Initialize Output: Create an empty string builder (or buffer) to hold the result.
3. Iterate and Consume: Loop through the mapped values. For each (value, symbol) pair:
   • While the current input num is greater than or equal to value:
     • Append symbol to the result string.
     • Subtract value from num.
4. Termination: The process naturally terminates when the loop finishes (which implies num has been reduced to 0).
5. Return: Convert the buffer to a string and return it.

Execution Flow

Let's trace num = 1994:

1. State: num = 1994, result = "".
2. Check 1000 ("M"):
   • 1994 >= 1000. Append "M". num becomes 994. result is "M".
   • 994 < 1000. Move to next symbol.
3. Check 900 ("CM"):
   • 994 >= 900. Append "CM". num becomes 94. result is "MCM".
   • 94 < 900. Move to next symbol.
4. Check 500 ("D") through 100 ("C"):
   • 94 is smaller than 500, 400, and 100. Skip these.
5. Check 90 ("XC"):
   • 94 >= 90. Append "XC". num becomes 4. result is "MCMXC".
   • 4 < 90. Move to next symbol.
6. Check 50 ("L") through 5 ("V"):
   • 4 is smaller than 50, 40, 10, 9, 5. Skip these.
7. Check 4 ("IV"):
   • 4 >= 4. Append "IV". num becomes 0. result is "MCMXCIV".
8. Check 1 ("I"):
   • 0 < 1. Loop ends.
9. Final Output: "MCMXCIV".

Proof of Correctness

The correctness relies on the greedy choice property. Roman numerals are constructed by writing the symbols for the largest components first. By iterating through values in strictly descending order and including the subtractive pairs (like 900, 400) as atomic units, we guarantee that we always select the optimal representation for the remaining magnitude of num. Since every integer matches a combination of these 13 values, and we reduce num towards zero, the algorithm is guaranteed to terminate with the correct string.

Pattern Reuse Notes

The pattern of mapping values and converting formats applies to several popular interview questions.

• LeetCode 13: Roman to Integer - The inverse of this problem. It uses a similar lookup map but iterates the string to sum values, handling subtraction by checking lookahead characters.
• LeetCode 8: String to Integer (atoi) - Involves parsing a string to build an integer, requiring careful handling of signs, whitespace, and overflow boundaries, similar to how we handle specific symbol rules here.

Reference Implementation

C++ Solution for LeetCode 12

1#include <string>
2#include <vector>
3
4class Solution {
5public:
6    string intToRoman(int num) {
7        // Define values and symbols in descending order
8        const vector<pair<int, string>> store = {
9            {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
10            {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
11            {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
12        };
13
14        string result = "";
15        
16        // Iterate through each symbol
17        for (const auto& pair : store) {
18            int value = pair.first;
19            string symbol = pair.second;
20            
21            // Greedy: subtract value and append symbol while possible
22            while (num >= value) {
23                result += symbol;
24                num -= value;
25            }
26        }
27        
28        return result;
29    }
30};

Java Solution for LeetCode 12

1class Solution {
2    public String intToRoman(int num) {
3        // Define values and symbols in descending order
4        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
5        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
6        
7        StringBuilder sb = new StringBuilder();
8        
9        // Iterate through each symbol
10        for (int i = 0; i < values.length; i++) {
11            // Greedy: subtract value and append symbol while possible
12            while (num >= values[i]) {
13                sb.append(symbols[i]);
14                num -= values[i];
15            }
16        }
17        
18        return sb.toString();
19    }
20}

Python Solution for LeetCode 12

1class Solution:
2    def intToRoman(self, num: int) -> str:
3        # Define values and symbols in descending order
4        value_map = [
5            (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
6            (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
7            (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
8        ]
9        
10        result = []
11        
12        # Iterate through each symbol
13        for value, symbol in value_map:
14            # Greedy: subtract value and append symbol while possible
15            while num >= value:
16                result.append(symbol)
17                num -= value
18                
19        return "".join(result)