Roman to Integer Conversion in DSA Python - Time & Space Complexity

Time Complexity: Roman to Integer Conversion

O(n)

Understanding Time Complexity

We want to understand how the time needed to convert a Roman numeral to an integer changes as the length of the Roman numeral grows.

Specifically, how does the number of steps grow when the input string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def roman_to_int(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        value = roman_map[s[i]]
        if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= value
        else:
            total += value
    return total
    

This code converts a Roman numeral string into its integer value by checking each character and deciding whether to add or subtract its value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the input string once.
• How many times: Exactly once for each character, so as many times as the length of the string.

How Execution Grows With Input

As the Roman numeral string gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 checks and additions/subtractions
100	About 100 checks and additions/subtractions
1000	About 1000 checks and additions/subtractions

Pattern observation: The work grows evenly and directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows in a straight line with the length of the Roman numeral string.

Common Mistake

[X] Wrong: "Because there is a nested if inside the loop, the time complexity is quadratic O(n²)."

[OK] Correct: The if condition is inside a single loop and does not cause extra loops; it only checks the next character once, so the overall work is still proportional to n.

Interview Connect

Understanding this linear time complexity helps you explain how your solution scales well with input size, a key skill interviewers look for.

Self-Check

"What if we used recursion to process each character instead of a loop? How would the time complexity change?"

Practice

1. What is the integer value of the Roman numeral IX?

easy

A. 11

B. 19

C. 6

D. 9

Solution

1. Step 1: Understand Roman numeral rules for subtraction

   In Roman numerals, when a smaller numeral appears before a larger one, it is subtracted. Here, I (1) is before X (10), so 1 is subtracted from 10.

2. Step 2: Calculate the value of IX

   10 - 1 = 9.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when smaller numeral is before larger one [OK]

Common Mistakes:

• Adding values instead of subtracting
• Confusing IX with XI
• Ignoring subtraction rule

2. Which of the following Python code snippets correctly initializes a dictionary mapping Roman numerals to integers?

easy

A. roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50}

B. roman_map = ['I': 1, 'V': 5, 'X': 10, 'L': 50]

C. roman_map = ('I' = 1, 'V' = 5, 'X' = 10, 'L' = 50)

D. roman_map = {I: 1, V: 5, X: 10, L: 50}

Solution

1. Step 1: Identify correct dictionary syntax in Python

   Python dictionaries use curly braces with key:value pairs, keys as strings must be quoted.

2. Step 2: Check each option

   roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50} uses correct syntax with quotes and curly braces. Options A, B, and D use invalid syntax. roman_map = {I: 1, V: 5, X: 10, L: 50} uses unquoted keys which causes NameError.

3. Final Answer:

   roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50} -> Option A

4. Quick Check:

   Correct dictionary syntax = roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50} [OK]

Hint: Use curly braces and quote keys for dictionaries [OK]

Common Mistakes:

• Using square brackets instead of curly braces
• Not quoting string keys
• Using assignment '=' inside dictionary

3. What is the output of the following Python code?

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= roman_map[s[i]]
        else:
            total += roman_map[s[i]]
    return total

print(roman_to_int('XIV'))

medium

A. 14

B. 16

C. 9

D. 11

Solution

1. Step 1: Trace the loop for input 'XIV'

   Characters: X(10), I(1), V(5). Loop index i from 0 to 2.
   i=0: X(10) < I(1)? No, add 10.
   i=1: I(1) < V(5)? Yes, subtract 1.
   i=2: V(5), no next char, add 5.

2. Step 2: Calculate total

   Total = 10 - 1 + 5 = 14.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   X(10) + IV(4) = 14 [OK]

Hint: Subtract if current < next numeral, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Off-by-one errors in loop
• Ignoring last character addition

4. The following code is intended to convert a Roman numeral string to an integer. What is the error?

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10}
    total = 0
    for i in range(len(s)):
        if roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= roman_map[s[i]]
        else:
            total += roman_map[s[i]]
    return total

print(roman_to_int('IX'))

medium

A. SyntaxError due to missing colon

B. KeyError because 'IX' is not in roman_map

C. IndexError due to accessing s[i + 1] without boundary check

D. Returns incorrect value 11 instead of 9

Solution

1. Step 1: Identify loop and index usage

   The loop runs from i=0 to len(s)-1. At last index i, accessing s[i+1] causes IndexError.

2. Step 2: Explain why error occurs

   For input 'IX' (length 2), when i=1, s[i+1] is s[2], which is out of range.

3. Final Answer:

   IndexError due to accessing s[i + 1] without boundary check -> Option C

4. Quick Check:

   Check index bounds before s[i+1] access [OK]

Hint: Always check index before accessing s[i+1] [OK]

Common Mistakes:

• Not checking index bounds in loops
• Assuming s[i+1] always exists
• Ignoring runtime errors

5. Given the Roman numeral string 'MCMXCIV', what integer does the following code return?

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev_value = 0
    for char in reversed(s):
        value = roman_map[char]
        if value < prev_value:
            total -= value
        else:
            total += value
        prev_value = value
    return total

print(roman_to_int('MCMXCIV'))

hard

A. 1494

B. 1994

C. 1949

D. 2094

Solution

1. Step 1: Understand reversed traversal and subtraction logic

   The code processes characters from right to left, subtracting if current value is less than previous.

2. Step 2: Trace values for 'MCMXCIV'

   Characters reversed: V(5), I(1), C(100), X(10), M(1000), C(100), M(1000)
   Calculate total:
   V=5 (add 5)
   I=1 < 5 subtract 1 (total=4)
   C=100 > 1 add 100 (total=104)
   X=10 < 100 subtract 10 (total=94)
   M=1000 > 10 add 1000 (total=1094)
   C=100 < 1000 subtract 100 (total=994)
   M=1000 > 100 add 1000 (total=1994)

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   MCMXCIV = 1994 [OK]

Hint: Traverse right to left, subtract if smaller than previous [OK]

Common Mistakes:

• Processing left to right without subtraction logic
• Confusing numeral values
• Missing reversed traversal step