Leetcode 13: Roman to Integer

Hash table; String as iterable

Problem description

Crucial tricks to solution

• Left-to-right iteration through input string: Problem description “Roman numerals are usually written largest to smallest from left to right” tells us that a normal iteration from left to right on the input string is proper for the problem
• Mathematical rules: We ultimately can distill Roman numeral rules into two scenarios:

1. Subtraction: Subtraction is only used when a numeral of greater value immediately follows a numeral. Examples include IV (4), IX (9), XL (40), XC (90), CD (400), and CM (900)
2. Addition: Otherwise, because Roman numerals are typically written in descending order from left to right, the suitable operation is to process characters one by one sequentially and add the corresponding values together

Efficiency considerations

The O(n) time complexity required for iterating through the input string is inevitable (where n is the length of the string), but the mapping between individual characters and numbers could be constant time by using a hash table.

Careful with subtraction

When combining the left-to-right iteration and the above-mentioned mathematical rules, we must be careful about subtraction operations. Let’s use IV (4) as an example:

1. When we start the iteration, we encounter “I” for the first time. Without knowing anything else, we apply addition, which gives us 1
2. Next, we move on to “V”. Now we realize the corresponding number is larger than the previous value. But because we have already added 1 in step 1, only adding V(5) — I(1) = 4 to the sum would still leave an extra 1. Therefore, we must subtract I(1) from the sum again

By denoting preceding value as prev , the current numeral value as current, and the cumulative sum as total , we get:

if prev >= current:
    total += current
else:
    # NOTE: We need to subtract `prev` twice to compensate for the previous
    #   addition when first encountering the character
    total += ((current - prev) - prev)

Python solution

Putting these together, we get the following solution:

class Solution:
    def romanToInt(self, s: str) -> int:
        mapping_char_to_int = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

        # For a valid roman numeral input `s` (guaranteed in description)
        # There are only two mathematical operations to consider
        # e.g., for any consecutive numeral pairs `ab`:
        # 1. When mapping_char_to_int[a] <  mapping_char_to_int[b]
        #   int = mapping_char_to_int[b] - mapping_char_to_int[a]
        # 2. When mapping_char_to_int[a] >= mapping_char_to_int[b]
        #   int = mapping_char_to_int[a] + mapping_char_to_int[b]

        total = 0

        # `prev` keeps track of proceeding character
        #   relative to current character
        # Before starting the iteration, initialize `prev` with None
        prev = None

        for char in s:
            current = mapping_char_to_int[char]
            # Applies addition when:
            #   1. At the onset of iteration
            #   2. When proceeding character's value no less than current value
            if not prev or prev >= current:
                total += current
            # When proceeding character's value is less than current value
            #   Add the corresponding value (current - prev)
            #   then subtract prev again to compensate for previous addition
            else:
                total += (current - prev) - prev

            prev = current

        return total

Space and time complexity

With n denoting input string length,

• Space complexity: O(1) — We only use constant space variables such as prev, current, and total. The space required for the input is already provided and thus not accounted for.
• Time complexity: O(n) — We must iterate through the input string once. The hash table look-up is constant time (O(1)). Collectively, the overall time complexity is O(n)

Example unit test (pytest)

import pytest


def test_basic_cases():
    solution = Solution()
    assert solution.romanToInt("III") == 3
    assert solution.romanToInt("IV") == 4
    assert solution.romanToInt("IX") == 9


def test_edge_cases():
    solution = Solution()
    assert solution.romanToInt("I") == 1
    assert solution.romanToInt("MM") == 2000


def test_invalid_input():
    solution = Solution()
    with pytest.raises(KeyError):
        solution.romanToInt("A")
    with pytest.raises(KeyError):
        solution.romanToInt("XY")