Roman to Integer Conversion in DSA Python - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total=0 and index=0

↓

Read current Roman symbol

↓

Check if next symbol exists and is larger?

↓

Subtract current

↓

Move index by 2

Back to start if index < length↓

Return total

↩Back to start if index < length

We read each Roman symbol, decide to add or subtract based on the next symbol, then move forward until all symbols are processed.

Execution Sample

DSA Python

def romanToInt(s):
    values = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    total = 0
    i = 0
    while i < len(s):
        if i+1 < len(s) and values[s[i]] < values[s[i+1]]:
            total += values[s[i+1]] - values[s[i]]
            i += 2
        else:
            total += values[s[i]]
            i += 1
    return total

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

Execution Table

Step	Operation	Index i	Current Symbol	Next Symbol	Condition (next larger?)	Action	Total	Visual State
1	Start	0	M	C	No	Add 1000	1000	M(1000)
2	Move i by 1	1	C	M	Yes	Add 900 (1000-100)	1900	M(1000) -> CM(900)
3	Move i by 2	3	X	C	Yes	Add 90 (100-10)	1990	M(1000) -> CM(900) -> XC(90)
4	Move i by 2	5	I	V	Yes	Add 4 (5-1)	1994	M(1000) -> CM(900) -> XC(90) -> IV(4)
5	Move i by 2	7	-	-	-	End	1994	Final total 1994

💡 Index i reached length of string, all symbols processed

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
total	0	1000	1900	1990	1994	1994
i	0	1	3	5	7	7

Key Moments - 3 Insights

Why do we check if the next symbol is larger before adding or subtracting?

Because Roman numerals use subtraction when a smaller symbol is before a larger one (like IV = 4). The execution_table rows 2, 3, and 4 show this check deciding to subtract current from next.

Why do we move the index by 2 when the next symbol is larger?

Because we process two symbols together as one number (like IV). The execution_table rows 2, 3, and 4 show i increasing by 2 after such pairs.

What happens if the next symbol does not exist or is not larger?

We simply add the value of the current symbol and move index by 1, as shown in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total after step 3?

A 1900

B 1990

C 1000

D 1994

💡 Hint

Check the 'Total' column in execution_table row 3

At which step does the index i move by 2 for the first time?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Action' and 'Index i' columns in execution_table rows 1 and 2

If the input was 'III', how would the index i change?

A Increase by 2 each time

B Stay the same

C Increase by 1 each time

D Increase by 3 each time

💡 Hint

Refer to variable_tracker for i increments when next symbol is not larger (like step 1)

Concept Snapshot

Roman to Integer Conversion:
- Read symbols left to right
- If next symbol is larger, subtract current from next and add result
- Move index by 2 when subtracting, else by 1
- Sum all values for final integer
- Handles special subtractive pairs like IV, IX, CM

Full Transcript

This visual trace shows how to convert Roman numerals to integers by reading each symbol and deciding whether to add or subtract based on the next symbol. We start with total zero and index zero. At each step, we check if the next symbol exists and is larger. If yes, we subtract the current symbol's value from the next and add that to total, moving index by two. Otherwise, we add the current symbol's value and move index by one. This continues until all symbols are processed. The example 'MCMXCIV' is traced step-by-step, showing total and index changes. Key moments clarify why we check the next symbol and how index moves. Quizzes test understanding of total values and index increments. The snapshot summarizes the conversion rules clearly.