Roman to Integer Conversion in DSA Typescript - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total = 0

↓

Read current Roman symbol

↓

Compare with next symbol

↓

Current < Next?

Yes→Subtract current value from total

↓

Add current value to total

↓

Move to next symbol

↓

Repeat until end of string

↓

Return total as integer

We read each Roman symbol, compare it with the next one to decide if we add or subtract its value, then move forward until all symbols are processed.

Execution Sample

DSA Typescript

function romanToInt(s: string): number {
  const map = new 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++) {
    if(map.get(s[i])! < map.get(s[i+1] || 'I')!) total -= map.get(s[i])!;
    else total += map.get(s[i])!;
  }
  return total;
}

This code converts a Roman numeral string to an integer by adding or subtracting values based on the next symbol.

Execution Table

Step	Operation	Current Symbol	Next Symbol	Compare	Add or Subtract	Total After Operation	Visual State
1	Read symbol	M	C	1000 >= 100	Add 1000	1000	M(1000)
2	Read symbol	C	M	100 < 1000	Subtract 100	900	M(1000) -> C(-100)
3	Read symbol	M	X	1000 >= 10	Add 1000	1900	M(1000) -> C(-100) -> M(1000)
4	Read symbol	X	I	10 >= 1	Add 10	1910	M(1000) -> C(-100) -> M(1000) -> X(10)
5	Read symbol	I	V	1 < 5	Subtract 1	1909	M(1000) -> C(-100) -> M(1000) -> X(10) -> I(-1)
6	Read symbol	V		5 >= 0	Add 5	1914	M(1000) -> C(-100) -> M(1000) -> X(10) -> I(-1) -> V(5)
7	End of string					1914	Final total

💡 Reached end of string, total is 1914

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
total	0	1000	900	1900	1910	1909	1914	1914
i	0	1	2	3	4	5	6	6
currentSymbol		M	C	M	X	I	V
nextSymbol		C	M	X	I	V

Key Moments - 3 Insights

Why do we subtract the current value when it is less than the next symbol?

Because in Roman numerals, a smaller value before a larger one means subtraction, as shown in steps 2 and 5 where 'C' and 'I' are subtracted.

What happens when the current symbol is the last one in the string?

Since there is no next symbol, we treat the next value as zero or undefined, so we always add the last symbol's value, as in step 6 with 'V'.

Why do we compare current symbol's value with the next symbol's value?

This comparison decides if we add or subtract the current value, ensuring correct conversion, as seen in every step of the execution table.

Visual Quiz - 3 Questions

Look at the execution table, what is the total after processing the third symbol?

A 900

B 1900

C 1000

D 1910

💡 Hint

Check the 'Total After Operation' column at Step 3 in the execution table.

At which step does the code subtract the value of the current symbol?

A Step 1

B Step 4

C Step 2

D Step 6

💡 Hint

Look for 'Subtract' in the 'Add or Subtract' column in the execution table.

If the input was 'IX', how would the total change after the first symbol?

A Add 1

B Subtract 1

C Add 10

D Subtract 10

💡 Hint

Refer to the logic where current symbol is less than next symbol, causing subtraction.

Concept Snapshot

Roman to Integer Conversion:
- Map each Roman symbol to its value.
- Traverse string left to right.
- If current < next, subtract current value.
- Else, add current value.
- Sum all to get integer.
- Return total at end.

Full Transcript

This visualization shows how to convert Roman numerals to integers by reading each symbol, comparing it with the next, and deciding to add or subtract its value. We start with total zero, then for each symbol, if its value is less than the next symbol's value, we subtract it; otherwise, we add it. This process continues until all symbols are processed, resulting in the final integer value. The example traced is 'MCMXIV' which converts to 1914.

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