Integer to Roman - Solution & Explanation

Problem Overview: Given an integer between 1 and 3999, convert it into its Roman numeral representation. Roman numerals use combinations of symbols like I, V, X, L, C, D, and M, including subtractive pairs such as IV (4) and IX (9).

Approach 1: Greedy Value-Symbol Mapping (Time: O(1), Space: O(1))

The most practical solution uses a greedy strategy. Create an ordered mapping of integer values to their Roman symbols: 1000 → M, 900 → CM, 500 → D, 400 → CD, 100 → C, 90 → XC, 50 → L, 40 → XL, 10 → X, 9 → IX, 5 → V, 4 → IV, and 1 → I. Iterate through this list from largest to smallest. For each value, repeatedly append the corresponding symbol while the remaining number is greater than or equal to that value, subtracting the value each time.

The key insight is that Roman numerals are constructed using the largest possible symbol at every step. Handling subtractive cases like 900, 400, and 9 directly in the mapping removes special-case logic. Because the Roman numeral range is capped at 3999, the number of iterations is constant, giving effective O(1) time and space complexity. The mapping itself is often stored using arrays or a small hash table, and the final result is built using string concatenation.

Approach 2: Digit-by-Digit Lookup (Time: O(1), Space: O(1))

Another clean approach processes the number by place value. Precompute arrays for thousands, hundreds, tens, and ones. For example, the tens array contains values like "", "X", "XX", "XXX", "XL", and so on. Extract each digit using division and modulo operations from math operations, then concatenate the corresponding Roman string from each lookup table.

This approach avoids loops and repeated subtraction entirely. Each digit maps directly to a prebuilt Roman fragment. Runtime remains constant because the number of digits is fixed (maximum four). The tradeoff is slightly more upfront setup with lookup arrays, but the final code is extremely fast and predictable.

Recommended for interviews: The greedy mapping approach is what most interviewers expect. It mirrors how Roman numerals are actually constructed and demonstrates clear reasoning about ordered values and subtractive notation. A brute-force mindset—trying to build symbols character by character—shows basic understanding, but the greedy mapping shows stronger algorithmic thinking and cleaner implementation.