Integer to Roman
mediumTime: O(1)Space: O(1)
Signals to notice
integer to Roman numeralgreedy largest-firstinclude subtractive forms in table
Brute force first
Not applicable — greedy IS the natural approach.
The key insight
Table of (value, symbol) including subtractive forms. Greedily subtract largest possible value, append symbol. O(1) since input ≤ 3999.
What must stay true
Including IV, IX, XL, XC, CD, CM in the table means the greedy algorithm handles subtractive notation naturally.
Easy way to go wrong
Not including subtractive forms — handling 4, 9, 40, etc. as special cases is much more complex.