Roman to Integer

• Difficulty: Easy
• Topics: Hash Table, Math, String
• Link: https://leetcode.com/problems/roman-to-integer/

Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

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

Example 3:

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

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Solution

1. Problem Deconstruction

Technical Restatement

Given a string s composed exclusively of the Roman numeral symbols {'I', 'V', 'X', 'L', 'C', 'D', 'M'}, convert it to its integer equivalent. The conversion must account for additive and subtractive notation rules:

• Additive: Symbols are summed when values decrease or remain equal left-to-right (e.g., III = 1+1+1 = 3).
• Subtractive: A smaller symbol preceding a larger one denotes subtraction (e.g., IV = 5 - 1 = 4). Valid subtractive pairs are (IV, IX), (XL, XC), (CD, CM).

Beginner-Friendly Explanation

Imagine reading a Roman numeral from left to right. Normally, you add up the values of each symbol. But if you see a smaller symbol followed by a larger one (like I before V), you subtract the smaller one instead of adding it. Your goal is to write a program that does this conversion automatically.

Mathematical Formulation

Let $s$ be a string of length $n$, and $v(c)$ map a symbol $c$ to its integer value. Define the integer result $R$ as:

$$R = \sum_{i=0}^{n-2} \left\{ \begin{array}{ll} -v(s_i) & \text{if } v(s_i) < v(s_{i+1}) \\ +v(s_i) & \text{otherwise} \end{array} \right. + v(s_{n-1})$$

Constraint Analysis

• Length (1–15): Allows brute-force checking of all symbol pairs. No algorithmic optimization needed.
• Valid characters: Input sanitization unnecessary. Symbols are guaranteed valid.
• Range (1–3999): Output fits in a standard integer. No overflow concerns.
• Guaranteed validity: No need to handle invalid sequences like IIV or VV.

---

2. Intuition Scaffolding

Analogies

1. Real-World Metaphor: Like reading a price tag with discounts. Base prices are added, but a “less than” sign before a higher value applies a discount (subtraction).
2. Gaming Analogy: In a RPG, combining potions: drinking a small potion before a large one might weaken it (subtraction), but drinking in order of increasing strength enhances it (addition).
3. Math Analogy: Similar to evaluating a sequence where operators (add/subtract) are determined by comparing adjacent elements.

Common Pitfalls

1. Right-to-Left Processing: While possible, it adds unnecessary complexity.
2. Overhandling Subtractions: Checking for invalid pairs (e.g., IC) is redundant due to validity guarantee.
3. Global Lookup Tables: Hardcoding values for multi-character sequences (e.g., CM=900) is less efficient than pairwise comparison.
4. Ignoring Last Symbol: Forgetting to add the final value after the loop.
5. Misindexing: Off-by-one errors when processing the last symbol.

---

3. Approach Encyclopedia

Brute Force (Pairwise Comparison)

• Logic: Iterate left-to-right, comparing each symbol with the next. Subtract if smaller, else add. Finally, add the last symbol.
• Pseudocode:

  map = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
  total = 0
  for i from 0 to len(s)-2:
      if map[s[i]] < map[s[i+1]]:
          total -= map[s[i]]
      else:
          total += map[s[i]]
  total += map[s[-1]]
  return total
  

• Complexity: Time: $O(n)$ (each symbol processed once). Space: $O(1)$ (fixed symbol map).
• Visualization:

  "MCMXCIV" (n=7):
  Step: 0 | Symbol: M (1000) | Next: C (100) | 1000 >= 100 → Add 1000 → total=1000
  Step: 1 | Symbol: C (100) | Next: M (1000) | 100 < 1000 → Subtract 100 → total=900
  Step: 2 | Symbol: M (1000) | Next: X (10) | 1000 >= 10 → Add 1000 → total=1900
  Step: 3 | Symbol: X (10) | Next: C (100) | 10 < 100 → Subtract 10 → total=1890
  Step: 4 | Symbol: C (100) | Next: I (1) | 100 >= 1 → Add 100 → total=1990
  Step: 5 | Symbol: I (1) | Next: V (5) | 1 < 5 → Subtract 1 → total=1989
  Add last: V (5) → total=1994
  

Alternative (Right-to-Left)

• Logic: Process from right to left, adding values. If a symbol is smaller than the previous one, subtract it.
• Why Worse: Less intuitive and requires storing the previous symbol.

---

4. Code Deep Dive

def romanToInt(s: str) -> int:
    roman = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    total = 0
    n = len(s)
    for i in range(n-1):
        if roman[s[i]] < roman[s[i+1]]:
            total -= roman[s[i]]
        else:
            total += roman[s[i]]
    total += roman[s[-1]]
    return total

Line-by-Line Analysis

1. Symbol Map: roman dictionary provides O(1) symbol value lookup.
2. Initialization: total accumulates the result.
3. Loop: Processes indices 0 to n-2 (second-to-last symbol).
4. Comparison: Checks if current symbol is smaller than the next. Subtracts if true, adds otherwise.
5. Final Symbol: Adds the last symbol unconditionally (no subsequent symbol to trigger subtraction).

Edge Case Handling

• Single Symbol: Loop skipped; last symbol added directly (e.g., "V" → 5).
• All Additive: Example "III" adds all Is.
• All Subtractive: Example "IV" subtracts I then adds V.

---

5. Complexity War Room

Hardware-Aware Analysis

• Time: $O(n)$ with $n \leq 15$. Negligible even on constrained devices.
• Space: $O(1)$ fixed-size map. Uses ~200 bytes, fitting in L1 cache.

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Left-to-Right	O(n)	O(1)	10/10	✅ Ideal
Right-to-Left	O(n)	O(1)	7/10	⚠️ Acceptable
Hardcoded Groups	O(n)	O(1)	6/10	❌ Overcomplicated

---

6. Pro Mode Extras

Variants

• Multiple Transactions: If asked to handle Roman numerals with arbitrary subtractive pairs (beyond standard six), the pairwise approach still works.
• Invalid Input Handling: Remove validity guarantee—add checks for invalid subtractive pairs (e.g., VX).

Interview Cheat Sheet

• Mention: “This is a linear scan with constant space, optimal for the constraints.”
• Watch For: Off-by-one errors on the last symbol.
• Test Cases: Include "IV" (4), "IX" (9), "XL" (40), "XC" (90), "CD" (400), "CM" (900).