Integer to Roman
mediumTime: O(1)Space: O(1)
Recognize the pattern
integer to Roman numeralgreedy largest-firstinclude subtractive forms in table
Brute force idea
Not applicable — greedy IS the natural approach.
Better approach
Table of (value, symbol) including subtractive forms. Greedily subtract largest possible value, append symbol. O(1) since input ≤ 3999.
Key invariant
Including IV, IX, XL, XC, CD, CM in the table means the greedy algorithm handles subtractive notation naturally.
Watch out for
Not including subtractive forms — handling 4, 9, 40, etc. as special cases is much more complex.