Algorithm Day107 - Integer to Roman

Posted on In Views:

📌 Problem

Convert an integer to a Roman numeral. Input is guaranteed to be within the range 1 <= num <= 3999.

💬 Examples

Example 1

1
2
Input: num = 3
Output: "III"

Example 2

1
2
3
Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3

1
2
3
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.

💡 Intuition (Greedy)

Use a greedy approach: repeatedly subtract the largest Roman value that does not exceed the current number and append its symbol. Predefine pairs of values and symbols in decreasing order (including subtractive forms like 900 -> “CM”).

🔢 Java Code (Greedy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length && num > 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }
        return sb.toString();
    }
}

⏱ Complexity Analysis

  • Time: O(1) — bounded by a small constant (max ~15 symbol appends).
  • Space: O(1) — output size is O(1) relative to input bounds.

✍️ Summary

  • Predefine Roman symbols including subtractive pairs.
  • Greedy subtraction + append produces correct Roman numeral efficiently.
  • Java implementation above is simple and interview-friendly.