0013_roman_to_integer.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Roman to Integer - LeetCode 13</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#13</span> Roman to Integer</h1>
            <p>Convert a Roman numeral to an integer.</p>
            <div class="problem-meta">
                <span class="meta-tag">Math</span>
                <span class="meta-tag">String</span>
                <span class="meta-tag">Easy</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0013_roman_to_integer/0013_roman_to_integer.py</code>
            </div>

        </div>



        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Read the numeral from left to right and add each symbol, except when a smaller symbol sits in front of a larger one, which means subtraction.</p>
            <ul>
                <li><strong>Look ahead:</strong> Compare the current value with the next one</li>
                <li><strong>Subtract pair:</strong> If current &lt; next, add <code>next - current</code> and skip both</li>
                <li><strong>Otherwise:</strong> Add the current value and move one step</li>
            </ul>
        </div>

        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            <div class="controls">
                <button id="stepBtn">Step</button>
                <button id="autoBtn">Auto Run</button>
                <button id="resetBtn">Reset</button>
            </div>
            <svg id="mainSvg" width="800" height="380"></svg>
            <div class="status-message" id="status">Click "Step" to convert Roman to integer</div>
        </div>

        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List

"""
LeetCode Roman to Integer

Problem from LeetCode: https://leetcode.com/problems/roman-to-integer/

Description:
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I            1
V            5
X            10
L            50
C            100
D            500
M            1000

For example, 2 is written as II in Roman numeral, just two ones added together. 
12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. 
Instead, the number four is written as IV. Because the one is before the five we subtract it making four. 
The same principle applies to the number nine, which is written as IX.

There are six instances where subtraction is used:
- I can be placed before V (5) and X (10) to make 4 and 9. 
- X can be placed before L (50) and C (100) to make 40 and 90. 
- C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3.

Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
"""

class Solution:
    def roman_to_int(self, s: str) -&gt; int:
        """
        Convert a Roman numeral to an integer.
        
        Args:
            s: A string representing a valid Roman numeral in the range [1, 3999]
            
        Returns:
            int: The integer value of the Roman numeral
        """
        # Define the mapping of Roman numerals to integers
        values = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        
        total = 0
        i = 0
        
        while i &lt; len(s):
            # If this is the subtractive case
            if i + 1 &lt; len(s) and values[s[i]] &lt; values[s[i + 1]]:
                total += values[s[i + 1]] - values[s[i]]
                i += 2
            # Else this is regular case
            else:
                total += values[s[i]]
                i += 1
                
        return total
    
    def roman_to_int_simpler(self, s: str) -&gt; int:
        """
        A simpler implementation that processes the string from right to left.
        
        Args:
            s: A string representing a valid Roman numeral
            
        Returns:
            int: The integer value of the Roman numeral
        """
        values = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        
        total = 0
        prev_value = 0
        
        # Process the string from right to left
        for char in reversed(s):
            current_value = values[char]
            # If current value is greater than or equal to previous value, add it
            if current_value &gt;= prev_value:
                total += current_value
            # Otherwise, subtract it (handles cases like IV, IX, etc.)
            else:
                total -= current_value
            prev_value = current_value
            
        return total


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    s1 = "III"
    result1 = solution.roman_to_int(s1)
    print(f"Example 1: '{s1}' -&gt; {result1}")  # Expected output: 3
    
    # Example 2
    s2 = "LVIII"
    result2 = solution.roman_to_int(s2)
    print(f"Example 2: '{s2}' -&gt; {result2}")  # Expected output: 58
    
    # Example 3
    s3 = "MCMXCIV"
    result3 = solution.roman_to_int(s3)
    print(f"Example 3: '{s3}' -&gt; {result3}")  # Expected output: 1994
    
    # Additional examples
    s4 = "MMXXIII"
    result4 = solution.roman_to_int(s4)
    print(f"Example 4: '{s4}' -&gt; {result4}")  # Expected output: 2023
    
    # Compare with simpler implementation
    print("\nUsing simpler approach (right to left):")
    print(f"Example 1: '{s1}' -&gt; {solution.roman_to_int_simpler(s1)}")
    print(f"Example 2: '{s2}' -&gt; {solution.roman_to_int_simpler(s2)}")
    print(f"Example 3: '{s3}' -&gt; {solution.roman_to_int_simpler(s3)}")
</pre>
            </div>
        </div>
    </div>

    <script>
        const romanValues = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000};
        const testCases = ["MCMXCIV", "III", "LVIII", "IX"];
        
        let s = "MCMXCIV";
        let i;
        let total = 0;
        let prevValue = 0;
        let phase = 'processing';
        
        const width = 800, height = 380;
        const svg = d3.select("#mainSvg");
        let autoTimer = null;
        let autoRunning = false;

        function draw() {
            svg.selectAll("*").remove();

            const cellWidth = 60, startX = 100, startY = 80;

            // Title
            svg.append("text")
                .attr("x", width / 2).attr("y", 30)
                .attr("text-anchor", "middle")
                .attr("font-weight", "bold")
                .text(`Converting "${s}" to Integer (Right to Left)`);

            // Draw Roman characters
            for (let idx = 0; idx < s.length; idx++) {
                const x = startX + idx * cellWidth;
                const isProcessed = idx > i;
                const isCurrent = idx === i;

                svg.append("rect")
                    .attr("x", x).attr("y", startY)
                    .attr("width", cellWidth - 5).attr("height", 55)
                    .attr("rx", 8)
                    .attr("fill", isCurrent ? "#fef3c7" : (isProcessed ? "#d1fae5" : "#e3f2fd"))
                    .attr("stroke", isCurrent ? "#f59e0b" : (isProcessed ? "#10b981" : "#1976d2"))
                    .attr("stroke-width", isCurrent ? 3 : 2);

                svg.append("text")
                    .attr("x", x + (cellWidth - 5) / 2)
                    .attr("y", startY + 30)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "26px")
                    .attr("font-weight", "bold")
                    .text(s[idx]);

                svg.append("text")
                    .attr("x", x + (cellWidth - 5) / 2)
                    .attr("y", startY + 48)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "12px")
                    .attr("fill", "#666")
                    .text(romanValues[s[idx]]);
            }

            // Direction arrow
            svg.append("text")
                .attr("x", startX + s.length * cellWidth + 20)
                .attr("y", startY + 30)
                .attr("font-size", "24px")
                .text("←");

            svg.append("text")
                .attr("x", startX + s.length * cellWidth + 50)
                .attr("y", startY + 35)
                .attr("font-size", "12px")
                .attr("fill", "#666")
                .text("Direction");

            // Variables display
            const varsY = 180;
            const vars = [
                { name: "Current Value", value: i >= 0 ? romanValues[s[i]] : "-" },
                { name: "Previous Value", value: prevValue },
                { name: "Total", value: total }
            ];

            vars.forEach((v, idx) => {
                const x = 100 + idx * 200;
                
                svg.append("rect")
                    .attr("x", x).attr("y", varsY)
                    .attr("width", 160).attr("height", 60)
                    .attr("rx", 10)
                    .attr("fill", idx === 2 ? "#e8f5e9" : "#f5f5f5")
                    .attr("stroke", idx === 2 ? "#4caf50" : "#ddd");

                svg.append("text")
                    .attr("x", x + 80).attr("y", varsY + 22)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "12px")
                    .attr("fill", "#666")
                    .text(v.name);

                svg.append("text")
                    .attr("x", x + 80).attr("y", varsY + 48)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "22px")
                    .attr("font-weight", "bold")
                    .text(v.value);
            });

            // Logic explanation
            if (i >= 0 && phase === 'processing') {
                const curr = romanValues[s[i]];
                const logicY = 280;
                const isSubtraction = curr < prevValue;

                svg.append("rect")
                    .attr("x", 150).attr("y", logicY)
                    .attr("width", 500).attr("height", 45)
                    .attr("rx", 8)
                    .attr("fill", isSubtraction ? "#fee2e2" : "#d1fae5")
                    .attr("stroke", isSubtraction ? "#ef4444" : "#10b981");

                svg.append("text")
                    .attr("x", 400).attr("y", logicY + 28)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "14px")
                    .text(isSubtraction 
                        ? `${curr} < ${prevValue}: SUBTRACT → total = ${total} - ${curr}`
                        : `${curr} ≥ ${prevValue}: ADD → total = ${total} + ${curr}`);
            }

            // Final result
            if (phase === 'done') {
                svg.append("rect")
                    .attr("x", width / 2 - 120).attr("y", 310)
                    .attr("width", 240).attr("height", 55)
                    .attr("rx", 12)
                    .attr("fill", "#d1fae5").attr("stroke", "#10b981")
                    .attr("stroke-width", 2);

                svg.append("text")
                    .attr("x", width / 2).attr("y", 345)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "24px")
                    .attr("font-weight", "bold")
                    .attr("fill", "#10b981")
                    .text(`${s} = ${total}`);
            }
        }

        function step() {
            if (phase === 'done') return false;

            if (i < 0) {
                phase = 'done';
                document.getElementById("status").textContent = `Done! ${s} = ${total}`;
                draw();
                return false;
            }

            const curr = romanValues[s[i]];
            
            if (curr >= prevValue) {
                total += curr;
                document.getElementById("status").textContent = 
                    `'${s[i]}' (${curr}) ≥ prev (${prevValue}): Add ${curr}. Total = ${total}`;
            } else {
                total -= curr;
                document.getElementById("status").textContent = 
                    `'${s[i]}' (${curr}) < prev (${prevValue}): Subtract ${curr}. Total = ${total}`;
            }

            prevValue = curr;
            i--;

            draw();
            return i >= 0;
        }

        function reset() {
            i = s.length - 1;
            total = 0;
            prevValue = 0;
            phase = 'processing';
            if (autoTimer) clearInterval(autoTimer);
            autoRunning = false;
            document.getElementById("autoBtn").textContent = "Auto Run";
            document.getElementById("status").textContent = 'Click "Step" to convert Roman to integer';
            draw();
        }

        function autoRun() {
            if (autoRunning) {
                clearInterval(autoTimer);
                autoRunning = false;
                document.getElementById("autoBtn").textContent = "Auto Run";
            } else {
                autoRunning = true;
                document.getElementById("autoBtn").textContent = "Pause";
                autoTimer = setInterval(() => {
                    if (!step()) {
                        clearInterval(autoTimer);
                        autoRunning = false;
                        document.getElementById("autoBtn").textContent = "Auto Run";
                    }
                }, 800);
            }
        }

        document.getElementById("stepBtn").addEventListener("click", step);
        document.getElementById("autoBtn").addEventListener("click", autoRun);
        document.getElementById("resetBtn").addEventListener("click", reset);

        reset();
    </script>
</body>
</html>