Roman to Integer Conversion in DSA Javascript - 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 length of the Roman numeral grows.

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.

function romanToInt(s) {
  const map = {I:1, V:5, X:10, L:50, C:100, D:500, M:1000};
  let total = 0;
  for (let i = 0; i < s.length; i++) {
    const current = map[s[i]];
    const next = map[s[i + 1]];
    if (next && current < next) {
      total -= current;
    } else {
      total += current;
    }
  }
  return total;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each character of the input string once.
• How many times: Exactly once for each character in the string (n times, where n is the string length).

How Execution Grows With Input

As the Roman numeral string gets longer, the number of steps grows directly with the 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 input size; doubling the input doubles the work.

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 we check the next character inside the loop, the time complexity is O(n²)."

[OK] Correct: We only look one step ahead each time, so each character is visited once, not repeatedly.

Interview Connect

Understanding how to analyze simple loops like this helps you explain your code clearly and shows you can reason about efficiency, a key skill in interviews.

Self-Check

"What if we changed the code to check pairs of characters at once instead of one by one? How would the time complexity change?"

Practice

1. What is the main rule to convert Roman numerals to integers?

easy

A. Subtract all values from the largest symbol

B. Add values of symbols, subtract if a smaller symbol is before a larger one

C. Add values only if symbols are the same

D. Multiply values of symbols in order

Solution

1. Step 1: Understand Roman numeral rules

   Roman numerals are added normally, but if a smaller numeral appears before a larger one, it is subtracted.

2. Step 2: Apply addition and subtraction rules

   For example, IV is 5 - 1 = 4, while VI is 5 + 1 = 6.

3. Final Answer:

   Add values of symbols, subtract if a smaller symbol is before a larger one -> Option B

4. Quick Check:

   Roman numeral rules = Add and subtract [OK]

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

Common Mistakes:

• Always adding without subtraction
• Multiplying values incorrectly
• Ignoring order of symbols

2. Which of the following is the correct JavaScript syntax to get the integer value of a Roman numeral character from a map object named romanMap?

easy

A. romanMap['V']

B. romanMap.get('V')

C. romanMap.V

D. romanMap('V')

Solution

1. Step 1: Identify the data structure type

   If romanMap is a plain JavaScript object, access values using square brackets with the key as a string.

2. Step 2: Choose correct syntax for object property access

   Using romanMap['V'] correctly accesses the value for key 'V'. romanMap.get('V') is for Map objects, not plain objects.

3. Final Answer:

   romanMap['V'] -> Option A

4. Quick Check:

   Object property access = romanMap['V'] [OK]

Hint: Use square brackets for object keys as strings [OK]

Common Mistakes:

• Using .get() on plain objects
• Using dot notation with string keys
• Calling object like a function

3. What will be the output of the following JavaScript code?

function romanToInt(s) {
  const map = {I:1, V:5, X:10, L:50, C:100, D:500, M:1000};
  let total = 0;
  for(let i = 0; i < s.length; i++) {
    const current = map[s[i]];
    const next = map[s[i+1]] || 0;
    if(current < next) {
      total -= current;
    } else {
      total += current;
    }
  }
  return total;
}
console.log(romanToInt('IX'));

medium

A. 9

B. 11

C. 1

D. Error

Solution

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

   For 'I' (1), next is 'X' (10), since 1 < 10, subtract 1 (total = -1). For 'X' (10), next is undefined (0), so add 10 (total = 9).

2. Step 2: Calculate final total

   Total after loop is 9, which is the integer value of 'IX'.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   'IX' = 9 [OK]

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

Common Mistakes:

• Adding all values without subtraction
• Ignoring next character check
• Off-by-one errors in loop

4. Find the error in this JavaScript function for Roman to Integer conversion:

function romanToInt(s) {
  const map = {I:1, V:5, X:10, L:50, C:100, D:500, M:1000};
  let total = 0;
  for(let i = 0; i <= s.length; i++) {
    const current = map[s[i]];
    const next = map[s[i+1]] || 0;
    if(current < next) {
      total -= current;
    } else {
      total += current;
    }
  }
  return total;
}

medium

A. Use '==' instead of '<' in if condition

B. map object keys should be lowercase

C. total should be initialized to 1

D. Loop condition should be i < s.length, not i <= s.length

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= s.length, which means it accesses s[s.length], an undefined index causing current to be undefined.

2. Step 2: Correct loop condition

   Changing loop condition to i < s.length prevents accessing out-of-bound index and avoids errors.

3. Final Answer:

   Loop condition should be i < s.length, not i <= s.length -> Option D

4. Quick Check:

   Loop boundary off-by-one error fixed [OK]

Hint: Use i < length to avoid out-of-bound errors [OK]

Common Mistakes:

• Using <= instead of < in loops
• Wrong case for map keys
• Incorrect comparison operators

5. Given the Roman numeral string 'MCMXCIV', what integer should the conversion function return?

hard

A. 2004

B. 1904

C. 1994

D. 1094

Solution

1. Step 1: Break down the Roman numeral 'MCMXCIV'

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

2. Step 2: Add all parts

   1000 + 900 + 90 + 4 = 1994 total.

3. Final Answer:

   1994 -> Option C

4. Quick Check:

   'MCMXCIV' = 1994 [OK]

Hint: Identify subtractive pairs and sum all values [OK]

Common Mistakes:

• Adding all numerals without subtraction
• Misreading subtractive pairs
• Confusing similar numerals