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

Time Complexity: Roman to Integer Conversion

O(n)

Understanding Time Complexity

We want to know how the time to convert a Roman numeral to an integer changes as the numeral gets longer.

How does the number of steps grow when the input string grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func romanToInt(s string) int {
    romanMap := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total := 0
    for i := 0; i < len(s); i++ {
        if i+1 < len(s) && romanMap[s[i]] < romanMap[s[i+1]] {
            total -= romanMap[s[i]]
        } else {
            total += romanMap[s[i]]
        }
    }
    return total
}

This code converts a Roman numeral string to an integer by checking each character and its next one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each character in the string once.
• How many times: Exactly once for each character in the input 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.

Common Mistake

[X] Wrong: "Because of the subtraction rule, the code might check pairs multiple times making it slower than linear."

[OK] Correct: The code only looks at each character once and compares it to the next one, so it never repeats work on the same characters.

Interview Connect

Understanding this helps you explain how simple loops handle string parsing efficiently, a common skill in coding interviews.

Self-Check

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

Practice

1. What is the value of the Roman numeral IX when converted to an integer?

easy

A. 6

B. 11

C. 19

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 integer value

   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 Go code snippets correctly initializes a map for Roman numeral values?

easy

A. romanMap := map[string]int{"I" = 1, "V" = 5, "X" = 10}

B. romanMap := map[int]string{1: "I", 5: "V", 10: "X"}

C. romanMap := map[string]int{"I": 1, "V": 5, "X": 10}

D. romanMap := map[string]int{I: 1, V: 5, X: 10}

Solution

1. Step 1: Check map key and value types

   The map should have string keys (Roman numerals) and int values (their integer equivalents). romanMap := map[string]int{"I": 1, "V": 5, "X": 10} uses map[string]int correctly.

2. Step 2: Verify syntax correctness

   romanMap := map[string]int{"I": 1, "V": 5, "X": 10} uses correct Go syntax with colon ':' to assign values. Options A and C have syntax errors, and B reverses key-value types.

3. Final Answer:

   romanMap := map[string]int{"I": 1, "V": 5, "X": 10} -> Option C

4. Quick Check:

   Correct map syntax uses colons and proper types [OK]

Hint: Use colon ':' for map key-value pairs in Go [OK]

Common Mistakes:

• Using '=' instead of ':' in map initialization
• Swapping key and value types
• Omitting quotes around string keys

3. What will be the output of the following Go code snippet?

func romanToInt(s string) int {
    romanMap := map[byte]int{'I': 1, 'V': 5, 'X': 10}
    total := 0
    for i := 0; i < len(s); i++ {
        if i+1 < len(s) && romanMap[s[i]] < romanMap[s[i+1]] {
            total -= romanMap[s[i]]
        } else {
            total += romanMap[s[i]]
        }
    }
    return total
}

fmt.Println(romanToInt("IV"))

medium

A. 6

B. 4

C. 9

D. Error

Solution

1. Step 1: Analyze the loop and subtraction logic

   The code subtracts the value if the current numeral is less than the next one, else adds it. For "IV", 'I' (1) < 'V' (5), so subtract 1, then add 5.

2. Step 2: Calculate total value

   Total = -1 + 5 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   IV = 4 using subtraction rule [OK]

Hint: Subtract when current < next numeral [OK]

Common Mistakes:

• Adding all values without subtraction
• Index out of range errors
• Confusing byte and string keys in map

4. The following Go function is intended to convert Roman numerals to integers. What is the bug?

func romanToInt(s string) int {
    romanMap := map[byte]int{'I': 1, 'V': 5, 'X': 10}
    total := 0
    for i := 0; i < len(s); i++ {
        if romanMap[s[i]] < romanMap[s[i+1]] {
            total -= romanMap[s[i]]
        } else {
            total += romanMap[s[i]]
        }
    }
    return total
}

medium

A. Missing check for i+1 < len(s) causing index out of range

B. Using map with byte keys instead of string keys

C. Incorrect subtraction logic for Roman numerals

D. Returning total before loop ends

Solution

1. Step 1: Identify loop boundary issue

   The code accesses s[i+1] without checking if i+1 is within string length, causing possible index out of range error.

2. Step 2: Explain fix

   Adding condition 'i+1 < len(s)' before accessing s[i+1] prevents runtime error.

3. Final Answer:

   Missing check for i+1 < len(s) causing index out of range -> Option A

4. Quick Check:

   Always check bounds before accessing next element [OK]

Hint: Check i+1 < len(s) before accessing s[i+1] [OK]

Common Mistakes:

• Ignoring string length check for next index
• Confusing byte and string keys (not a bug here)
• Incorrect subtraction logic (logic is correct)

5. Given the Roman numeral MCMXCIV, what integer does it convert to using the standard Roman to Integer rules?

hard

A. 1994

B. 1984

C. 2004

D. 1949

Solution

1. Step 1: Break down the numeral into parts

   M = 1000, CM = 900 (100 before 1000 means subtract 100), XC = 90 (10 before 100), IV = 4 (1 before 5).

2. Step 2: Sum all parts

   1000 + 900 + 90 + 4 = 1994.

3. Final Answer:

   1994 -> Option A

4. Quick Check:

   MCMXCIV = 1994 by adding and subtracting parts [OK]

Hint: Add values, subtract when smaller before larger [OK]

Common Mistakes:

• Adding all numerals without subtraction
• Misreading CM as 1100 instead of 900
• Ignoring subtraction pairs