Roman to Integer - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Convert a Roman numeral string s to its integer value.
Create a dictionary d mapping Roman numerals to their values: I=1, V=5, X=10, L=50, C=100, D=500, M=1000.
Initialize a variable summ to 0 to store the total value and an index i to 0.
While i is less than the length n of s:
- If i < n-1 and the value of s[i] is less than s[i+1], subtract s[i]’s value from s[i+1]’s value, add the result to summ, and increment i by 2.
- Otherwise, add s[i]’s value to summ and increment i by 1.
Return summ as the integer value.

Code Solution

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I': 1, 'V':5, 'X':10, 'L':50, 'C':100, 'D': 500, 'M':1000}
        summ = 0
        n = len(s)
        i = 0
        
        while i < n:
            if i < n - 1 and d[s[i]] < d[s[i+1]]:
                summ += d[s[i+1]] - d[s[i]]
                i += 2
            else:
                summ += d[s[i]]
                i += 1
        
        return summ
        # Time: O(n)
        # Space: O(1)

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> d = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
        int summ = 0;
        int n = s.size();
        int i = 0;

        while (i < n) {
            if (i < n - 1 && d[s[i]] < d[s[i + 1]]) {
                summ += d[s[i + 1]] - d[s[i]];
                i += 2;
            } else {
                summ += d[s[i]];
                i++;
            }
        }

        return summ;
    }
};

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

public class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> d = new HashMap<>();
        d.put('I', 1);
        d.put('V', 5);
        d.put('X', 10);
        d.put('L', 50);
        d.put('C', 100);
        d.put('D', 500);
        d.put('M', 1000);

        int summ = 0;
        int n = s.length();
        int i = 0;

        while (i < n) {
            if (i < n - 1 && d.get(s.charAt(i)) < d.get(s.charAt(i + 1))) {
                summ += d.get(s.charAt(i + 1)) - d.get(s.charAt(i));
                i += 2;
            } else {
                summ += d.get(s.charAt(i));
                i++;
            }
        }

        return summ;
    }
}

function romanToInt(s) {
    const d = {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000};
    let summ = 0;
    const n = s.length;
    let i = 0;

    while (i < n) {
        if (i < n - 1 && d[s[i]] < d[s[i + 1]]) {
            summ += d[s[i + 1]] - d[s[i]];
            i += 2;
        } else {
            summ += d[s[i]];
            i++;
        }
    }

    return summ;
}

Detailed Explanation

Detailed Explanation: Roman to Integer

The Roman to Integer problem asks you to take a string written in Roman numerals and convert it into an integer value. Roman numerals were used in ancient Rome and are composed of letters representing certain base values. This task involves interpreting those characters correctly and handling specific patterns where subtraction is used instead of addition.

Understanding Roman Numerals

Roman numerals use seven different symbols:

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

Normally, these symbols are added from left to right. For example, "VI" means 5 + 1 = 6. However, if a smaller symbol appears before a larger one, it is subtracted. For example, "IV" means 5 - 1 = 4.

How the Algorithm Works

The solution involves scanning the input string from left to right while checking each character and the one after it (if it exists). We use a dictionary to map each Roman numeral to its integer value. Then, during the scan:

If the current character represents a value smaller than the next one, we subtract it.
Otherwise, we simply add the current character's value.

Example Walkthrough

Consider the input "MCMXCIV". We can break it down like this:

M  = 1000
CM = 900  (100 before 1000, so subtract)
XC = 90   (10 before 100, subtract)
IV = 4    (1 before 5, subtract)
Total = 1000 + 900 + 90 + 4 = 1994

Pseudocode

map = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
sum = 0
i = 0

while i < s.length:
if i + 1 < s.length and map[s[i]] < map[s[i+1]]:
    sum += map[s[i+1]] - map[s[i]]
    i += 2
else:
    sum += map[s[i]]
    i += 1

return sum

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since the Roman numeral map is constant in size.

Summary

To convert a Roman numeral to an integer, we loop through the string while using a simple rule: subtract if the current numeral is smaller than the next; otherwise, add it. This approach covers all valid Roman numeral strings and runs efficiently in linear time.

Get Personalized Support at AlgoMap Bootcamp 💡