Skip to main content
Talentd

Roman to Integer - Solution & Explanation

EasyHash TableMathString23 min readAsked at: Amazon, Microsoft, Apple +33
Practice this problem

Problem Statement

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].

Approach Overview

Problem Overview: Roman numerals represent numbers using characters like I, V, X, L, C, D, and M. Each symbol has a value, but smaller symbols placed before larger ones indicate subtraction (e.g., IV = 4). The task is to convert a Roman numeral string into its integer value while correctly handling these subtractive patterns.

Approach 1: Linear Scan from Left to Right (O(n) time, O(1) space)

Store the value of each Roman symbol in a small lookup structure such as a hash table. Iterate through the string from left to right. For each character, compare its value with the value of the next character. If the current value is smaller than the next one, subtract it from the total because this represents a subtractive pair (for example, I before V). Otherwise, add the value normally. This approach directly models how Roman numerals are written and keeps the logic simple. The iteration touches each character once, giving O(n) time complexity, while the lookup map and a few variables keep space at O(1).

This method is intuitive and mirrors the rules of Roman numerals closely. Many candidates start with this approach because it clearly expresses the subtractive rule and is easy to debug during interviews.

Approach 2: Optimized Reverse Iteration (O(n) time, O(1) space)

Instead of checking the next symbol, iterate from right to left. Maintain the value of the previous numeral seen during the traversal. For each symbol, look up its value from the same mapping structure (again typically implemented with a hash table). If the current value is smaller than the previous value, subtract it from the total. Otherwise, add it and update the previous value.

The key insight is that Roman numerals only subtract when a smaller symbol appears before a larger one. When scanning from the end, the "previous" value naturally represents the larger numeral in those cases. This eliminates the need to check the next character or manage index bounds. The algorithm still performs a single pass over the string, so the time complexity remains O(n) and space stays O(1). Many engineers prefer this version because the subtraction rule becomes a simple comparison with the last processed value.

Recommended for interviews: Both approaches are linear and acceptable. Interviewers typically expect the reverse-iteration solution because the logic is cleaner and avoids look‑ahead checks. Starting with the left‑to‑right scan demonstrates that you understand Roman numeral subtraction rules, then refining it to the reverse traversal shows strong algorithmic thinking. The core idea in both implementations is constant-time value lookup combined with a single pass over the input using basic math comparisons.

Approach 1: Linear Scan from Left to Right

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Reverse Iteration

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Hash Table + Simulation

First, we use a hash table d to record the numerical value corresponding to each character. Then, we traverse the string s from left to right. If the numerical value corresponding to the current character is less than the numerical value corresponding to the character on the right, we subtract the numerical value corresponding to the current character. Otherwise, we add the numerical value corresponding to the current character.

The time complexity is O(n), and the space complexity is O(m). Here, n and m are the length of the string s and the size of the character set, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHPRubyC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Ruby

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), constant space as the dictionary size does not depend on the input.

Optimized Reverse Iteration

Time Complexity: O(n).
Space Complexity: O(1).

Hash Table + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan from Left to RightO(n)O(1)Good for explaining Roman subtraction rules clearly during interviews
Optimized Reverse IterationO(n)O(1)Preferred implementation with cleaner logic and no look‑ahead checks

Video Solution

Roman to Integer - Leetcode 13 - Python • NeetCode • 236,481 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Roman to Integer easy or hard?
Roman to Integer is classified as an Easy problem. The challenge is mainly understanding the subtractive cases such as IV (4) and IX (9). Once that rule is handled, the implementation becomes a straightforward single-pass string traversal.
Roman to Integer Python/Java solution
Most Python and Java solutions define a dictionary or map with the seven Roman symbols and their values, then iterate through the string applying the subtraction rule. Both languages implement the algorithm in O(n) time and O(1) extra space since the mapping size is constant.
How to solve Roman to Integer in O(n)?
Create a mapping from Roman symbols to integer values. Iterate through the string once while applying the subtraction rule: if a symbol is smaller than the one after it (or smaller than the previous symbol in reverse traversal), subtract it; otherwise add it. Because every character is visited once, the algorithm runs in O(n) time.
What is the best approach for Roman to Integer?
The optimized reverse iteration approach is usually considered the best solution. Traverse the string from right to left, keep track of the previous value, and subtract when the current value is smaller. This method processes the string once with O(n) time and O(1) space while keeping the logic concise.
Is Roman to Integer asked at Google/Amazon/Meta?
Roman to Integer appears frequently in coding interview prep lists and has been reported in interview rounds at companies like Amazon and Google for entry-level roles. It tests string traversal, edge case handling, and understanding of simple rule-based parsing.
What data structure is used in Roman to Integer?
A hash table (or dictionary/map) is typically used to store the integer value for each Roman numeral symbol. This allows constant-time lookup when converting characters like I, V, X, L, C, D, and M during the scan of the string.
What is the time complexity of Roman to Integer?
The standard solution runs in O(n) time where n is the length of the Roman numeral string. Each character is processed exactly once with constant-time value lookup from a map. Space complexity stays O(1) because the symbol-to-value mapping contains only seven fixed entries.

Ready to solve this problem?

Practice Roman to Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Integer to Roman