LeetSolved

Find solutions to all LeetCode problems here.

13.

Roman to Integer

Easy

Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Examples

Input: III
Output: 3

Input: IV
Output: 4

Constraints

Approach to Solve

Use a greedy algorithm to convert the Roman numeral to integer.

Code Implementation

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_int = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        total = 0
        prev_value = 0
        for char in reversed(s):
            value = roman_to_int[char]
            if value < prev_value:
                total -= value
            else:
                total += value
            prev_value = value
        return total

Explanation

The Roman to Integer problem is solved using a greedy algorithm. Here's a detailed explanation of the approach:

  1. We start by creating a mapping of Roman numeral symbols to their corresponding integer values. This is typically done using a hash map or dictionary for constant-time lookups.

  2. We initialize two variables:

    • 'total' to keep track of the final integer value
    • 'prevValue' to store the value of the previous Roman numeral symbol
  3. We iterate through the input string from right to left. This is crucial because in Roman numerals, the order of symbols determines whether we add or subtract their values.

  4. For each symbol: a. We get its integer value from our mapping. b. We compare this value with the previous value:

    • If the current value is less than the previous value, we subtract it from the total. This handles cases like 'IV' (4) or 'CM' (900).
    • Otherwise, we add it to the total. c. We update 'prevValue' for the next iteration.
  5. After processing all symbols, we return the total.

This approach works because of how Roman numerals are structured:

  • Normally, symbols are arranged from largest to smallest, left to right (e.g., 'XVI' = 16).
  • When a smaller value appears before a larger value, it represents subtraction (e.g., 'IV' = 4).

By iterating from right to left and comparing each value with the previous one, we can correctly handle both standard cases and subtractive cases.

Time Complexity: O(n), where n is the length of the input string. We iterate through each character once. Space Complexity: O(1), as we use a fixed-size hash map and a constant amount of extra space, regardless of the input size.

This solution is optimal as it processes the input in a single pass and uses constant extra space, making it both time and space efficient for the given constraints.

Complexity

  • Time Complexity: O(n)
  • Space Complexity: O(1)
Code copied to clipboard!