Solving the ‘Roman to Integer’ Problem on LeetCode — Python Solutions Walkthrough

Image Source

Introduction

Converting Roman numerals to integers is a classic challenge frequently encountered in programming interviews and competitive coding. This article provides a detailed walkthrough of three distinct Python solutions to tackle the ‘Roman to Integer’ problem on LeetCode. Each method offers unique insights into effective problem-solving strategies in Python. By the end of this guide, you will have a thorough understanding of the mechanics behind each approach, as well as their efficiency and effectiveness. Detailed comments and step-by-step explanations for each method are provided after the conclusion, helping you grasp the practical implementation and nuances of these solutions.

Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M, with respective values of 1, 5, 10, 50, 100, 500, and 1000. Given a roman numeral, the task is to convert it to an integer.

Function Signature in Python:

def romanToInt(self, s):

Examples:

• Input: s = “III”, Output: 3
• Input: s = “LVIII”, Output: 58
• Input: s = “MCMXCIV”, Output: 1994

Solution 1: Iterative Approach

This basic method iterates through the string from left to right, summing the values of the Roman numerals. If a numeral of smaller value precedes a larger value, the smaller value is subtracted.

Python Code:

class Solution(object):
     def romanToInt(self, s):
        sum = 0
        prevValue = 0
        value = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        
        for c in s:
            currentValue = value[c]
            sum += (currentValue - 2 * prevValue) if (currentValue > prevValue) else currentValue
            prevValue = currentValue
        return sum

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the input string. This complexity arises because the algorithm loops through each character in the string exactly once. Each iteration involves a direct lookup in a dictionary (value) and a couple of arithmetic operations, which are both constant time operations O(1). Thus, the time complexity remains linear relative to the length of the string.
• Space Complexity: O(1), because aside from the storage used for the input and a few auxiliary variables (sum, prevValue, and the small fixed-size dictionary for the Roman numeral values), no additional space that scales with the input size is used. The dictionary does not grow with the size of the input string since the number of Roman numeral symbols is constant and limited to seven.

Solution 2: Direct Mapping with Array

Optimized by using an array for fast lookup, this method minimizes the overhead seen in hash map operations.

Python Code:

class Solution(object):
     def romanToInt(self, s):
        sum = 0
        prevValue = 0
        values = [0] * 256
        values[ord('I')] = 1; values[ord('V')] = 5; values[ord('X')] = 10; values[ord('L')] = 50
        values[ord('C')] = 100; values[ord('D')] = 500; values[ord('M')] = 1000
        
        for c in s:
            currentValue = values[ord(c)]
            sum += (currentValue - 2 * prevValue) if (currentValue > prevValue) else currentValue
            prevValue = currentValue
        return sum

Time and Space Complexity

• Time Complexity: O(n), as it involves a single pass through the string. Each character of the string is accessed once, and its corresponding integer value is retrieved from a pre-filled array based on the character’s ASCII value. This retrieval is a constant time operation, and the subsequent arithmetic operations (comparison, addition, and subtraction) performed during each iteration are also executed in constant time.
• Space Complexity: O(1), it uses a fixed-size array of 256 integers (assuming extended ASCII character set for generality). The size of this array does not depend on the input size but is fixed regardless of the input string’s length. No additional space that scales with the size of the input is used, hence the constant space complexity.

Solution 3: Using Dictionary for Flexibility

This solution uses a Python dictionary which provides a balance between readability and performance.

Python Code:

class Solution(object):
     def romanToInt(self, s):
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        sum = 0
        prevValue = roman[s[0]]
        
        for i in range(1, len(s)):
            currentValue = roman[s[i]]
            sum += -prevValue if (currentValue > prevValue) else prevValue
            prevValue = currentValue
        sum += prevValue
        return sum

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string. Although dictionaries generally offer average constant time complexity for insertions and lookups, in this context, the dictionary is pre-filled with only seven key-value pairs (corresponding to the Roman numerals), and lookups therefore approximate constant time due to the limited size. The loop processes each character of the string exactly once, performing operations similar to the previous solutions.
• Space Complexity: O(1), the dictionary used to store the Roman numeral mappings is constant in size regardless of the input string length, as it contains only seven entries. The additional variables for computing the sum and storing previous values are minimal and do not increase with the size of the input.

Conclusion and Comparison

Upon reviewing the three Python methods to solve the ‘Roman to Integer’ problem, it’s clear that all exhibit similar time complexities, as each method processes the input string in a single traversal. The space complexity remains low across all approaches, thanks to minimal use of auxiliary storage and in some cases, data structures that efficiently map numeral values.

Solution 1: Iterative Approach with Dictionary This approach utilizes a dictionary for mapping Roman numerals to their corresponding integer values. The method is simple and direct, making the code easy to understand and follow. The dictionary provides an effective way to manage numeral-to-value conversions, although at times, the simplicity could obscure the flow of calculations. It’s well-suited for those seeking a straightforward solution with clear code structure.

Solution 2: Direct Mapping with Array By embedding the numeral-to-integer mapping within an array, this solution offers a slight performance boost by reducing the overhead typically associated with more complex data structures like dictionaries. This method is highly efficient but might face challenges with maintainability or scalability should there be changes to the numeral system, as any modification requires adjustments directly within the array’s initialization.

Solution 3: Using Dictionary for Flexibility Standing out for its readability and maintainability, this approach employs a dictionary to separate the storage of numeral mappings from the logic of the computation. This separation aids in understanding and modifying the code, making it adaptable to future changes or enhancements. The dictionary approach here not only keeps the code clean but also allows for more dynamic handling of numeral mappings, providing an elegant solution to potential extensions or adaptations.

While the Direct Mapping with Array approach focuses on performance and Iterative Approach on structural clarity, Using Dictionary for Flexibility approach strikes an optimal balance between readability, maintainability, and the ability to adapt. This reflects a preferred approach in modern Python programming, where the flexibility and clarity of a dictionary can significantly enhance code quality and future-proofing.

• LeetCode — Roman to Integer
• Python Documentation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated and helps keep content like this free!

Also check out my other Leetcode Walkthrough Lists:

• Two Sum Problem
• Palindrome Number Problem

Commented Code and Step-by-Step Explanations

Solution 1: Iterative Approach

This method utilizes a dictionary to map Roman numerals to integers, allowing for quick value retrieval. By iterating from left to right across the string, it checks and compares each numeral with its predecessor to decide whether to add or subtract its value. This straightforward logic directly applies Roman numeral rules such as subtracting a smaller numeral that precedes a larger one. The dictionary ensures that these lookups are efficient, providing O(1) access time for each numeral, making the solution simple yet effective.

Python Code:

class Solution(object):
    def romanToInt(self, s):
        sum = 0  # Initialize the total sum
        prevValue = 0  # Initialize the value of the previous Roman numeral
        value = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        
        for c in s:
            currentValue = value[c]
            # If the current value is greater than the previous value, subtract twice the previous value
            # Otherwise, add the current value to the sum
            sum += (currentValue - 2 * prevValue) if (currentValue > prevValue) else currentValue
            prevValue = currentValue  # Update the previous value for the next iteration
        return sum  # Return the computed total

Step-by-Step Explanation

• Step 1: Initialize the total sum (sum) and the value of the previous Roman numeral (prevValue) to 0.
• Step 2: Iterate through each character (c) in the input Roman string (s).
• Step 3: Retrieve the integer value of the current Roman numeral (currentValue) from the dictionary.
• Step 4: Check if the current value is greater than the previous value. If true, subtract twice the previous value from the current value and add the result to the sum. Otherwise, add the current value to the sum.
• Step 5: Update prevValue with the current value for the next iteration.
• Step 6: Return the final sum as the result.

Solution 2: Direct Mapping with Array

The direct mapping approach uses an array where the indices represent ASCII values of characters, allowing each Roman numeral’s integer value to be accessed instantly. This setup enhances performance by utilizing the constant time access of arrays, reducing overhead compared to more dynamic data structures. While highly efficient, this method’s static nature means that any modification to the numeral system would require changes to the array initialization, limiting its flexibility.

Python Code:

class Solution(object):
    def romanToInt(self, s):
        sum = 0  # Initialize the total sum
        prevValue = 0  # Initialize the value of the previous Roman numeral
        values = [0] * 256  # All initialized to zero
        values[ord('I')] = 1; values[ord('V')] = 5; values[ord('X')] = 10
        values[ord('L')] = 50; values[ord('C')] = 100; values[ord('D')] = 500; values[ord('M')] = 1000
        
        for c in s:
            currentValue = values[ord(c)]
            # If the current value is greater than the previous value, subtract twice the previous value
            # Otherwise, add the current value to the sum
            sum += (currentValue - 2 * prevValue) if (currentValue > prevValue) else currentValue
            prevValue = currentValue  # Update the previous value for the next iteration
        return sum  # Return the computed total

Step-by-Step Explanation

• Step 1: Initialize the total sum (sum) and the value of the previous Roman numeral (prevValue) to 0.
• Step 2: Iterate through each character (c) in the input string, using the array to directly map each Roman numeral character to its integer value (currentValue).
• Step 3: Check if the current value is greater than the previous value. If true, subtract twice the previous value; otherwise, add the current value to the sum.
• Step 4: Update prevValue with the current value for the next iteration.
• Step 5: Return the computed total (sum).

Solution 3: Using Dictionary for Flexibility

This solution prioritizes maintainability and adaptability by using a dictionary to separate numeral mappings from the calculation logic. It handles numerals by checking if the current numeral’s value is greater than the previous one to adjust the total sum accordingly. This separation allows for easy updates and clear understanding, making the code not only efficient but also highly adaptable to changes or extensions in the numeral system.

Python Code:

class Solution(object):
    def romanToInt(self, s):
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        sum = 0  # Initialize the total sum
        prevValue = roman[s[0]]  # Initialize the value of the first Roman numeral
        
        for i in range(1, len(s)):
            currentValue = roman[s[i]]
            # If the current value is greater than the previous value, subtract the previous value
            # Otherwise, add the previous value
            sum += -prevValue if (currentValue > prevValue) else prevValue
            prevValue = currentValue  # Update the previous value for the next iteration
        sum += prevValue  # Add the last value to sum
        return sum  # Return the computed total

Step-by-Step Explanation

• Step 1: Create a dictionary (roman) to store the mappings of Roman numerals to their integer values.
• Step 2: Populate the dictionary with mappings for each Roman numeral character.
• Step 3: Initialize the total sum (sum) and the value of the first Roman numeral (prevValue) to the value of the first character in the string.
• Step 4: Iterate through each subsequent character (c) in the input string (s).
• Step 5: Look up the integer value of the current Roman numeral in the dictionary (currentValue).
• Step 6: Check if the current value is greater than the previous value. If true, subtract the previous value; otherwise, add the previous value.
• Step 7: Update prevValue with the current value for the next iteration.
• Step 8: Add the last value of prevValue to sum.
• Step 9: Return the computed total (sum).