Roman to Integer Conversion in DSA Typescript - 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 grows as the input gets longer.

How does the number of steps change when the Roman numeral string is bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function romanToInt(s: string): number {
  const map: Record = {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;
}
    

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

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 string length).

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 cases, the code might need to look ahead multiple characters, making it slower than linear."

[OK] Correct: The code only looks one character ahead each time, so it still processes each character once, keeping the time linear.

Interview Connect

Understanding this helps you show how to handle string processing efficiently, a common skill in coding challenges and interviews.

Self-Check

"What if we changed the code to use recursion instead of a loop? How would the time complexity change?"

Practice

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

easy

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

B. Multiply all symbol values together

C. Add values only if symbols are the same

D. Subtract all symbol values from 1000

Solution

1. Step 1: Understand Roman numeral rules

   Roman numerals are converted by adding values of symbols, but if a smaller value comes before a larger one, it is subtracted.

2. Step 2: Apply the rule to conversion

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

3. Final Answer:

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

4. Quick Check:

   Roman to integer = add/subtract values [OK]

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

Common Mistakes:

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

2. Which TypeScript syntax correctly defines a function to convert Roman numerals to integers?

easy

A. def romanToInt(s): return 0

B. function romanToInt(s: string): number { return 0; }

C. func romanToInt(s string) int { return 0 }

D. romanToInt = (s) => { return '0'; }

Solution

1. Step 1: Identify TypeScript function syntax

   TypeScript functions use the syntax: function name(params): returnType { body }

2. Step 2: Match correct syntax

   function romanToInt(s: string): number { return 0; } matches TypeScript syntax with parameter type and return type specified.

3. Final Answer:

   function romanToInt(s: string): number { return 0; } -> Option B

4. Quick Check:

   TypeScript function syntax = function romanToInt(s: string): number { return 0; } [OK]

Hint: Use 'function name(params: type): returnType' in TypeScript [OK]

Common Mistakes:

• Using Python or Go syntax in TypeScript
• Returning string instead of number
• Missing type annotations

3. What is the output of this TypeScript code?

function romanToInt(s: string): number {
  const map: {[key: string]: number} = {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. 11

B. 4

C. 9

D. Error

Solution

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

   For 'I' (1) and next 'X' (10), since 1 < 10, subtract 1. For 'X' (10), no next, add 10.

2. Step 2: Calculate total

   Total = -1 + 10 = 9.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   'IX' = 9 [OK]

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

Common Mistakes:

• Adding all values without subtraction
• Off-by-one error in loop
• Not handling last character correctly

4. Find the bug in this TypeScript code for Roman to Integer conversion:

function romanToInt(s: string): number {
  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. Return type should be string, not number

B. map object keys should be lowercase

C. Use 'var' instead of 'let' for i

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

Solution

1. Step 1: Check loop boundary

   The loop runs from i = 0 to i <= s.length, which causes s[i] to be undefined at last iteration.

2. Step 2: Correct loop condition

   Change to i < s.length to avoid accessing undefined index.

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-bounds access [OK]

Common Mistakes:

• Using <= instead of < in loops
• Wrong case for map keys
• Incorrect return type

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

function romanToInt(s: string): number {
  const map: {[key: string]: number} = {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('MCMXCIV'));

hard

A. 1994

B. 1904

C. 2004

D. 1494

Solution

1. Step 1: Break down 'MCMXCIV'

   M=1000, C=100, M=1000, X=10, C=100, I=1, V=5. Apply subtraction where smaller precedes larger.

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

   1000 (M) + (100 < 1000, subtract 100) + 1000 + (10 < 100, subtract 10) + 100 + (1 < 5, subtract 1) + 5 = 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option A

4. Quick Check:

   'MCMXCIV' = 1994 [OK]

Hint: Subtract smaller before larger, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Misreading symbol order
• Skipping last character