Roman to Integer Conversion in DSA Javascript

Mental Model

Roman numerals are letters that represent numbers. We add or subtract values based on their order to get the total number.

Analogy: Think of reading a price tag where some discounts apply if a smaller number comes before a bigger number, so you subtract instead of add.

R O M A N -> I N T E G E R

Example: M -> D -> C -> X -> I
Values: 1000 -> 500 -> 100 -> 10 -> 1

Dry Run Walkthrough

Input: Roman numeral: "MCMIV"

Goal: Convert the Roman numeral "MCMIV" to its integer value.

Step 1: Read 'M' (1000), add 1000 to total

Total = 1000

Why: Start with the first symbol's value

Step 2: Read 'C' (100), next is 'M' (1000), since 100 < 1000, subtract 100

Total = 1000 - 100 = 900

Why: Smaller before bigger means subtract

Step 3: Read 'M' (1000), next is 'I' (1), since 1000 > 1, add 1000

Total = 900 + 1000 = 1900

Why: Bigger or equal means add

Step 4: Read 'I' (1), next is 'V' (5), since 1 < 5, subtract 1

Total = 1900 - 1 = 1899

Why: Smaller before bigger means subtract

Step 5: Read 'V' (5), no next symbol, add 5

Total = 1899 + 5 = 1904

Why: Last symbol always adds

Result:

Total = 1904

Annotated Code

DSA Javascript

class RomanToInteger {
  constructor() {
    this.values = {
      'I': 1, 'V': 5, 'X': 10, 'L': 50,
      'C': 100, 'D': 500, 'M': 1000
    };
  }

  convert(roman) {
    let total = 0;
    for (let i = 0; i < roman.length; i++) {
      const currentVal = this.values[roman[i]];
      const nextVal = i + 1 < roman.length ? this.values[roman[i + 1]] : 0;

      if (currentVal < nextVal) {
        total -= currentVal; // subtract when smaller before bigger
      } else {
        total += currentVal; // add otherwise
      }
    }
    return total;
  }
}

const converter = new RomanToInteger();
const input = "MCMIV";
const result = converter.convert(input);
console.log(result);

const currentVal = this.values[roman[i]];

Get current Roman symbol's value

const nextVal = i + 1 < roman.length ? this.values[roman[i + 1]] : 0;

Look ahead to next symbol's value or 0 if none

if (currentVal < nextVal) { total -= currentVal; } else { total += currentVal; }

Subtract if smaller before bigger, else add

Output

1904

Complexity Analysis

Time: O(n) because we scan each Roman symbol once

Space: O(1) because the map of Roman values is fixed size

vs Alternative: This is more efficient than repeatedly searching or converting substrings, which could be slower

Edge Cases

Empty string

Returns 0 since no symbols to convert

DSA Javascript

for (let i = 0; i < roman.length; i++) {

Single symbol like 'V'

Returns the value of that symbol directly

DSA Javascript

const nextVal = i + 1 < roman.length ? this.values[roman[i + 1]] : 0;

Symbols in descending order like 'XVII'

All values add up since no smaller before bigger

DSA Javascript

if (currentVal < nextVal) { total -= currentVal; } else { total += currentVal; }

When to Use This Pattern

When you see a problem asking to convert Roman numerals to numbers, use the subtract-if-smaller-before-bigger pattern to handle special cases.

Common Mistakes

Mistake: Always adding values without checking the next symbol
Fix: Compare current and next symbol values to decide subtract or add

Mistake: Not handling the last symbol correctly
Fix: Use 0 as next value for last symbol so it always adds

Summary

Converts Roman numeral strings to integer numbers by adding or subtracting symbol values.

Use when you need to interpret Roman numerals as normal numbers.

Remember to subtract when a smaller value comes before a bigger one, otherwise add.

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