Roman to Integer Conversion in DSA C++ - Time & Space Complexity

Time Complexity: Roman to Integer Conversion

O(n)

Understanding Time Complexity

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

How does the number of steps grow when the Roman numeral string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int romanToInt(string s) {
    unordered_map<char, int> values = {{'I',1}, {'V',5}, {'X',10}, {'L',50}, {'C',100}, {'D',500}, {'M',1000}};
    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && values[s[i]] < values[s[i+1]]) {
            total -= values[s[i]];
        } else {
            total += values[s[i]];
        }
    }
    return total;
}
    

This code converts a Roman numeral string to its integer value by scanning each character once and deciding to add or subtract based on the next character.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single for-loop scanning each character in the string once.
• How many times: Exactly once per character, so n times for input length n.

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 in a straight line with input size; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows directly with the length of the Roman numeral string.

Common Mistake

[X] Wrong: "Because of the subtraction rule, the code might need to look ahead multiple characters or backtrack, making it slower than linear."

[OK] Correct: The code only looks one character ahead at a time and never revisits characters, so it still processes each character once, keeping it linear.

Interview Connect

Understanding this linear time complexity helps you explain why your solution is efficient and meets expectations for string processing tasks.

Self-Check

"What if the input was given as a linked list of characters instead of a string? How would the time complexity change?"

Practice

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

easy

A. 11

B. 6

C. 9

D. 19

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 subtract 1 from 10.

2. Step 2: Calculate the integer value

   10 - 1 = 9.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when smaller numeral precedes larger one [OK]

Common Mistakes:

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

2. Which of the following C++ code snippets correctly initializes a map for Roman numeral values?

easy

A. std::map roman{{'I', 1}, {'V', 5}, {'X', 10}};

B. std::map roman = {'I':1, 'V':5, 'X':10};

C. std::map roman = {('I', 1), ('V', 5), ('X', 10)};

D. std::map roman = [('I', 1), ('V', 5), ('X', 10)];

Solution

1. Step 1: Check C++ map initialization syntax

   In modern C++, maps can be initialized using initializer lists with curly braces and pairs inside curly braces.

2. Step 2: Identify correct syntax

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; uses double braces with pairs correctly. Options A, B, and C use invalid syntax for map initialization.

3. Final Answer:

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; -> Option A

4. Quick Check:

   Correct map initialization syntax [OK]

Hint: Use double braces with pairs for map initialization [OK]

Common Mistakes:

• Using colon instead of comma in initializer list
• Using parentheses instead of braces for pairs
• Using square brackets for initialization

3. What is the output of the following C++ code snippet?

std::string s = "MCMXCIV";
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int result = 0;
for (int i = 0; i < s.size(); ++i) {
  if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
    result -= roman[s[i]];
  } else {
    result += roman[s[i]];
  }
}
std::cout << result << std::endl;

medium

A. 1904

B. 1994

C. 1094

D. 1949

Solution

1. Step 1: Trace the loop through the string "MCMXCIV"

   Check each character and compare with next: M(1000), C(100), M(1000), X(10), C(100), I(1), V(5). Subtract when current < next, else add.

2. Step 2: Calculate result step-by-step

   Positions: M(1000, add), C(100, next M=1000 > 100 subtract), M(1000, add), X(10, next C=100 > 10 subtract), C(100, add), I(1, next V=5 > 1 subtract), V(5, add). Calculation: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   Roman "MCMXCIV" = 1994 [OK]

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

Common Mistakes:

• Adding all values without subtraction
• Misreading character values
• Off-by-one errors in loop

4. Identify the bug in the following C++ code for Roman to Integer conversion:

int romanToInt(std::string s) {
  std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
  int result = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (roman[s[i]] < roman[s[i+1]]) {
      result -= roman[s[i]];
    } else {
      result += roman[s[i]];
    }
  }
  return result;
}

medium

A. Accessing s[i+1] without checking bounds causes out-of-range error

B. Using map instead of unordered_map causes slow lookup

C. Result variable should be initialized to 1 instead of 0

D. The subtraction logic is reversed

Solution

1. Step 1: Analyze loop and index usage

   The loop runs from i = 0 to s.size() - 1, but inside the loop it accesses s[i+1] without checking if i+1 is within bounds.

2. Step 2: Identify potential runtime error

   When i is the last index, s[i+1] is out of range, causing undefined behavior or crash.

3. Final Answer:

   Accessing s[i+1] without checking bounds causes out-of-range error -> Option A

4. Quick Check:

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

Hint: Always check index bounds before accessing next element [OK]

Common Mistakes:

• Ignoring index bounds causing runtime errors
• Incorrect initialization of result
• Misunderstanding subtraction logic

5. Given the Roman numeral string "XLIX", which of the following C++ code snippets correctly converts it to an integer?

hard

A. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
total += roman[s[i]];
}
return total;
}

B. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (roman[s[i]] > roman[s[i+1]]) {
total += roman[s[i]];
} else {
total -= roman[s[i]];
}
}
return total;
}

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

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

Solution

1. Step 1: Check correct subtraction logic with bounds check

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } correctly checks if next character exists and if current value is less than next, then subtracts; else adds.

2. Step 2: Verify other options for errors

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (roman[s[i]] > roman[s[i+1]]) { total += roman[s[i]]; } else { total -= roman[s[i]]; } } return total; } reverses logic and lacks bounds check; int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = s.size() - 1; i >= 0; --i) { if (roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } accesses s[i+1] when i is last index (out-of-bounds); int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { total += roman[s[i]]; } return total; } adds all values ignoring subtraction rule.

3. Final Answer:

   The code in Step 1 -> Option D

4. Quick Check:

   Check bounds and subtract if current < next [OK]

Hint: Check next char exists before subtracting current [OK]

Common Mistakes:

• Not checking index bounds before accessing s[i+1]
• Reversing subtraction logic
• Ignoring subtraction rule completely