Integer to Roman - Solution & Explanation

Problem Overview: Convert a given integer into its Roman numeral representation. Roman numerals use specific symbols such as I, V, X, L, C, D, and M, combined using additive and subtractive rules (for example, IV for 4 and IX for 9).

Approach 1: Repeated Subtraction with Symbol Mapping (O(n) time, O(1) space)

Start with two parallel arrays: one holding Roman numeral values and another holding their corresponding symbols. Iterate from the largest value (1000 → M) down to the smallest (1 → I). For each value, repeatedly subtract it from the input number while appending the associated symbol to the result string. This approach directly mirrors how Roman numerals are constructed. The loop performs multiple subtractions for each symbol, so the time complexity depends on how many characters end up in the output, typically treated as O(n) relative to the result length.

Approach 2: Greedy Value Selection (O(1) time, O(1) space)

The optimal solution uses a greedy strategy. Maintain an ordered list of value-symbol pairs including subtractive cases such as 900 (CM), 400 (CD), 90 (XC), 40 (XL), 9 (IX), and 4 (IV). Iterate through this list from largest to smallest. At each step, compute how many times the value fits into the current number, append the symbol that many times, and reduce the number using modulus. The key insight is that Roman numerals always prefer the largest valid symbol first, which makes greedy selection correct.

Because the Roman numeral system only supports values up to 3999, the number of iterations is bounded by a small constant. That makes both time and space effectively O(1). The algorithm mostly performs integer division, modulus operations, and string concatenation.

The implementation is straightforward and portable across languages such as Python, Java, C++, C#, C, and JavaScript. The logic relies on simple iteration and string building rather than complex data structures, though the mapping of values to symbols can be stored in an array or a small hash table. The reasoning behind subtractive notation comes from the structure of Roman numerals, which fits naturally into greedy algorithms often discussed in math and string manipulation problems.

Recommended for interviews: Interviewers expect the greedy value-symbol mapping solution. It demonstrates that you understand Roman numeral rules and can encode them efficiently. Starting with a simple repeated subtraction idea shows reasoning, but the greedy list with subtractive pairs is the clean, production-ready solution most candidates are evaluated on.