Roman to Integer

Easyhash-tablestringmath
Category: Fundamentals
Companies that ask this question:
AmazonMicrosoftGoogleFacebook

Approach

Roman to Integer

Problem Statement

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 |

Roman numerals are usually written from largest to smallest left to right. However, there are special cases for subtraction:

  • I before V or X makes 4 or 9
  • X before L or C makes 40 or 90
  • C before D or M makes 400 or 900

Given a roman numeral, convert it to an integer.

Examples

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, IV = 4

Approach

Left-to-Right with Subtraction Detection

Key Insight: When a smaller value appears before a larger value, subtract it instead of adding it.

Algorithm:

  1. Create a hash map of symbol → value
  2. Iterate through the string left to right
  3. If current symbol < next symbol: subtract current
  4. Otherwise: add current
  5. Return total

Example: "MCMXCIV"

  • M (1000) < C? No → add 1000
  • C (100) < M (1000)? Yes → subtract 100
  • M (1000) < X? No → add 1000
  • X (10) < C (100)? Yes → subtract 10
  • C (100) < I? No → add 100
  • I (1) < V (5)? Yes → subtract 1
  • V (5) → add 5
  • Total: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

Complexity Analysis

  • Time Complexity: O(n) where n is the length of the string

    • Single pass through the string

  • Space Complexity: O(1)

    • Fixed size hash map (7 symbols)

Edge Cases

  1. Single symbol: Return its value
  2. All same symbols: "III" = 3
  3. Multiple subtractions: "MCMXCIV" = 1994
  4. No subtractions: "LVIII" = 58
  5. Maximum value: "MMMCMXCIX" = 3999

Visual Intuition

"MCMXCIV"
 ↓
M: 1000 (add, next is C which is less)
  ↓
 C: 100 (subtract, next is M which is greater)
    ↓
   M: 1000 (add, next is X which is less)
      ↓
     X: 10 (subtract, next is C which is greater)
        ↓
       C: 100 (add, next is I which is less)
          ↓
         I: 1 (subtract, next is V which is greater)
            ↓
           V: 5 (add, last symbol)

Result: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

Common Mistakes

  1. Not handling subtraction cases: Must check if next symbol is larger
  2. Adding instead of subtracting: When current < next, subtract
  3. Index out of bounds: Check if there's a next symbol before comparing
  4. Wrong subtraction rules: Only specific pairs can subtract

Related Problems

  • Integer to Roman
  • Excel Sheet Column Number
  • Excel Sheet Column Title

Solution

java
1/**
2 * Roman to Integer
3 * Time: O(n)
4 * Space: O(1)
5 */
6
7class Solution {
8    public int romanToInt(String s) {
9        Map<Character, Integer> values = new HashMap<>();
10        values.put('I', 1);
11        values.put('V', 5);
12        values.put('X', 10);
13        values.put('L', 50);
14        values.put('C', 100);
15        values.put('D', 500);
16        values.put('M', 1000);
17        
18        int total = 0;
19        int n = s.length();
20        
21        for (int i = 0; i < n; i++) {
22            int currentValue = values.get(s.charAt(i));
23            
24            // If current < next, subtract it
25            if (i < n - 1 && currentValue < values.get(s.charAt(i + 1))) {
26                total -= currentValue;
27            } else {
28                total += currentValue;
29            }
30        }
31        
32        return total;
33    }
34}
35
Loading visualizer...