Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    0013 - Roman to Integer
    0013 - Roman to Integer

    0013 - Roman to Integer

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/roman-to-integer/

    Solution 1 - Hash Map with Subtraction Rule

    Iterate through the string character by character. For each pair of adjacent characters, if the current value is less than the next value, subtract it (handles cases like IV = 4, IX = 9). Otherwise, add it. Finally, add the last character's value.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Right-to-Left Traversal

    Traverse the string from right to left. If the current character's value is less than the previous character's value (the one to its right), subtract it. Otherwise, add it. This naturally handles the subtraction rule without needing to look ahead.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0013.1 - Roman to Integer - Solution 1 - Hash Map with Subtraction Rule """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def romanToInt(self, s: str) -> int:
        """Roman to Integer Function"""
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        ans = 0

        for a, b in zip(s, s[1:]):
            if roman[a] < roman[b]:
                ans -= roman[a]
            else:
                ans += roman[a]

        return ans + roman[s[-1]]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().romanToInt("III"))       # 3
    print(Solution().romanToInt("LVIII"))     # 58
    print(Solution().romanToInt("MCMXCIV"))   # 1994


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0013.2 - Roman to Integer - Solution 2 - Right-to-Left Traversal """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def romanToInt(self, s: str) -> int:
        """Roman to Integer Function"""
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        ans = 0
        prev = 0

        for ch in reversed(s):
            curr = roman[ch]
            if curr < prev:
                ans -= curr
            else:
                ans += curr
            prev = curr

        return ans


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().romanToInt("III"))       # 3
    print(Solution().romanToInt("LVIII"))     # 58
    print(Solution().romanToInt("MCMXCIV"))   # 1994


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()