This document illustrates the execution of three solutions for the "Roman to Integer" problem (LeetCode 13) using the valid Roman numeral string "MCMXCIV" (1994). The solutions are:
- First Pass: Naive addition of each symbol’s value.
- Second Pass: Compare adjacent symbols to handle subtractive cases.
- Final Solution: Single-pass addition with correction for subtractive cases.
Each solution is visualized with a Mermaid sequence diagram showing the step-by-step processing of "MCMXCIV". A flowchart for the Final Solution’s logic is also included, with notes on how it differs for the other solutions.
The following flowchart represents the Final Solution’s logic, which is the most optimized. The First Pass skips the subtractive check, and the Second Pass handles the last character separately but follows a similar structure.
graph TD
A[Start] --> B[Initialize map: I=1, V=5, X=10, L=50, C=100, D=500, M=1000]
B --> C[Initialize result = 0, prev = 0]
C --> D[For each character in string]
D --> E[Get curr from map for char]
E --> F[Add curr to result]
F --> G{prev < curr?}
G -->|Yes| H[Subtract 2 * prev from result]
G -->|No| I[Continue]
H --> J[Set prev = curr]
I --> J
J -->|More characters?| D
J -->|No| K[Return result]
K --> L[End]
Notes:
- First Pass: Skips the
prev < curr?check (G and H), simply adding each symbol’s value. - Second Pass: Similar structure but checks
map[s[i]] < map[s[i+1]]and handles the last character separately (no comparison for the final symbol). - Final Solution: Uses the above logic, adjusting for subtractive cases within the loop by subtracting
2 * prev.
The First Pass adds each symbol’s value without checking for subtractive cases, leading to incorrect results for inputs like "MCMXCIV".
sequenceDiagram
participant A as Algorithm
participant S as String: MCMXCIV
participant M as Map
Note over A: Initialize result = 0
A->>S: Read char 'M'
A->>M: Lookup 'M'
M-->>A: Returns 1000
A->>A: result += 1000 (result = 1000)
A->>S: Read char 'C'
A->>M: Lookup 'C'
M-->>A: Returns 100
A->>A: result += 100 (result = 1100)
A->>S: Read char 'M'
A->>M: Lookup 'M'
M-->>A: Returns 1000
A->>A: result += 1000 (result = 2100)
A->>S: Read char 'X'
A->>M: Lookup 'X'
M-->>A: Returns 10
A->>A: result += 10 (result = 2110)
A->>S: Read char 'C'
A->>M: Lookup 'C'
M-->>A: Returns 100
A->>A: result += 100 (result = 2210)
A->>S: Read char 'I'
A->>M: Lookup 'I'
M-->>A: Returns 1
A->>A: result += 1 (result = 2211)
A->>S: Read char 'V'
A->>M: Lookup 'V'
M-->>A: Returns 5
A->>A: result += 5 (result = 2216)
Note over A: End, return result = 2216
Explanation:
- Input: "MCMXCIV" (M=1000, C=100, M=1000, X=10, C=100, I=1, V=5).
- Steps: Adds each value: 1000 + 100 + 1000 + 10 + 100 + 1 + 5 = 2216.
- Issue: Incorrect result (2216 instead of 1994) because it doesn’t handle subtractive cases (e.g., CM = 1000 - 100, XC = 100 - 10, IV = 5 - 1).
- Result: 2216 (incorrect).
The Second Pass compares each symbol with the next, subtracting the current value if it’s less than the next, and handles the last character separately.
sequenceDiagram
participant A as Algorithm
participant S as String: MCMXCIV
participant M as Map
Note over A: Initialize result = 0
A->>S: Read char 'M' (index 0)
A->>M: Lookup 'M'
M-->>A: Returns 1000
A->>M: Lookup next char 'C'
M-->>A: Returns 100
Note over A: 1000 >= 100, add 1000
A->>A: result += 1000 (result = 1000)
A->>S: Read char 'C' (index 1)
A->>M: Lookup 'C'
M-->>A: Returns 100
A->>M: Lookup next char 'M'
M-->>A: Returns 1000
Note over A: 100 < 1000, subtract 100
A->>A: result -= 100 (result = 900)
A->>S: Read char 'M' (index 2)
A->>M: Lookup 'M'
M-->>A: Returns 1000
A->>M: Lookup next char 'X'
M-->>A: Returns 10
Note over A: 1000 >= 10, add 1000
A->>A: result += 1000 (result = 1900)
A->>S: Read char 'X' (index 3)
A->>M: Lookup 'X'
M-->>A: Returns 10
A->>M: Lookup next char 'C'
M-->>A: Returns 100
Note over A: 10 < 100, subtract 10
A->>A: result -= 10 (result = 1890)
A->>S: Read char 'C' (index 4)
A->>M: Lookup 'C'
M-->>A: Returns 100
A->>M: Lookup next char 'I'
M-->>A: Returns 1
Note over A: 100 >= 1, add 100
A->>A: result += 100 (result = 1990)
A->>S: Read char 'I' (index 5)
A->>M: Lookup 'I'
M-->>A: Returns 1
A->>M: Lookup next char 'V'
M-->>A: Returns 5
Note over A: 1 < 5, subtract 1
A->>A: result -= 1 (result = 1989)
A->>S: Read char 'V' (index 6)
A->>M: Lookup 'V'
M-->>A: Returns 5
Note over A: Last char, add 5
A->>A: result += 5 (result = 1994)
Note over A: End, return result = 1994
Explanation:
- Input: "MCMXCIV".
- Steps:
- M: 1000 ≥ 100 (C), add 1000 (result = 1000).
- C: 100 < 1000 (M), subtract 100 (result = 900).
- M: 1000 ≥ 10 (X), add 1000 (result = 1900).
- X: 10 < 100 (C), subtract 10 (result = 1890).
- C: 100 ≥ 1 (I), add 100 (result = 1990).
- I: 1 < 5 (V), subtract 1 (result = 1989).
- V: Last character, add 5 (result = 1994).
- Result: 1994 (correct).
The Final Solution adds each symbol’s value and corrects for subtractive cases by subtracting twice the previous value if it’s less than the current value.
sequenceDiagram
participant A as Algorithm
participant S as String: MCMXCIV
participant M as Map
Note over A: Initialize result = 0, prev = 0
A->>S: Read char 'M'
A->>M: Lookup 'M'
M-->>A: Returns 1000
A->>A: result += 1000 (result = 1000)
Note over A: prev = 0 < curr = 1000, no subtraction
A->>A: prev = 1000
A->>S: Read char 'C'
A->>M: Lookup 'C'
M-->>A: Returns 100
A->>A: result += 100 (result = 1100)
Note over A: prev = 1000 > curr = 100, no subtraction
A->>A: prev = 100
A->>S: Read char 'M'
A->>M: Lookup 'M'
M-->>A: Returns 1000
A->>A: result += 1000 (result = 2100)
Note over A: prev = 100 < curr = 1000, subtract 2 * 100
A->>A: result -= 200 (result = 1900)
A->>A: prev = 1000
A->>S: Read char 'X'
A->>M: Lookup 'X'
M-->>A: Returns 10
A->>A: result += 10 (result = 1910)
Note over A: prev = 1000 > curr = 10, no subtraction
A->>A: prev = 10
A->>S: Read char 'C'
A->>M: Lookup 'C'
M-->>A: Returns 100
A->>A: result += 100 (result = 2010)
Note over A: prev = 10 < curr = 100, subtract 2 * 10
A->>A: result -= 20 (result = 1990)
A->>A: prev = 100
A->>S: Read char 'I'
A->>M: Lookup 'I'
M-->>A: Returns 1
A->>A: result += 1 (result = 1991)
Note over A: prev = 100 > curr = 1, no subtraction
A->>A: prev = 1
A->>S: Read char 'V'
A->>M: Lookup 'V'
M-->>A: Returns 5
A->>A: result += 5 (result = 1996)
Note over A: prev = 1 < curr = 5, subtract 2 * 1
A->>A: result -= 2 (result = 1994)
A->>A: prev = 5
Note over A: End, return result = 1994
Explanation:
- Input: "MCMXCIV".
- Steps:
- M: Add 1000 (result = 1000), prev = 0 < 1000, no subtraction, prev = 1000.
- C: Add 100 (result = 1100), prev = 1000 > 100, no subtraction, prev = 100.
- M: Add 1000 (result = 2100), prev = 100 < 1000, subtract 2 * 100 = 200 (result = 1900), prev = 1000.
- X: Add 10 (result = 1910), prev = 1000 > 10, no subtraction, prev = 10.
- C: Add 100 (result = 2010), prev = 10 < 100, subtract 2 * 10 = 20 (result = 1990), prev = 100.
- I: Add 1 (result = 1991), prev = 100 > 1, no subtraction, prev = 1.
- V: Add 5 (result = 1996), prev = 1 < 5, subtract 2 * 1 = 2 (result = 1994), prev = 5.
- Result: 1994 (correct).
- First Pass: Simple but incorrect for subtractive cases (e.g., CM, XC, IV), resulting in 2216 instead of 1994. It’s a good starting point in an interview to show initial thinking.
- Second Pass: Correctly handles subtractive cases by comparing adjacent symbols, but requires separate handling for the last character, making it slightly less elegant.
- Final Solution: Most concise and efficient, handling all cases in a single pass without special cases. The correction (subtracting
2 * prev) simplifies the logic while maintaining correctness. - Diagrams: The sequence diagrams highlight the differences in processing:
- First Pass is straightforward but wrong.
- Second Pass checks the next character, adding complexity.
- Final Solution uses a single loop with a clever correction mechanism.
- Time Complexity: All solutions are O(n) (n = string length), as they iterate once. Space complexity is O(1) due to the fixed-size map.
- Interview Tip: Start with the First Pass to show understanding, then refine to the Second Pass, and optimize to the Final Solution, explaining trade-offs and testing with "MCMXCIV" to demonstrate correctness.