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 <= 15s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').s is a valid roman numeral in the range [1, 3999].The key idea in Roman to Integer is understanding how Roman numerals represent numbers. Each symbol has a fixed value (for example I=1, V=5, X=10, etc.). Normally, values are added from left to right. However, when a smaller value appears before a larger value (such as IV or IX), it represents subtraction instead of addition.
A common approach is to use a hash table (or map) to store the value of each Roman symbol. Then iterate through the string and compare the current symbol with the next one. If the current value is smaller than the next, subtract it; otherwise, add it to the result. Another clean approach is scanning from right to left while tracking the previous value.
This method processes each character once, making it efficient for interview settings. The algorithm runs in linear time relative to the length of the string and uses constant extra space for the symbol map.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Single Pass Traversal | O(n) | O(1) |
| Right-to-Left Comparison Method | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Problem is simpler to solve by working the string from back to front and using a map.
The key idea is to traverse the given Roman numeral string from left to right. As we process each character, we compare it with the next one. If the current character has a smaller value than the next one, it means we are in a subtraction scenario (like IV = 4), so we subtract the value of the current character. Otherwise, we add its value.
Time Complexity: O(n), where n is the length of the string, because we make one pass through the string.
Space Complexity: O(1), constant space as the dictionary size does not depend on the input.
1#include <stdio.h>
2#include <string.h>
3
4int romanToInt(char* s) {
5 int values[256] =
This C implementation starts by initializing a mapping from Roman symbols to their respective integer values using an array indexed by ASCII character codes. As we iterate through the Roman numeral string, we subtract or add the value based on the rule of subtraction.
In this approach, we traverse the string from right to left. We add the value of the current character to the total if it is greater or equal to its previous character; otherwise, we subtract it. Reverse traversal helps us intuitively handle the subtraction rule.
Time Complexity: O(n).
Space Complexity: O(1).
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Roman to Integer is a common easy-level interview problem used to test string processing and basic hash map usage. It often appears in coding practice platforms and can be asked in interviews at companies including large tech firms.
The optimal approach uses a hash map to store Roman numeral values and iterates through the string once. By comparing the current symbol with the next symbol, the algorithm decides whether to add or subtract the value. This results in an O(n) time solution with constant space.
A hash table (or dictionary) is the most convenient data structure for this problem. It allows constant-time lookup of each Roman numeral's integer value, making the conversion process efficient and easy to implement.
Roman numerals use a subtractive rule where a smaller numeral placed before a larger one indicates subtraction. For example, IV represents 4 and IX represents 9. Detecting this pattern during traversal is essential for correct conversion.
This C program reverses the logic, starting from the end of the string and using a variable to remember the last checked value to determine whether to add or subtract.