Solving the ‘Roman to Integer’ Problem on LeetCode — Swift Solutions Walkthrough

Image Source

Introduction

Converting Roman numerals to integers is a classic challenge often encountered in programming interviews and competitive coding. This article provides a detailed walkthrough of three distinct Swift solutions to tackle the ‘Roman to Integer’ problem on LeetCode. Each method offers unique insights into effective problem-solving strategies in Swift. By the end of this guide, you will have a thorough understanding of the mechanics behind each approach, as well as their efficiency and effectiveness. Detailed comments and step-by-step explanations for each method are provided after the conclusion, helping you grasp the practical implementation and nuances of these solutions.

Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M, with respective values of 1, 5, 10, 50, 100, 500, and 1000. Given a roman numeral, the task is to convert it to an integer.

Function Signature in Swift:

class Solution {
    func romanToInt(_ s: String) -> Int {
        
    }
}

Examples:

• Input: s = “III”, Output: 3
• Input: s = “LVIII”, Output: 58
• Input: s = “MCMXCIV”, Output: 1994

Solution 1: Iterative Approach

This simple approach involves iterating over the string from left to right, adding the values of the corresponding Roman numerals. If a numeral with a smaller value precedes a larger value, the smaller value is subtracted.

Swift Code:

class Solution {
    func romanToInt(_ s: String) -> Int {
        let value: [Character: Int] = [
            "I": 1, "V": 5, "X": 10, "L": 50,
            "C": 100, "D": 500, "M": 1000
        ]
        var sum = 0
        var prevValue = 0
        
        for char in s {
            let currentValue = value[char] ?? 0
            sum += (currentValue > prevValue) ? (currentValue - 2 * prevValue) : currentValue
            prevValue = currentValue
        }
        return sum
    }
}

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the input string. This complexity arises because the algorithm loops through each character in the string exactly once. During each iteration, it performs a constant-time lookup in the dictionary to retrieve the corresponding integer value for the Roman numeral character. The subsequent arithmetic operations (comparison, addition, and subtraction) performed during each iteration are also executed in constant time. Thus, the overall time complexity remains linear relative to the length of the string.
• Space Complexity: O(1), this constant space usage is because, aside from the storage used for the input and a few auxiliary variables (sum and prevValue), no additional space that scales with the input size is used. The dictionary used to store the Roman numeral values is of fixed size, containing only seven entries (one for each Roman numeral symbol). Therefore, the space required for the dictionary does not grow with the size of the input string, ensuring constant space complexity.

Solution 2: Direct Mapping with Array

This optimized approach maps each Roman numeral directly using an array for fast lookup, thus avoiding the overhead of dictionary operations.

Swift Code:

class Solution {
    func romanToInt(_ s: String) -> Int {
        var values = [Int](repeating: 0, count: 256)
        values[Int(Character("I").asciiValue!)] = 1
        values[Int(Character("V").asciiValue!)] = 5
        values[Int(Character("X").asciiValue!)] = 10
        values[Int(Character("L").asciiValue!)] = 50
        values[Int(Character("C").asciiValue!)] = 100
        values[Int(Character("D").asciiValue!)] = 500
        values[Int(Character("M").asciiValue!)] = 1000
        
        var sum = 0
        var prevValue = 0
        
        for char in s {
            let currentValue = values[Int(char.asciiValue!)]
            sum += (currentValue > prevValue) ? (currentValue - 2 * prevValue) : currentValue
            prevValue = currentValue
        }
        return sum
    }
}

Time and Space Complexity

• Time Complexity: O(n), since it involves a single pass through the string. Each character of the string is accessed once, and its corresponding integer value is retrieved from a pre-filled array based on the character’s ASCII value. This retrieval is a constant-time operation (O(1)), as array indexing in Swift is an O(1) operation. The subsequent arithmetic operations (comparison, addition, and subtraction) performed during each iteration are also executed in constant time. Thus, the overall time complexity remains linear relative to the length of the string.
• Space Complexity: O(1), the algorithm uses a fixed-size array of 256 integers (assuming extended ASCII character set for generality), which is initialized with zeros. The size of this array does not depend on the input size but is fixed regardless of the input string’s length. No additional space that scales with the size of the input is used, ensuring constant space complexity. The auxiliary variables (sum and prevValue) also do not contribute to the space complexity beyond a constant factor.

Solution 3: Using Dictionary for Flexibility

Leveraging a dictionary, this approach provides a balance between readability and performance, making the code more adaptable to changes.

Swift Code:

class Solution {
    func romanToInt(_ s: String) -> Int {
        let roman: [Character: Int] = [
            "I": 1, "V": 5, "X": 10, "L": 50,
            "C": 100, "D": 500, "M": 1000
        ]
        
        var sum = 0
        var prevValue = roman[s.first!] ?? 0
        
        for char in s.dropFirst() {
            let currentValue = roman[char] ?? 0
            sum += (currentValue > prevValue) ? -prevValue : prevValue
            prevValue = currentValue
        }
        sum += prevValue
        return sum
    }
}

Time and Space Complexity

• Time Complexity: O(n), with n being the length of the string. While dictionary operations (insertions and lookups) generally have an average time complexity of O(1), in this context, the dictionary is pre-filled with only seven key-value pairs (corresponding to the Roman numerals), ensuring that lookups take constant time. The loop processes each character of the string exactly once, performing operations similar to the previous solutions. Therefore, the overall time complexity remains linear relative to the length of the string.
• Space Complexity: O(1), the dictionary used to store the Roman numeral mappings is of constant size, containing only seven entries. The space required for the dictionary does not grow with the size of the input string, ensuring constant space complexity. The additional variables (sum and prevValue) used for computing the total are minimal and do not increase with the size of the input. Thus, the space complexity remains constant regardless of the input size.

Conclusion and Comparison

On analysis, all three Swift methods demonstrate similar time complexities, as each involves a single traversal of the input string. The space complexity is also comparable across the solutions due to the minimal auxiliary space used for variables and, in the case of Solution 3, a dictionary for storing numeral values.

Solution 1: Iterative Approach with Dictionary

Strengths:

• Simplicity and Readability: This approach is straightforward and easy to understand, making it a good choice for quick implementation and readability.
• Separation of Concerns: Using a dictionary to store the numeral-to-value mappings eliminates the need for repeatedly coding the conversion logic, thus providing a clear separation of concerns.

Weaknesses:

• Performance: While the lookup time for each character in a dictionary is constant, there might be slight overhead compared to a direct array access approach.
• Potential for Errors: The logic involving subtracting twice the previous value when the current value is greater can be slightly harder to follow at a glance, potentially leading to implementation errors.

Solution 2: Direct Mapping with Array

Strengths:

• Efficiency: By directly embedding the numeral-to-integer mapping within the loop using an array for direct access, this method eliminates the need for a separate mapping structure like a dictionary. This can potentially enhance performance due to reduced overhead from typical map operations.
• Constant Time Access: The array access time is constant and generally faster than other lookup methods, making this approach very efficient.

Weaknesses:

• Maintainability: The static nature of the array mapping could make the method less maintainable if updates or extensions to the numeral set are required. Any changes would necessitate modifications directly within the array initialization.
• Memory Usage: Although the space complexity is constant, using an array of size 256 (to account for all ASCII characters) might be considered overkill, as only a few entries are actually used.

Solution 3: Using Dictionary for Flexibility

Strengths:

• Readability and Maintainability: This solution stands out in terms of readability and maintainability. By using a dictionary to store numeral values, it not only makes the code cleaner but also separates the numeral-to-value mapping from the logic of computing the total. This separation simplifies understanding and maintaining the code.
• Flexibility: The use of a dictionary improves adaptability, allowing for easier adjustments and extensions to numeral mappings. For instance, if additional symbols or composite numerals need to be supported in the future, updating the dictionary would be straightforward.

Weaknesses:

• Performance: While the lookups in the dictionary are constant time due to the small number of entries, there might be a slight overhead compared to direct array access. However, this is generally negligible given the small and fixed size of the dictionary.
• Complexity: The code might appear slightly more complex than the direct array approach due to the additional dictionary structure, although this is often offset by the improved readability and maintainability.

Summary

• Solution 1 offers a simple and readable approach using a dictionary, making it easy to understand and implement quickly. However, it may have slight performance overheads compared to array access.
• Solution 2 provides an efficient solution with constant time access using an array, making it highly performant. However, its maintainability is less flexible due to the static nature of the array.
• Solution 3 strikes a balance between readability, maintainability, and performance. Using a dictionary for numeral values, it offers flexibility for future modifications while maintaining clear and understandable code.

The choice of solution depends on the specific requirements of readability, performance, and maintainability. Each approach has its own merits and can be chosen based on the context of the problem at hand. While the second solution offers efficiency and the first ensures a clean separation of concerns, the third solution provides the best combination of readability, maintainability, and ease of modification. The use of a dictionary in Solution 3 reflects a modern approach to handling mappings, which is often preferred in software development for its flexibility and clarity.

• LeetCode — Roman to Integer
• Swift Documentation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated and helps keep content like this free!

Also check out my other Leetcode Walkthrough Lists:

• Two Sum Problem
• Palindrome Number Problem

Commented Code and Step-by-Step Explanations

Solution 1: Iterative Approach Using Dictionary

In this approach, we use an iterative method to traverse the input Roman numeral string. We maintain a running total of the integer values of the Roman numerals encountered. The subtraction cases are managed by comparing the current numeral with the previous one and subtracting twice the previous value if it is smaller.

class Solution {
    func romanToInt(_ s: String) -> Int {
        // Dictionary to map Roman numerals to their integer values
        let value: [Character: Int] = [
            "I": 1, "V": 5, "X": 10, "L": 50,
            "C": 100, "D": 500, "M": 1000
        ]
        var sum = 0  // Initialize sum to store the total value
        var prevValue = 0  // Initialize prevValue to store the value of the previous Roman numeral
        
        // Iterate through each character in the string
        for char in s {
            // Get the integer value of the current Roman numeral
            let currentValue = value[char] ?? 0
            // If the current value is greater than the previous value, subtract twice the previous value
            // Otherwise, add the current value to the sum
            sum += (currentValue > prevValue) ? (currentValue - 2 * prevValue) : currentValue
            // Update prevValue with the current value
            prevValue = currentValue
        }
        return sum  // Return the total sum
    }
}

Step-by-Step Explanation

1. Step 1: Initialize the total sum (sum) and the value of the previous Roman numeral (prevValue) to 0.
2. Step 2: Create a dictionary (value) that maps each Roman numeral character to its corresponding integer value.
3. Step 3: Iterate through each character (char) in the input Roman string (s).
4. Step 4: Retrieve the integer value of the current Roman numeral (currentValue) from the dictionary.
5. Step 5: Check if the current value is greater than the previous value. If true, subtract twice the previous value from the current value and add the result to the sum. Otherwise, add the current value to the sum.
6. Step 6: Update prevValue with the current value for the next iteration.
7. Step 7: Return the final sum as the result.

Solution 2: Direct Mapping with Array

This method directly maps each Roman numeral character to its integer value using an array. The input string is iterated through, adding values to calculate the total integer value. Subtraction scenarios are handled similarly to the first solution.

class Solution {
    func romanToInt(_ s: String) -> Int {
        // Initialize an array of size 256 (assuming extended ASCII character set) with all elements set to 0
        var values = [Int](repeating: 0, count: 256)
        // Set the corresponding integer values for each Roman numeral character in the array
        values[Int(Character("I").asciiValue!)] = 1
        values[Int(Character("V").asciiValue!)] = 5
        values[Int(Character("X").asciiValue!)] = 10
        values[Int(Character("L").asciiValue!)] = 50
        values[Int(Character("C").asciiValue!)] = 100
        values[Int(Character("D").asciiValue!)] = 500
        values[Int(Character("M").asciiValue!)] = 1000
        
        var sum = 0  // Initialize sum to store the total value
        var prevValue = 0  // Initialize prevValue to store the value of the previous Roman numeral
        
        // Iterate through each character in the string
        for char in s {
            // Get the integer value of the current Roman numeral using the array
            let currentValue = values[Int(char.asciiValue!)]
            // If the current value is greater than the previous value, subtract twice the previous value
            // Otherwise, add the current value to the sum
            sum += (currentValue > prevValue) ? (currentValue - 2 * prevValue) : currentValue
            // Update prevValue with the current value
            prevValue = currentValue
        }
        return sum  // Return the total sum
    }
}

Step-by-Step Explanation

• Step 1: Initialize the total sum (sum) and the value of the previous Roman numeral (prevValue) to 0.
• Step 2: Create an array (values) of size 256 (assuming extended ASCII character set) and initialize all elements to 0.
• Step 3: Set the corresponding integer values for each Roman numeral character in the array.
• Step 4: Iterate through each character (char) in the input string (s), using the array to directly map each Roman numeral character to its integer value (currentValue).
• Step 5: Check if the current value is greater than the previous value. If true, subtract twice the previous value; otherwise, add the current value to the sum.
• Step 6: Update prevValue with the current value for the next iteration.
• Step 7: Return the computed total (sum).

Solution 3: Using Dictionary for Flexibility

This solution leverages a dictionary to establish a mapping between Roman numerals and their corresponding integer values. The iteration through the string involves looking up values in the dictionary to calculate the total integer value. Subtraction cases are handled by comparing the current numeral with the previous one.

class Solution {
    func romanToInt(_ s: String) -> Int {
        // Create a dictionary to store the mappings of Roman numerals to their integer values
        let roman: [Character: Int] = [
            "I": 1, "V": 5, "X": 10, "L": 50,
            "C": 100, "D": 500, "M": 1000
        ]
        
        var sum = 0  // Initialize sum to store the total value
        // Initialize prevValue with the value of the first Roman numeral in the string
        var prevValue = roman[s.first!] ?? 0
        
        // Iterate through each character in the string starting from the second character
        for char in s.dropFirst() {
            // Get the integer value of the current Roman numeral from the dictionary
            let currentValue = roman[char] ?? 0
            // If the current value is greater than the previous value, subtract the previous value
            // Otherwise, add the previous value
            sum += (currentValue > prevValue) ? -prevValue : prevValue
            // Update prevValue with the current value
            prevValue = currentValue
        }
        // Add the last value of prevValue to sum
        sum += prevValue
        return sum  // Return the computed total
    }
}

Step-by-Step Explanation

1. Step 1: Create a dictionary (roman) to store the mappings of Roman numerals to their integer values.
2. Step 2: Populate the dictionary with mappings for each Roman numeral character.
3. Step 3: Initialize the total sum (sum) and the value of the first Roman numeral (prevValue) to the value of the first character in the string.
4. Step 4: Iterate through each subsequent character (char) in the input string (s).
5. Step 5: Look up the integer value of the current Roman numeral in the dictionary (currentValue).
6. Step 6: Check if the current value is greater than the previous value. If true, subtract the previous value; otherwise, add the previous value.
7. Step 7: Update prevValue with the current value for the next iteration.
8. Step 8: Add the last value of prevValue to sum.
9. Step 9: Return the computed total (sum).