Leetcode 13: Roman to Integer

1. Problem Statement (Simple Explanation):

You are given a valid Roman numeral string s (value in [1, 3999]).

You must convert it to its integer value.

Roman symbols and values:

Roman numerals are usually written from largest to smallest left to right, except for specific subtractive cases:

IV = 4 (5 − 1)
IX = 9 (10 − 1)
XL = 40 (50 − 10)
XC = 90 (100 − 10)
CD = 400 (500 − 100)
CM = 900 (1000 − 100)

2. Examples:

Example 1:

Input: s = "III"

Output: 3

Explanation: III = 1 + 1 + 1 = 3.

Example 2:

Input: s = "LVIII"

Output: 58

Explanation:

L = 50
V = 5
III = 3
Total = 50 + 5 + 3 = 58.

Example 3:

Input: s = "MCMXCIV"

Output: 1994

Explanation:

M = 1000
CM = 900
XC = 90
IV = 4
Total = 1000 + 900 + 90 + 4 = 1994.

3. Approach – Left-to-Right with Subtraction Rule:

Intuition:

We process the string from left to right:

Convert each Roman character to its value.
Normally, we add the value.
But when a smaller value appears before a larger value, it means subtraction (e.g., IV, IX, XL, etc.).

So for each position i:

Compare value(s[i]) with value(s[i+1]):

If value(s[i]) < value(s[i+1]), subtract value(s[i]).
Else, add value(s[i]).

This automatically handles all six subtractive cases given the input is guaranteed valid.

Algorithm (Step-by-Step):

Build a mapping from Roman characters to integer values.
Initialize result = 0.
Loop over index i from 0 to len(s) - 1:

Let current = value(s[i]).
if i + 1 < len(s), let next = value(s[i + 1]), else next = 0 (or treat as no next).
if current < next:

result -= current (subtractive case)

else:

result += current.

Return result.

Pseudo-code:

Complexity:

Let n (up to 15):

Time: O(1)
Space: O(1) (fixed-size map)

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code:

<<<PREV

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog