leetcode

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;
}

more LeetCode posts