Given a string s representing a Roman numeral, convert it into its corresponding integer value.
Roman numerals consist of seven different symbols, each having a fixed value:
I= 1V= 5X= 10L= 50C= 100D= 500M= 1000
Roman numerals are generally written from larger values to smaller values, from left to right. However, in certain cases, a smaller symbol placed before a larger symbol represents subtraction instead of addition.
The following combinations follow this rule:
IV= 4 andIX= 9XL= 40 andXC= 90CD= 400 andCM= 900
For all other valid combinations, the values of the symbols are added together.
Return the integer represented by the given Roman numeral.
Example 1
Input: s = "XLII"
Output: 42
Explanation: The combination XL represents 40 because X appears before L. The remaining II represents 2. Hence, the final value is 40 + 2 = 42.
Example 2
Input: s = "MCMXCIV"
Output: 1994
Explanation: The Roman numeral can be divided into M = 1000, CM = 900, XC = 90, and IV = 4. Adding these values gives 1000 + 900 + 90 + 4 = 1994.
Approach
Roman numerals follow a simple addition rule in most cases, where the value of each symbol contributes to the final number. The only exception occurs when a smaller symbol appears before a larger one. In such cases, the smaller value is subtracted instead of added. For example, IV represents 4 rather than 6.
A comparison with the next symbol helps identify these special cases. If the current symbol has a smaller value than the next one, its value is subtracted; otherwise, it is added. Applying this rule while moving through the string gives the final integer.
Algorithm
Create a mapping between each Roman symbol and its corresponding integer value.
Traverse the given string from left to right.
Get the integer value of the current Roman symbol.
Check the next symbol, if one exists.
If the current value is smaller than the next value, subtract it from the result.
Otherwise, add the current value to the result.
Return the final accumulated value after processing all symbols.
Dry Run
Roman to Integer
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Converts a Roman numeral into an integer. int romanToInt(string s) { unordered_map<char, int> romanValues = { {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000} }; int result = 0; // Visit every symbol in the Roman numeral. for (int index = 0; index < s.size(); index++) { int currentValue = romanValues[s[index]]; /* Subtract the current value when a larger Roman symbol appears immediately after it. */ if ( index + 1 < s.size() && currentValue < romanValues[s[index + 1]] ) { result -= currentValue; } // Add the current value in every other case. else { result += currentValue; } } return result; }};// Driver Code startsint main() { string s = "XLII"; Solution solution; // Call the function to convert the Roman numeral. int answer = solution.romanToInt(s); cout << answer << "\n"; return 0;}Complexity Analysis
• Time Complexity: O(N) as the algorithm traverses the Roman numeral string once, performing constant-time hashmap lookups and comparisons for each character.
• Space Complexity: O(1), because the hashmap stores exactly seven Roman numeral symbols, requiring constant extra space regardless of the input length.
Interview follow-up Questions
No. Standard Roman numerals use uppercase symbols such as I, V, X, and M. Lowercase input would require conversion to uppercase before processing.
Be the first to add a comment.