DSA 450 Notes

Problem Statement

Given a Roman numeral string, convert it to its decimal (integer) equivalent.

Roman Numeral Values:

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

Special Rules (Subtraction):

I before V (5) or X (10) → subtract I (e.g., IV = 4, IX = 9)
X before L (50) or C (100) → subtract X (e.g., XL = 40, XC = 90)
C before D (500) or M (1000) → subtract C (e.g., CD = 400, CM = 900)

Example:

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

Approach 1: Check Each Pair

Intuition

Process two characters at a time. If the current pair forms a subtraction pattern (like IV, IX), handle it specially; otherwise, add the current character's value.

Algorithm

Create a mapping of Roman numerals to values
Create a mapping for two-character subtraction patterns
Iterate through the string
If current position forms a two-char pattern, add its value and skip next
Otherwise, add single character value
Return total sum

java

import java.util.*;

public class Solution {
    public int romanToDecimal(String s) {
        Map<Character, Integer> single = new HashMap<>();
        single.put('I', 1); single.put('V', 5);
        single.put('X', 10); single.put('L', 50);
        single.put('C', 100); single.put('D', 500);
        single.put('M', 1000);
        
        Map<String, Integer> pairs = new HashMap<>();
        pairs.put("IV", 4); pairs.put("IX", 9);
        pairs.put("XL", 40); pairs.put("XC", 90);
        pairs.put("CD", 400); pairs.put("CM", 900);
        
        int result = 0;
        int i = 0;
        int n = s.length();
        
        while (i < n) {
            // Check for two-character pattern
            if (i + 1 < n) {
                String twoChar = s.substring(i, i + 2);
                if (pairs.containsKey(twoChar)) {
                    result += pairs.get(twoChar);
                    i += 2;
                    continue;
                }
            }
            
            // Single character
            result += single.get(s.charAt(i));
            i++;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through the string
Space Complexity: O(1) - Fixed-size maps

Approach 2: Compare with Next (Optimal)

Intuition

If a smaller value appears before a larger value, we subtract it; otherwise, we add it. This eliminates the need for a separate pairs map.

Algorithm

Create mapping of Roman numerals to values
Iterate through the string
If current value < next value, subtract current from result
Otherwise, add current to result
Return final result

java

import java.util.*;

public class Solution {
    public int romanToDecimal(String s) {
        Map<Character, Integer> values = new HashMap<>();
        values.put('I', 1); values.put('V', 5);
        values.put('X', 10); values.put('L', 50);
        values.put('C', 100); values.put('D', 500);
        values.put('M', 1000);
        
        int result = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            int current = values.get(s.charAt(i));
            int next = (i + 1 < n) ? values.get(s.charAt(i + 1)) : 0;
            
            if (current < next) {
                result -= current;  // Subtraction case
            } else {
                result += current;  // Addition case
            }
        }
        
        return result;
    }
}

Dry Run Example

Input: "MCMXCIV"

Position 0: M(1000), next=C(100), 1000 > 100, ADD 1000, result = 1000
Position 1: C(100), next=M(1000), 100 < 1000, SUBTRACT 100, result = 900
Position 2: M(1000), next=X(10), 1000 > 10, ADD 1000, result = 1900
Position 3: X(10), next=C(100), 10 < 100, SUBTRACT 10, result = 1890
Position 4: C(100), next=I(1), 100 > 1, ADD 100, result = 1990
Position 5: I(1), next=V(5), 1 < 5, SUBTRACT 1, result = 1989
Position 6: V(5), next=0, 5 > 0, ADD 5, result = 1994

Output: 1994

Complexity Analysis

Time Complexity: O(n) - Single pass
Space Complexity: O(1) - Fixed-size map

Approach 3: Right to Left Traversal

Intuition

Process from right to left. If current value is less than the previous maximum value seen, subtract it; otherwise, add it and update max.

java

import java.util.*;

public class Solution {
    public int romanToDecimalRTL(String s) {
        Map<Character, Integer> values = new HashMap<>();
        values.put('I', 1); values.put('V', 5);
        values.put('X', 10); values.put('L', 50);
        values.put('C', 100); values.put('D', 500);
        values.put('M', 1000);
        
        int result = 0;
        int maxSoFar = 0;
        
        // Process right to left
        for (int i = s.length() - 1; i >= 0; i--) {
            int current = values.get(s.charAt(i));
            
            if (current < maxSoFar) {
                result -= current;
            } else {
                result += current;
                maxSoFar = current;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

Key Takeaways

Pattern recognition: Subtraction happens when a smaller numeral precedes a larger one
Compare with next is cleaner than checking all special cases explicitly
Right-to-left traversal with max tracking is an elegant alternative
All approaches are O(n) - the difference is in code clarity
This is a common interview question testing attention to edge cases
The reverse problem (integer to Roman) is also frequently asked

Converting Roman Numerals to Decimal

Problem Statement

Approach 1: Check Each Pair

Intuition

Algorithm

Complexity Analysis

Approach 2: Compare with Next (Optimal)

Intuition

Algorithm

Dry Run Example

Complexity Analysis

Approach 3: Right to Left Traversal

Intuition

Complexity Analysis

Key Takeaways