The O(n) Club: Roman to Integer — Why Does ‘IX’ Always Betray Me?

The O(n) Club: Roman to Integer — Why Does ‘IX’ Always Betray Me?

⚡ TL;DR

Roman numerals aren’t just fancy birthday cake icing—they come with rules that can trip up even the smartest dev. If you just add up the letter values, ‘IX’ will bite you (outputting 11 instead of 9). The trick? Subtract when a smaller value comes before a bigger one. Here’s what not to do in Java:

// Sad trombone version:
int total = 0;
for (char c : s.toCharArray()) {
    total += map.get(c); // This gives you 'IV' == 6. Yikes.
}

🧠 How Devs Usually Mess This Up

Classic mistake? Devs treat every character like it’s just another cookie to toss in the jar: sum, sum, sum. But then comes a subtraction pair like ‘IV’ or ‘XC’ to flip your code upside down. Forgetting subtraction means your solution’s as reliable as a flip-flop in a snowstorm. And yes, only certain pairs can subtract—the Romans were picky like that.

🔍 What’s Actually Going On

Reading Roman numerals is like interpreting a soap opera from 2000 years ago. Normally, you just add values together. But if the drama builds—a smaller numeral struts before a bigger one—subtract it instead (e.g. ‘I’ before ‘V’ is 5-1=4, not 5+1=6). Only these troublemaker combos trigger subtraction: I before V/X, X before L/C, C before D/M. Everything else? Chuck it in the total.

🛠️ PseudoCode

• Make a lookup map: Match each Roman char to its value.
  

  Map<Character, Integer> map = Map.of('I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000);

• Walk left to right: For each letter, peek at the next. If the current is smaller, subtract it. Otherwise, add.
  

  for (int i = 0; i < s.length(); i++) {
    int curr = map.get(s.charAt(i));
    int next = (i + 1 < s.length()) ? map.get(s.charAt(i + 1)) : 0;
    if (curr < next) total -= curr;
    else total += curr;
  }

• Drop the total at the end and grab a coffee.

💻 The Code

public int romanToInt(String s) {
    Map<Character, Integer> map = new HashMap<>();
    map.put('I', 1);
    map.put('V', 5);
    map.put('X', 10);
    map.put('L', 50);
    map.put('C', 100);
    map.put('D', 500);
    map.put('M', 1000);
     int total = 0;
    for (int i = 0; i < s.length(); i++) {
        int curr = map.get(s.charAt(i));
        int next = (i + 1 < s.length()) ? map.get(s.charAt(i + 1)) : 0;
        if (curr < next) {
            total -= curr;
        } else {
            total += curr;
        }
    }
    return total;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Fake combos: ‘IC’, ‘IL’—if this sneaks into your data, your code will just smile and sum it. Roman emperors would not approve.
• Edge weirdness: If the string starts or ends with a subtraction pair (‘IX’, ‘XC’), double check you’re not off by one.
• Efficiency high-five: One pass (O(n)), and your only “extra” memory is the fixed symbol map. Your CPU will thank you.

🧠 Interviewer Brain-Tattoo

“If you ignore order in Roman numerals, you’ll get comedy—not arithmetic.”