Integer to Roman solution using TypeScript
Below is my TypeScript solution to the LeetCode "Integer to Roman" question using a Greedy Algorithm.
Time Complexity: Because the input will always be smaller than 3,999 and the resulting string is of a limited length, the time complexity is O(1).
Space Complexity: This approach will also use a constant amount of space, so the space complexity is O(1).
/**
* Find a Roman Numeral that represents a given number.
* Input is guaranteed to be within the range from 1 to 3999.
*
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* Input: 1994
* Output: MCMXCIV
* Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
*/
function intToRoman(num: number): string {
let result = "";
while (num) {
const largest = LargestSymbol(num);
result += largest.symbol;
num -= largest.value;
}
return result;
};
/**
* Find a Roman Numeral symbol which represents the
* largest value that is still smaller than or equal
* to the value of a given number.
*
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* Input: 2000
* Output: { symbol: 'M', value: 1000 }
*/
function LargestSymbol(num: number) {
const map = new Map([
['M', 1000],
['CM', 900],
['D', 500],
['CD', 400],
['C', 100],
['XC', 90],
['L', 50],
['XL', 40],
['X', 10],
['IX', 9],
['V', 5],
['IV', 4],
['I', 1]
]);
let result = { symbol: "", value: 0 };
for (let [symbol, value] of map) {
if (value <= num) {
result = { symbol, value }
break;
}
}
return result;
}