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].Problem Overview: Given a Roman numeral string, convert it into its integer value. Roman numerals use symbols like I, V, and X, but sometimes a smaller value appears before a larger one to indicate subtraction (for example IV = 4, IX = 9).
Approach 1: Linear Scan from Left to Right (O(n) time, O(1) space)
Store the value of each Roman symbol in a lookup map (for example I=1, V=5, X=10). Iterate through the string from left to right and compare the value of the current symbol with the next symbol. If the current value is smaller than the next one, it forms a subtractive pair, so subtract the current value from the result. Otherwise add it normally. This approach directly models how Roman numerals are written. The algorithm performs a single pass through the string and uses constant extra memory for the symbol map.
The main operation is a value lookup and comparison at each index. Because each character is processed once, the time complexity is O(n) where n is the length of the string, and the space complexity remains O(1). The value mapping is typically implemented using a dictionary or array, a simple example of a Hash Table lookup while processing the String.
Approach 2: Optimized Reverse Iteration (O(n) time, O(1) space)
Traverse the Roman numeral from right to left instead of left to right. Keep track of the previous value you processed. If the current symbol's value is smaller than the previous value, subtract it from the result; otherwise add it and update the previous value. This works because subtraction only happens when a smaller numeral appears before a larger one. By iterating from the end, the larger value is already known.
This method removes the need to check the next character explicitly and keeps the logic compact. Each character still requires a constant-time lookup and comparison, so the total time complexity remains O(n) with O(1) additional space. The approach relies on simple numeric comparisons based on Roman numeral rules, which fall under basic Math reasoning.
Recommended for interviews: Reverse iteration is usually the cleanest implementation because it avoids lookahead checks and keeps the logic simple. That said, many candidates start with the left‑to‑right scan because it mirrors the written rules of Roman numerals. Showing both demonstrates clear understanding, but the reverse traversal often results in fewer condition checks and cleaner code.
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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Linear Scan from Left to Right | Time Complexity: O(n), where n is the length of the string, because we make one pass through the string. |
| Optimized Reverse Iteration | Time Complexity: O(n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan from Left to Right | O(n) | O(1) | When you want a direct implementation that follows Roman numeral writing rules using next-character comparison. |
| Optimized Reverse Iteration | O(n) | O(1) | Preferred in interviews for simpler logic and no lookahead checks while scanning the string. |
Roman to Integer - Leetcode 13 - Python • NeetCode • 197,307 views views
Watch 9 more video solutions →Practice Roman to Integer with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor