Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Roman to Integer | Leetcode 13 | Mapping and Subtraction Rule Solution
    Data Structures & Algorithms

    Roman to Integer | Leetcode 13 | Mapping and Subtraction Rule Solution

    codeanddebugBy codeanddebug1 September 2025No Comments3 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve Roman to Integer
    Share
    Facebook Twitter LinkedIn Pinterest Email

    The Roman to Integer problem asks us to convert a given Roman numeral string into its corresponding integer value.

    • Roman numerals are represented using seven symbols:
      • I = 1
      • V = 5
      • X = 10
      • L = 50
      • C = 100
      • D = 500
      • M = 1000
    • Numbers are formed by combining these symbols and adding their values.
    • However, when a smaller value comes before a larger value, it is subtracted instead of added.

    Here’s the [Problem Link] to begin with.


    Examples

    Example 1

    Input: s = "III"
    Output: 3
    Explanation: 1 + 1 + 1 = 3

    Example 2

    Input: s = "LVIII"
    Output: 58
    Explanation: L = 50, V = 5, III = 3 → 50 + 5 + 3 = 58

    Example 3

    Input: s = "MCMXCIV"
    Output: 1994
    Explanation: 
    M = 1000, CM = 900, XC = 90, IV = 4 → 1000 + 900 + 90 + 4 = 1994

    Intuition and Approach

    To solve the Roman to Integer problem, we need to carefully apply Roman numeral rules:

    1. Mapping values:
      • Create a dictionary that maps Roman numerals to their integer values.
    2. Traverse the string:
      • For each character, check if its value is less than the next character’s value.
      • If yes → subtract the value (subtractive case, e.g., IV = 4).
      • If no → add the value to the total.
    3. Return total:
      • After processing all characters, the accumulated total is the integer equivalent.

    This approach works because Roman numerals follow a consistent additive and subtractive rule.


    Code Implementation

    class Solution:
        def romanToInt(self, s: str) -> int:
            # Mapping Roman numerals to their values
            roman_map = {
                "I": 1,
                "V": 5,
                "X": 10,
                "L": 50,
                "C": 100,
                "D": 500,
                "M": 1000
            }
            
            total = 0
            n = len(s)
            
            for i in range(n):
                # If current value is less than the next one, subtract it
                if i + 1 < n and roman_map[s[i]] < roman_map[s[i + 1]]:
                    total -= roman_map[s[i]]
                else:
                    total += roman_map[s[i]]
            
            return total

    Code Explanation

    • Mapping: roman_map assigns values to Roman symbols.
    • Loop through string:
      • If the current numeral is smaller than the next, subtract it (IV → -1 + 5 = 4).
      • Otherwise, add it normally (VI → 5 + 1 = 6).
    • Result: The accumulated total gives the integer equivalent.

    Dry Run

    Input: s = "MCMXCIV"

    • M = 1000 → total = 1000
    • C < M → subtract 100 → total = 900
    • M = 1000 → total = 1900
    • X < C → subtract 10 → total = 1890
    • C = 100 → total = 1990
    • I < V → subtract 1 → total = 1989
    • V = 5 → total = 1994

    Output: 1994


    Time and Space Complexity

    • Time Complexity:
      • Traverse string once → O(N), where N is length of s.
    • Space Complexity:
      • Dictionary of fixed size (7 elements) → O(1).

    Conclusion

    The Roman to Integer problem is solved using a mapping dictionary and the subtraction rule.

    • Add values normally unless a smaller numeral precedes a larger one, in which case subtract.
    • Runs in O(N) time with O(1) space.
    • Efficient and widely used approach for converting Roman numerals to integers.

    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Medium Strings
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleMaximum Nesting Depth of the Parentheses | Leetcode 1614 | Depth Counting Solution
    Next Article Implement Trie (Prefix Tree) | Leetcode 208 | Efficient String Data Structure
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Count Distinct Substrings – Brute Force and Trie Approaches

    1 September 2025
    Data Structures & Algorithms

    Complete String – Trie Based Solution

    1 September 2025
    Data Structures & Algorithms

    Implement Trie ll | Full Trie with Insert, Count, and Erase

    1 September 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (235)
      • Beginner (81)
      • Expert (51)
      • Intermediate (103)
    • Uncategorised (1)
    Recent Posts

    Count Distinct Substrings – Brute Force and Trie Approaches

    1 September 2025

    Complete String – Trie Based Solution

    1 September 2025

    Implement Trie ll | Full Trie with Insert, Count, and Erase

    1 September 2025

    Implement Trie (Prefix Tree) | Leetcode 208 | Efficient String Data Structure

    1 September 2025

    Roman to Integer | Leetcode 13 | Mapping and Subtraction Rule Solution

    1 September 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.