# Roman to Integer
**Difficulty:** EASY
[External](https://leetcode.com/problems/roman-to-integer)
Canonical: https://scaleengineer.com/dsa/problems/roman-to-integer
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Hash Table, String
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [KLA](https://scaleengineer.com/companies/kla), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Pwc](https://scaleengineer.com/companies/pwc), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Wipro](https://scaleengineer.com/companies/wipro), [Wise](https://scaleengineer.com/companies/wise), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Salesforce](https://scaleengineer.com/companies/salesforce), [Booking.com](https://scaleengineer.com/companies/booking.com), [Geico](https://scaleengineer.com/companies/geico), [Axon](https://scaleengineer.com/companies/axon), [DeltaX](https://scaleengineer.com/companies/deltax), [Thomson Reuters](https://scaleengineer.com/companies/thomson-reuters), [Warnermedia](https://scaleengineer.com/companies/warnermedia)
---
## Problem
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]`.

# Approaches
## Replacement of Subtractive Pairs
This approach simplifies the problem by first transforming the Roman numeral string into a purely additive form. It identifies and replaces all subtractive combinations (like 'IV', 'IX') with their additive equivalents (like 'IIII', 'VIIII'). After all replacements, the string contains only symbols that are added together. The final step is to iterate through this modified string and sum the values of each individual Roman numeral symbol.
**Time:** O(N) · **Space:** O(N)
**Pros:** The logic for the final summation is very simple, as it involves only addition.
**Cons:** Inefficient due to multiple string passes and creating new string objects for each replacement (especially in languages with immutable strings like Java).; The space complexity is O(N) because new strings are created, making it less memory-efficient than other approaches.
### Explanation
The core idea is to eliminate the complexity of subtraction rules. We perform a series of string replacements to convert subtractive pairs into their longer, additive forms. For example, 'CM' (900) is replaced by 'DCCCC' (500 + 100*4). Once all such replacements are done, the Roman numeral follows a simple rule: the total value is the sum of all individual symbol values. We can then iterate through the transformed string once to calculate this sum. A map is used to store the value of each Roman symbol for easy lookup.

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    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);

        s = s.replace("IV", "IIII");
        s = s.replace("IX", "VIIII");
        s = s.replace("XL", "XXXX");
        s = s.replace("XC", "LXXXX");
        s = s.replace("CD", "CCCC");
        s = s.replace("CM", "DCCCC");

        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += map.get(c);
        }
        return sum;
    }
}
```
### Algorithm
- Create a map to store the integer value for each Roman symbol ('I', 'V', 'X', etc.).
- Perform string replacements for all subtractive pairs in the input string `s`:
  - `s = s.replace("IV", "IIII")`
  - `s = s.replace("IX", "VIIII")`
  - `s = s.replace("XL", "XXXX")`
  - `s = s.replace("XC", "LXXXX")`
  - `s = s.replace("CD", "CCCC")`
  - `s = s.replace("CM", "DCCCC")`
- Initialize a variable `total` to 0.
- Iterate through each character of the modified string.
- For each character, look up its value in the map and add it to `total`.
- Return `total`.

## Left-to-Right Pass with Lookahead
This approach processes the Roman numeral string from left to right in a single pass. For each symbol, it compares its value with the value of the symbol immediately to its right. If the current symbol's value is less than the next one, it signifies a subtractive case (like 'IV' or 'CM'), and its value is subtracted from the total. Otherwise, its value is added to the total. The value of the last symbol is always added.
**Time:** O(N) · **Space:** O(1)
**Pros:** Efficient with O(N) time complexity as it requires only a single pass through the string.; Space-efficient with O(1) space complexity (excluding the map which is constant size).
**Cons:** The logic is slightly more complex than a right-to-left pass due to the need for a lookahead and special handling of the last character.
### Explanation
This method iterates through the string from left to right, which is a natural way to read. We maintain a running total. For each symbol, we check if it's part of a subtractive pair by looking at the next symbol. If the current symbol's value is less than the next symbol's value (e.g., 'I' before 'V' in "IV"), we subtract the current symbol's value from our total. Otherwise, we add it. The final symbol is always added, so the loop runs up to the second-to-last character, and the last character's value is added after the loop.

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    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() - 1; i++) {
            int currentVal = map.get(s.charAt(i));
            int nextVal = map.get(s.charAt(i + 1));
            if (currentVal < nextVal) {
                total -= currentVal;
            } else {
                total += currentVal;
            }
        }
        total += map.get(s.charAt(s.length() - 1));
        return total;
    }
}
```
### Algorithm
- Create a map to store the integer value for each Roman symbol.
- Initialize `total` to 0.
- Iterate through the string from `i = 0` to `s.length() - 2`.
- Get the value of the current symbol `s.charAt(i)` and the next symbol `s.charAt(i+1)`.
- If `value(current) < value(next)`, subtract `value(current)` from `total`.
- Otherwise, add `value(current)` to `total`.
- After the loop, add the value of the last symbol (`s.charAt(s.length() - 1)`) to `total`.
- Return `total`.

## Right-to-Left Pass
This is the most efficient and elegant approach. It involves iterating through the Roman numeral string from right to left. The logic is based on the observation that when read from right to left, a symbol's value is added to the total unless it is smaller than the symbol to its right, in which case it is subtracted. This eliminates the need for complex lookaheads.
**Time:** O(N) · **Space:** O(1)
**Pros:** Highly efficient with O(N) time and O(1) space complexity.; Features a very clean and simple implementation logic without special cases inside the loop.; Arguably the most elegant solution to the problem.
**Cons:** Iterating from right to left might be slightly less intuitive for some developers compared to a standard left-to-right pass.
### Explanation
This approach is often considered the most clever and clean. By processing the string from right to left, the logic becomes very straightforward. We initialize our total with the value of the rightmost symbol. Then, we iterate backwards. For each symbol, we compare it with the one to its right (which we have already processed). If the current symbol's value is smaller (e.g., 'I' in "IV"), we subtract its value. Otherwise, we add it. This works because in Roman numerals, any smaller value preceding a larger value indicates subtraction; otherwise, it's always addition.

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    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 = map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                total -= map.get(s.charAt(i));
            } else {
                total += map.get(s.charAt(i));
            }
        }
        return total;
    }
}
```
### Algorithm
- Create a map to store the integer value for each Roman symbol.
- Initialize `total` with the value of the last symbol in the string.
- Iterate through the string backwards, from `i = s.length() - 2` down to `0`.
- Get the value of the current symbol `s.charAt(i)` and the symbol to its right `s.charAt(i+1)`.
- If `value(current) < value(right)`, subtract `value(current)` from `total`.
- Otherwise, add `value(current)` to `total`.
- Return `total`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int RomanToInt(string s) {
        Dictionary < char, int > d = new Dictionary < char, int > ();
        d.Add('I', 1);
        d.Add('V', 5);
        d.Add('X', 10);
        d.Add('L', 50);
        d.Add('C', 100);
        d.Add('D', 500);
        d.Add('M', 1000);
        int ans = d[s[s.Length - 1]];
        for (int i = 0; i < s.Length - 1; ++i) {
            int sign = d[s[i]] < d[s[i + 1]] ? -1 : 1;
            ans += sign * d[s[i]];
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int romanToInt(String s) {
    String cs = "IVXLCDM";
    int[] vs = {1, 5, 10, 50, 100, 500, 1000};
    Map<Character, Integer> d = new HashMap<>();
    for (int i = 0; i < vs.length; ++i) {
      d.put(cs.charAt(i), vs[i]);
    }
    int n = s.length();
    int ans = d.get(s.charAt(n - 1));
    for (int i = 0; i < n - 1; ++i) {
      int sign = d.get(s.charAt(i)) < d.get(s.charAt(i + 1)) ? -1 : 1;
      ans += sign * d.get(s.charAt(i));
    }
    return ans;
  }
}

```

### JavaScript

```javascript
const romanToInt = function ( s ) { const d = { I : 1 , V : 5 , X : 10 , L : 50 , C : 100 , D : 500 , M : 1000 , }; let ans = d [ s [ s . length - 1 ]]; for ( let i = 0 ; i < s . length - 1 ; ++ i ) { const sign = d [ s [ i ]] < d [ s [ i + 1 ]] ? - 1 : 1 ; ans += sign * d [ s [ i ]]; } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  int romanToInt(string s) {
    unordered_map<char, int> nums{
        {'I', 1},   {'V', 5},   {'X', 10},   {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000},
    };
    int ans = nums[s.back()];
    for (int i = 0; i < s.size() - 1; ++i) {
      int sign = nums[s[i]] < nums[s[i + 1]] ? -1 : 1;
      ans += sign * nums[s[i]];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def romanToInt(self, s: str) -> int: d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} return sum((- 1 if d[a] < d[b] else 1) * d[a] for a, b in pairwise(s)) + d[s[- 1]]

```