Roman to Integer - LeetCode 13 Solution

Problem Overview

#

The Roman to Integer problem from LeetCode asks you to convert a Roman numeral string to an integer.

Problem Statement: Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Given a roman numeral, convert it to an integer.

Symbol Values:

• I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000

Example:

• Input: s = "III"

• Output: 3

• Input: s = "LVIII"

• Output: 58 (50 + 5 + 3)

• Input: s = "MCMXCIV"

• Output: 1994 (1000 + 900 + 90 + 4)

Solution Approach

#

C# Solution - Single Pass with Dictionary

#

Create a Dictionary mapping each Roman numeral symbol to its integer value. Iterate through the string once, tracking the previous value. When the current value is greater than the previous value, it means subtraction should apply (like IV or IX), so subtract twice the previous value. Otherwise, simply add the current value to the total.

public class Solution {
    public int RomanToInt(string s) {
        var romanMap = new Dictionary<char, int> {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

        var total = 0;
        var prevVal = 0;

        foreach(var c in s) {
            var currentVal = romanMap[c];
            if( prevVal < currentVal) {
                total += currentVal - (2 * prevVal);
            }else {
                total += currentVal;
            }
            prevVal = currentVal;
        }

        return total;
    }
}

Time Complexity: O(n) - single pass through the string Space Complexity: O(1) - dictionary has at most 7 entries (constant size)

Key Insights

#

1. Dictionary Mapping: Store all seven Roman symbols with their values for O(1) lookup
2. Subtraction Detection: When current value > previous value, a subtraction case occurs (e.g., IV, IX)
3. Smart Adjustment: Subtract twice the previous value instead of complex subtraction logic
4. Left to Right Processing: Process characters sequentially, comparing with previous value only
5. Common Patterns: IV (4), IX (9), XL (40), XC (90), CD (400), CM (900) are handled automatically
6. Single Pass Efficiency: Only one iteration through the string needed

Related Problems

#

• Integer to Roman
• Valid Parentheses
• Evaluate Reverse Polish Notation

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.