Forem: Hommies

LeetCode Solution: 13. Roman to Integer

Hommies — Thu, 21 May 2026 11:37:46 +0000

How to Conquer Roman Numerals: LeetCode #13 Explained Simply!

Hey there, future coding superstar! 👋 Ever looked at Roman numerals and thought, "That's a cool system, but how would I code that conversion?" Today, we're diving into LeetCode problem #13, "Roman to Integer," a fantastic problem for beginners that teaches some core programming concepts.

Let's unravel this ancient number system together and turn it into elegant Python code!

The Roman Numeral Mystery (Problem Explanation)

Roman numerals use a set of seven symbols:

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

Usually, they're written from largest value to smallest, and you just add them up. For example:

II = 1 + 1 = 2
XII = 10 + 1 + 1 = 12
XXVII = 10 + 10 + 5 + 1 + 1 = 27

Sounds simple, right? But here's the twist! There are six special cases where a smaller numeral comes before a larger one, and instead of adding, you subtract it.

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

So, your task is to take a Roman numeral string (like "MCMXCIV") and convert it into its integer equivalent (like 1994). The input string is guaranteed to be a valid Roman numeral within a certain range.

Let's look at an example to clarify:
Input: s = "MCMXCIV"
Output: 1994

M = 1000
CM = 900 (C before M means 1000 - 100)
XC = 90 (X before C means 100 - 10)
IV = 4 (I before V means 5 - 1) Total: 1000 + 900 + 90 + 4 = 1994

The "Aha!" Moment (Intuition)

The core challenge is handling those subtraction cases (IV, IX, etc.). How do we know whether to add or subtract a symbol's value?

Think about it: when you see IV, you process I and then V. The I isn't added directly because it's followed by a larger value (V). If it was III, each I would be added because it's followed by a smaller or equal value (I).

This gives us a huge hint: we need to look at the next character!

If the current symbol's value is less than the next symbol's value, it's a subtraction case. We should subtract the current symbol's value.
Otherwise (if the current symbol's value is greater than or equal to the next symbol's value), it's a standard addition case. We should add the current symbol's value.

This "look ahead" strategy is the key to solving this problem efficiently!

Your Step-by-Step Guide (Approach)

Let's break down how we can implement this "look ahead" strategy:

Create a Lookup Table: First things first, we need an easy way to get the integer value for each Roman symbol. A dictionary (or hash map) is perfect for this! It maps each Roman character to its integer value ('I': 1, 'V': 5, etc.).
Initialize Result: We'll need a variable, let's call it result, to keep a running total of our integer conversion. Start it at 0.
Iterate with a "Look Ahead": We'll loop through the Roman numeral string. However, since we need to compare the current character with the next one, we should stop our loop one character before the end of the string.
- For each pair of (current_char, next_char):
  - Look up current_char's value (val_current) in our dictionary.
  - Look up next_char's value (val_next) in our dictionary.
  - Condition Check:
    - If val_current < val_next (e.g., 'I' is 1, 'V' is 5, so 1 < 5): This is a subtraction case! Add -val_current to our result.
    - Else (val_current >= val_next): This is an addition case! Add val_current to our result.
Handle the Last Character: Our loop stops one character before the end. This means the very last character in the string was never compared as a current_char to a next_char. Since a last character can never be part of a subtraction pair (it has no character after it), its value is always added. So, after the loop, we simply add the value of the last_char to our result.
Return: Finally, result holds the complete integer conversion. Return it!

The Code (Python)

Here's the Python solution based on our approach:

class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0  # Initialize our result accumulator

        # Our handy lookup table for Roman symbols to integer values
        roman_map = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }

        # Iterate through the string, comparing current character (a) with the next (b)
        # The zip(s, s[1:]) trick cleverly creates pairs:
        # (s[0], s[1]), (s[1], s[2]), ..., (s[N-2], s[N-1])
        # This processes all pairs *except* for the very last character s[N-1]
        for current_char, next_char in zip(s, s[1:]):
            current_value = roman_map[current_char]
            next_value = roman_map[next_char]

            if current_value < next_value:
                # If current value is smaller than next, it's a subtraction case (e.g., IV, IX)
                res -= current_value
            else:
                # Otherwise, it's a standard addition case (e.g., III, L)
                res += current_value

        # After the loop, the value of the *last* character in the string
        # has not yet been added to `res`. It will always be an addition.
        res += roman_map[s[-1]] 

        return res

Performance Check (Time & Space Complexity)

Time Complexity: O(N)
- We iterate through the input string s once using the zip function, which effectively processes each character pair. The length of the string is N.
- Looking up values in our roman_map (a dictionary) takes O(1) (constant time) on average.
- Therefore, the total time complexity is directly proportional to the length of the input string.
Space Complexity: O(1)
- We use a dictionary (roman_map) to store the symbol-to-value mappings. This dictionary has a fixed size (7 entries), regardless of how long the input Roman numeral string s is.
- No other data structures are used that grow with the input size.
- Thus, the auxiliary space used is constant.

Key Takeaways

Lookahead Pattern: This problem is a classic example of when to use a "lookahead" pattern in string processing. By considering the next element, you can make informed decisions about the current element.
Hash Maps/Dictionaries are Your Friends: For quick lookups of values associated with specific keys (like Roman symbols to their integers), dictionaries are incredibly efficient and make your code clean.
Edge Cases Matter: Always consider the beginning, middle, and end of your input. Here, the very last character needed special handling because our zip iteration didn't include a "next" for it.

That's it! You've successfully converted Roman numerals to integers using a clever approach. Keep practicing, and you'll be tackling even more complex problems in no time!

Authored by: p1Hzd8mRM8

Published: 2026-05-21 17:07:27

LeetCode Solution: 12. Integer to Roman

Hommies — Thu, 21 May 2026 11:36:00 +0000

Unraveling the Mystery of Roman Numerals: A LeetCode Journey (Problem 12. Integer to Roman)

Hey LeetCoders and aspiring developers! 👋 Today, we're taking a trip back in time to ancient Rome... well, almost! We're tackling LeetCode problem 12: "Integer to Roman." This problem asks us to convert a standard integer into its Roman numeral representation. It sounds simple, but Roman numerals have some quirky rules that make this a fun challenge. Let's dive in!

🧐 Problem Explanation: What are Roman Numerals Anyway?

Roman numerals use a system of seven symbols, each representing a specific value:

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

The general idea is to build numbers by adding these symbols. For example:

II = 1 + 1 = 2
VI = 5 + 1 = 6
LX = 50 + 10 = 60
MCC = 1000 + 100 + 100 = 1200

But here's where it gets interesting – there are special "subtractive forms" for numbers that would otherwise require four repeated symbols or just sound clunky:

Subtractive Rule: If a smaller value symbol appears before a larger value symbol, it means subtraction.
- IV = 5 - 1 = 4 (instead of IIII)
- IX = 10 - 1 = 9 (instead of VIIII)
- XL = 50 - 10 = 40
- XC = 100 - 10 = 90
- CD = 500 - 100 = 400
- CM = 1000 - 100 = 900

Crucially, the problem states that Roman numerals are formed by converting decimal place values from highest to lowest. This means when converting 3749:

You first convert 3000 (MMM)
Then 700 (DCC)
Then 40 (XL)
Then 9 (IX)
Combining them gives MMMDCCXLIX.

You can't do things like IL for 49, because I is not a decimal place lower than L (which is in the tens place, I is in the ones place). 49 is 40 (XL) + 9 (IX). This "decimal place" rule is important for understanding the valid subtractive forms.

Our task is to take an integer num (between 1 and 3999) and return its Roman numeral string representation.

🤔 Intuition: The "Aha!" Moment

When I first look at this, my brain immediately thinks, "Okay, I need to figure out which Roman symbols make up the number." But with the additive and especially the subtractive rules, a simple if num >= value: add symbol loop might get complicated fast.

The key insight comes from the combination of the specific rules and the examples:

Fixed Symbols & Values: We have a known set of symbol-value pairs.
Greedy Approach: We want to build the Roman numeral from left to right, which means processing the largest possible values first.
Subtractive Forms are Special: CM (900) is one unit in the Roman system, not D then CCCC. Same for CD, XC, XL, IX, IV. These special forms are essentially "preferred" over their additive counterparts.

This leads to the "aha!" moment: If we create a list of all valid Roman numeral values, including the subtractive forms, and sort them from largest to smallest, we can simply go through this list and greedily subtract the largest possible value from our input number until it becomes zero.

For example, if num = 900:

If we only considered M=1000, D=500, C=100, we might try to use D (500), leaving 400. Then try C four times. This would be incorrect (DCCCC).
But if our list explicitly contains (900, 'CM'), then 900 would be matched directly, giving us CM and the correct result.

✍️ Approach: Step-by-Step Greedy Conversion

Based on our intuition, here's the plan:

Create a lookup table: We'll define a list of tuples, where each tuple contains (integer_value, roman_symbol_string). This list is critical:
- It must include all standard symbols (M, D, C, L, X, V, I).
- It must also include the special subtractive forms (CM, CD, XC, XL, IX, IV).
- Crucially, this list must be sorted in descending order of the integer values. This ensures our greedy approach always picks the largest possible Roman numeral component first.
Our list will look something like this:
[(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'), (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')]
Initialize result: Start with an empty list or string to build our Roman numeral. A list is generally more efficient for appending in Python, then we'll join it at the end.
Iterate and subtract: Loop through our value_symbols list (which is sorted largest to smallest):
- For each (value, symbol) pair:
  - Check how many times this value can fit into our current num. Let's call this count. count = num // value (integer division).
  - Append the symbol repeated count times to our result list. For example, if num is 3000 and value is 1000, count will be 3, and we'll append "MMM".
  - Update num by subtracting count * value from it. This consumes the portion of the number we just converted.
  - We can add an early break if num becomes 0, as there's nothing left to convert.
Join and return: Once the loop finishes, all parts of num will have been converted. Join the elements in our result list into a single string and return it.

Let's trace num = 1994 with this approach:

res = [], num = 1994
value_symbols list: [(1000, 'M'), (900, 'CM'), ..., (1, 'I')]

`value`	`symbol`	`num` (start)	`count = num // value`	`res.append(symbol * count)`	`num -= count * value`	`num` (end)
1000	'M'	1994	1	`res = ['M']`	`1994 - 1000`	994
900	'CM'	994	1	`res = ['M', 'CM']`	`994 - 900`	94
500	'D'	94	0	-	-	94
400	'CD'	94	0	-	-	94
100	'C'	94	0	-	-	94
90	'XC'	94	1	`res = ['M', 'CM', 'XC']`	`94 - 90`	4
50	'L'	4	0	-	-	4
40	'XL'	4	0	-	-	4
10	'X'	4	0	-	-	4
9	'IX'	4	0	-	-	4
5	'V'	4	0	-	-	4
4	'IV'	4	1	`res = ['M', 'CM', 'XC', 'IV']`	`4 - 4`	0
1	'I'	0	(break loop)	-	-	0

Finally, ''.join(res) gives us "MCMXCIV", which is the correct answer! This greedy approach, combined with a carefully constructed and ordered lookup table, handles all the Roman numeral rules elegantly.

💻 Code

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the Roman numeral values and their corresponding symbols.
        # This list is crucial: it must be sorted in descending order of values,
        # and include the special subtractive forms (like 900 for CM)
        # BEFORE their additive components (like 500 for D and 100 for C).
        value_symbols = [
            (1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
            (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'), (10, 'X'),
            (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
        ]

        # Initialize an empty list to store the Roman numeral characters.
        # Appending to a list and then joining is generally more efficient
        # than repeated string concatenation in Python.
        res = []

        # Iterate through our defined value-symbol pairs.
        for value, symbol in value_symbols:
            # If num has become 0, we've converted the entire number,
            # so we can break early.
            if num == 0:
                break

            # Calculate how many times the current 'value' fits into 'num'.
            # E.g., if num = 3000 and value = 1000, count = 3.
            count = num // value

            # Append the 'symbol' repeated 'count' times to our result list.
            # E.g., if count = 3 and symbol = 'M', it appends 'MMM'.
            res.append(symbol * count)

            # Subtract the converted portion from num.
            # E.g., num = 3000 - (3 * 1000) = 0.
            num -= count * value

        # Join all the symbols in the list to form the final Roman numeral string.
        return ''.join(res)

⏱️ Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(1)
- The value_symbols list has a fixed size (13 elements).
- We iterate through this list exactly once.
- Inside the loop, operations like integer division (//), multiplication (*), list append(), and subtraction (-) take constant time. The string multiplication symbol * count and append are also bounded because the maximum count is small (at most 3 for 'I', 'X', 'C', 'M') and the Roman numeral string's total length for num <= 3999 is very short (e.g., "MMMCMXCIX" for 3999 has 7 characters).
- Since the number of iterations and the work done in each iteration are bounded by a constant (independent of the input num's magnitude, within the given constraints), the overall time complexity is constant.
Space Complexity: O(1)
- The value_symbols list is a fixed-size data structure (13 tuples), so it takes constant space.
- The res list stores the characters of the resulting Roman numeral string. The maximum length of a Roman numeral for an integer up to 3999 is also very small (e.g., "MMMCMXCIX" has 7 characters).
- Therefore, the space used is bounded by a constant, leading to O(1) space complexity.

This solution is incredibly efficient because it leverages the fixed and relatively small nature of the Roman numeral system's rules and symbols.

🎯 Key Takeaways

Greedy Approach Power: This problem is a classic example where a greedy approach shines. By always taking the largest possible valid Roman numeral component first, and ensuring your lookup table accounts for special cases (like subtractive forms) in the correct order, you can simplify complex rules.
Lookup Tables are Your Friend: When dealing with predefined mappings or rules, a well-structured lookup table (like our value_symbols list) can make your code much cleaner and easier to reason about than a series of nested if/else statements.
Order Matters! For greedy algorithms, the order of elements in your lookup table is paramount. Always ensure the largest values (including special combinations) come first.
Python String Efficiency: Appending to a list and then using ''.join() is generally more efficient for building strings than repeated string concatenation (+=) in Python, especially for potentially longer strings (though in this specific problem, the string length is so small that the difference would be negligible).

And there you have it! Converting integers to Roman numerals might seem tricky at first, but with a solid understanding of the rules and a well-designed greedy approach, it becomes quite straightforward.

Happy coding!

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-21 17:05:20

LeetCode Solution: 10. Regular Expression Matching

Hommies — Thu, 21 May 2026 11:22:46 +0000

Mastering Regular Expressions: A Deep Dive into LeetCode 10 with Dynamic Programming

Hey there, fellow coders! 👋 Are you ready to tackle one of LeetCode's classic challenges that might seem daunting at first glance but becomes quite elegant with the right approach? Today, we're diving into Problem 10: Regular Expression Matching.

This problem is a fantastic way to sharpen your dynamic programming (DP) skills and gain a deeper understanding of how regular expressions actually work under the hood. Don't worry if regex feels like magic – we're going to demystify it together!

The Puzzle: Regular Expression Matching

We're given two strings: an input string s and a pattern p. Our goal is to determine if the pattern p completely matches the input string s.

The twist? The pattern p isn't just plain text. It can contain two special characters:

'.': This dot matches any single character. Think of it as a wildcard for one character.
'*': This asterisk matches zero or more of the preceding element. This is where things get interesting!

Important Note: The match must cover the entire input string s, not just a part of it.

Let's look at a few examples to solidify our understanding:

Example 1: Basic Mismatch

s = "aa", p = "a"
Output: false
Why? The pattern "a" only matches the first 'a' of "aa". It doesn't cover the entire string.

Example 2: The Power of *

s = "aa", p = "a*"
Output: true
Why? * means "zero or more of the preceding element," which is 'a'. By repeating 'a' once, the pattern becomes "aa", matching the input. If s was "a", it would also match (zero repetitions). If s was "aaa", it would match (two repetitions).

Example 3: .* - The Ultimate Wildcard Combo

s = "ab", p = ".*"
Output: true
Why? . matches any single character. * means "zero or more" of whatever precedes it. So, .* means "zero or more of any character." It can match "ab", "a", "", "xyz", anything!

The "Aha!" Moment: Intuition

When you see problems involving matching parts of strings, especially with wildcards or options like "zero or more," your mind should start thinking about Dynamic Programming (DP). Why DP? Because the decision at any point (does s[i] match p[j]) often depends on the results of smaller subproblems.

Imagine trying to match s and p.

If p[j] is a regular character or . you just check if s[i] matches p[j] and then move on to matching the rest of s and p.
But what if p[j] is *? This is the tricky part. * gives us options:
1. It could match zero occurrences of the character before it.
2. It could match one or more occurrences of the character before it.

These multiple choices, and the fact that we can build up a solution from smaller matches, strongly hints at DP!

Our Strategy: Dynamic Programming Grid

We'll use a 2D boolean array, let's call it dp, where dp[i][j] will be True if the first i characters of s (i.e., s[0...i-1]) match the first j characters of p (i.e., p[0...j-1]). Otherwise, it will be False.

Let m be the length of s and n be the length of p. Our dp table will be (m+1) x (n+1).

Step 1: Initialize the DP Table

dp[0][0] = True: An empty string (s with 0 characters) always matches an empty pattern (p with 0 characters). This is our base case.
First Row (dp[0][j] for j > 0): This represents matching an empty string s with a non-empty pattern p.
An empty string can only be matched by a pattern that allows zero characters. This typically happens with *.
If p[j-1] is '*', then it can match zero of the preceding element (p[j-2]). In this scenario, dp[0][j] would be True if dp[0][j-2] was True. All other dp[0][j] would be False.

Step 2: Fill the DP Table

We'll iterate through s (from i = 1 to m) and p (from j = 1 to n) to fill the table. For each dp[i][j], we consider two main scenarios for the current character p[j-1]:

Scenario 1: p[j-1] is NOT '*' (i.e., it's a regular character or '.')

If p[j-1] matches s[i-1] (meaning p[j-1] == s[i-1] or p[j-1] == '.'), then s[0...i-1] matches p[0...j-1] only if s[0...i-2] matched p[0...j-2].
So, dp[i][j] = dp[i-1][j-1].
Otherwise (if p[j-1] doesn't match s[i-1]), dp[i][j] = False.

Scenario 2: p[j-1] IS '*'

This is the trickiest part. The * implies "zero or more" of the preceding character (p[j-2]). Let's call this preceding character prev_char_in_pattern = p[j-2].

We have two possibilities for how * can be interpreted:

* matches zero occurrences of prev_char_in_pattern:
- In this case, prev_char_in_pattern and the * effectively disappear from the pattern.
- So, we need to check if s[0...i-1] matches p[0...j-3]. This state is represented by dp[i][j-2].
- Thus, dp[i][j] = dp[i][j-2].
* matches one or more occurrences of prev_char_in_pattern:
- For * to match one or more times, prev_char_in_pattern must match the current character s[i-1]. (i.e., prev_char_in_pattern == s[i-1] or prev_char_in_pattern == '.').
- If they match, s[i-1] is consumed by one instance of prev_char_in_pattern. We then need s[0...i-2] to match p[0...j-1] (the prev_char_in_pattern followed by * is still active, potentially matching more characters).
- This state is represented by dp[i-1][j].
- So, if prev_char_in_pattern matches s[i-1], then dp[i][j] can also be dp[i-1][j].

Combining these: dp[i][j] will be True if either of these conditions holds. dp[i][j] = dp[i][j-2] (zero occurrences) If prev_char_in_pattern matches s[i-1] (i.e., p[j-2] == s[i-1] or p[j-2] == '.'): dp[i][j] = dp[i][j] or dp[i-1][j] (one or more occurrences)

Step 3: The Result

After filling the entire dp table, the final answer will be in dp[m][n].

Let's walk through an example: s = "aab", p = "c*a*b"

dp[i][j]	""	c	*	a	*	b
""	T	F	T	F	T	F
a	F	F	F	T	T	F
aa	F	F	F	F	T	F
aab	F	F	F	F	F	T

dp[0][0] is T.
dp[0][2] (for c*): p[1] is *, so dp[0][2] = dp[0][0] which is T. (empty string matches c* by c repeating 0 times).
dp[0][4] (for c*a*): p[3] is *, so dp[0][4] = dp[0][2] which is T. (empty string matches c*a* by a repeating 0 times).
Now, consider dp[1][1] (s="a", p="c"): p[0] ('c') != s[0] ('a'). So F.
Consider dp[1][4] (s="a", p="c*a*"):
- p[3] is *. Preceding char p[2] is 'a'.
- dp[1][2] (zero 'a's for a*) is F.
- Does p[2] ('a') match s[0] ('a')? Yes!
- dp[0][4] (one or more 'a's) is T.
- So dp[1][4] becomes F OR T = T.
Finally, dp[3][6] will be T.

The Code

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m, n = len(s), len(p)

        # dp[i][j] will be True if s[0...i-1] matches p[0...j-1]
        # Dimensions: (m+1) x (n+1)
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: Empty string matches empty pattern
        dp[0][0] = True

        # Initialize the first row (s is empty)
        # An empty string 's' can only match patterns like "a*", "a*b*", etc.
        # This means the pattern must end with '*' and its preceding element can be skipped.
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # If p[j-1] is '*', it means zero occurrences of p[j-2].
                # So, dp[0][j] depends on whether p[0...j-3] matched an empty string.
                dp[0][j] = dp[0][j - 2]

        # Fill the DP table for all other cells
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # Scenario 1: Current pattern character is a regular character or '.'
                # (p[j-1] is not '*')
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    # If current characters match, depend on the match of preceding substrings
                    dp[i][j] = dp[i - 1][j - 1]

                # Scenario 2: Current pattern character is '*'
                elif p[j - 1] == '*':
                    # Case A: '*' matches zero occurrences of the preceding element (p[j-2])
                    # We effectively ignore p[j-2] and p[j-1] (the '*')
                    # So, s[0...i-1] must match p[0...j-3]
                    dp[i][j] = dp[i][j - 2]

                    # Case B: '*' matches one or more occurrences of the preceding element (p[j-2])
                    # This is only possible if the preceding character (p[j-2]) matches s[i-1]
                    # (p[j-2] == s[i-1] or p[j-2] == '.')
                    if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                        # If they match, '*' consumes s[i-1], and we check if s[0...i-2] matches p[0...j-1]
                        # (where p[j-1] is still '*', allowing it to match further characters)
                        dp[i][j] = dp[i][j] or dp[i - 1][j]

        return dp[m][n]

Time and Space Complexity Analysis

Time Complexity: O(m * n)
- We are filling an m x n DP table. Each cell calculation takes constant time (a few comparisons and assignments). Therefore, the total time complexity is proportional to the product of the lengths of the string s and pattern p.
Space Complexity: O(m * n)
- We use a 2D dp array of size (m+1) x (n+1) to store our intermediate results. This contributes O(m * n) to the space complexity.

Given the constraints 1 <= s.length <= 20 and 1 <= p.length <= 20, an O(m*n) solution is perfectly efficient for this problem. 20 * 20 = 400 operations per test case is lightning fast!

Key Takeaways

Dynamic Programming for String Matching: Problems involving matching substrings, especially with wildcards or varying length matches, are prime candidates for DP.
Defining DP State: Clearly defining dp[i][j] as the match for prefixes s[0...i-1] and p[0...j-1] is crucial.
Handling Special Characters (. and *):
- . is straightforward: it matches any single character.
- * requires careful consideration: it has two main interpretations ("zero occurrences" OR "one or more occurrences") that lead to combining results from different DP states.
  - Zero occurrences: The * and its preceding character are skipped (dp[i][j-2]).
  - One or more occurrences: The * matches the current character s[i-1] (if the preceding char allows it), and the * pattern remains active (dp[i-1][j]).
Base Cases: Correctly initializing dp[0][0] and the first row (dp[0][j]) for an empty string s is vital for the DP to propagate correctly.

This problem is a fantastic way to stretch your DP muscles and see how complex string operations can be broken down into manageable subproblems. Keep practicing, and you'll master these patterns in no time!

Published by p1Hzd8mRM8 on 2026-05-21 16:52:13

LeetCode Solution: 10. Regular Expression Matching

Hommies — Thu, 21 May 2026 09:05:53 +0000

Cracking the Regex Code: LeetCode 10 - Regular Expression Matching (Beginner-Friendly DP!)

Hey fellow coders! 👋

Today, we're diving into a classic LeetCode problem that might seem daunting at first glance but becomes incredibly elegant with the right approach: 10. Regular Expression Matching.

If you've ever used regular expressions (regex) in your programming, you know how powerful they are. This problem asks us to implement a simplified version of that power from scratch! Don't worry, we'll break it down step by step.

The Problem: Regular Expression Matching 🤯

We're given two strings: an input string (s) and a pattern (p). Our mission? Determine if the pattern p entirely matches the input string s.

The tricky part comes with two special characters in our pattern:

. (Dot): This little guy is a wildcard! It matches any single character. Think of it as a Joker card in a deck.
* (Asterisk): This one is a bit more complex. It matches zero or more occurrences of the preceding element. The "preceding element" could be a regular character (like a in a*) or even a dot (. in .*).

Crucial Note: The match must cover the entire input string s, not just a part of it.

Let's look at a few examples to make it super clear:

Example 1:
- s = "aa", p = "a"
- Output: false
- Why? The pattern "a" only matches the first 'a'. It doesn't cover the entire "aa".
Example 2:
- s = "aa", p = "a*"
- Output: true
- Why? The * means "zero or more of the preceding 'a'". If we repeat 'a' once, it becomes "aa", which matches s.
Example 3:
- s = "ab", p = ".*"
- Output: true
- Why? . matches "any single character". * means "zero or more of the preceding element". So, .* means "zero or more of any character". This can match "ab" (specifically, it matches a once, then b once).

Constraints:

s and p are pretty short (length up to 20). This is a hint that solutions with complexity like O(len(s) * len(p)) might pass!
s only has lowercase English letters.
p has lowercase English letters, ., and *.
Every * in p is guaranteed to have a valid preceding character (no *abc).

The Intuition: "Aha!" - It's a Matching Game! 🎮

When you see problems asking if one string "matches" another, especially with wildcards or characters that depend on previous elements, your brain should immediately start thinking about Dynamic Programming (DP).

Why DP? Because matching involves checking if sub-parts of s match sub-parts of p. If s[0...i] matches p[0...j], it likely depends on whether s[0...i-1] matched p[0...j-1], or some other combination. We can build up our solution from smaller, simpler matches!

Think of it like this: If you're trying to match s and p, you look at their last characters.

If they're simple characters and match, great! You just need to check if the rest of s matches the rest of p.
If p has a . (dot), it's a free pass! It matches any character in s. So again, check the rest.
If p has a * (asterisk), this is where it gets interesting. A * can represent zero occurrences, one occurrence, or multiple occurrences. This means we have choices, and DP is excellent for exploring choices efficiently!

The Approach: Building Our DP Table 🏗️

Let's define our DP state:

dp[i][j] will be a boolean value, true if the first i characters of s (i.e., s[0...i-1]) match the first j characters of p (i.e., p[0...j-1]), and false otherwise.

We'll create a (m+1) x (n+1) 2D array (or list of lists in Python), where m = len(s) and n = len(p). The extra row/column is for handling empty prefixes.

1. Initialization (Base Cases)

dp[0][0] = true: An empty string "" always matches an empty pattern "". This is our starting point!
dp[i][0] = false for i > 0: A non-empty string s can never match an empty pattern "". These will remain false by default.
dp[0][j] for j > 0: An empty string s can match patterns like "a*" or "a*b*".
- If p[j-1] is *, then dp[0][j] can be true if dp[0][j-2] is true. This means the X* part (where X is p[j-2]) is effectively skipped, matching zero occurrences of X.
- Example: For s="", p="a*b*".
  - dp[0][0] = true
  - p[1] is *. dp[0][2] (for a*) = dp[0][0] = true.
  - p[3] is *. dp[0][4] (for a*b*) = dp[0][2] = true.

2. Filling the DP Table (Iterative Logic)

We'll iterate i from 1 to m (for s) and j from 1 to n (for p).

For each dp[i][j], we consider s[i-1] (the current character in s) and p[j-1] (the current character in p).

Case 1: p[j-1] is NOT * (it's a regular character or .)

If p[j-1] is a regular letter OR p[j-1] is . (the wildcard):

We need s[i-1] to match p[j-1] (or p[j-1] is . which matches anything).
If they match, then dp[i][j] is true if and only if the previous parts also matched: dp[i-1][j-1].

if p[j-1] == s[i-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]

Case 2: p[j-1] IS *

This is the most complex part, as * gives us two main options for the preceding element p[j-2]:

Option A: * matches zero occurrences of p[j-2]
- If * matches zero occurrences, it's like p[j-2] and p[j-1] (*) aren't even there.
- So, dp[i][j] would be true if s[0...i-1] matches p[0...j-3] (which is dp[i][j-2]).
- dp[i][j] = dp[i][j-2] (initial state for this cell)
Option B: * matches one or more occurrences of p[j-2]
- This is only possible if s[i-1] (the current character in s) actually matches p[j-2] (the character before *). Remember . also counts as a match!
- If s[i-1] matches p[j-2] (or p[j-2] is .):
  - * matches one occurrence: s[0...i-1] matches p[0...j-1] if s[0...i-2] matched p[0...j-1] (meaning s[i-1] is another occurrence of p[j-2]). This is dp[i-1][j].
  - We combine this with Option A: dp[i][j] = dp[i][j] OR dp[i-1][j]
- if p[j-2] == s[i-1] or p[j-2] == '.': dp[i][j] = dp[i][j] or dp[i-1][j]

Putting it all together for *:

elif p[j-1] == '*':
dp[i][j] = dp[i][j-2] # Option A: '*' matches zero preceding elements
if p[j-2] == s[i-1] or p[j-2] == '.':
dp[i][j] = dp[i][j] or dp[i-1][j] # Option B: '*' matches one or more

Finally, after filling the entire table, our answer is simply dp[m][n].

The Code ✨

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        # dp[i][j] will be true if s[0...i-1] matches p[0...j-1]
        # (m+1) rows for string s, (n+1) columns for pattern p
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: Empty string matches empty pattern
        dp[0][0] = True

        # Handle patterns like "a*", "a*b*", etc., matching an empty string s
        # dp[i][0] for i > 0 will remain False as a non-empty string cannot match an empty pattern.
        for j in range(1, n + 1):
            # If the current pattern character is '*', it might match zero occurrences
            # of the preceding element. So, dp[0][j] depends on dp[0][j-2].
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        # Fill the DP table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # Case 1: Current pattern character is a letter or '.'
                # If s[i-1] matches p[j-1] (or p[j-1] is '.'), then the match depends on
                # whether the preceding parts (s[0...i-2] and p[0...j-2]) matched.
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]

                # Case 2: Current pattern character is '*'
                elif p[j - 1] == '*':
                    # Option A: '*' matches zero occurrences of the preceding element p[j-2]
                    # In this scenario, we effectively ignore p[j-2] and p[j-1] ('*').
                    # So, dp[i][j] is true if dp[i][j-2] is true.
                    dp[i][j] = dp[i][j - 2]

                    # Option B: '*' matches one or more occurrences of the preceding element p[j-2]
                    # This is only possible if s[i-1] matches p[j-2] (or p[j-2] is '.').
                    # If it matches, then dp[i][j] can also be true if dp[i-1][j] is true.
                    # dp[i-1][j] means s[0...i-2] already matched p[0...j-1], and now s[i-1]
                    # is another instance matching p[j-2], so the '*' consumes s[i-1].
                    if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                        dp[i][j] = dp[i][j] or dp[i - 1][j]

        return dp[m][n]

Time & Space Complexity Analysis ⏱️

Time Complexity: O(m * n)
- We are filling an m x n DP table. Each cell calculation takes constant time (a few comparisons and lookups).
- Given m, n <= 20, this is 20 * 20 = 400 operations, which is extremely fast!
Space Complexity: O(m * n)
- We use a 2D dp array of size (m+1) x (n+1) to store our results.
- Similarly, for m, n <= 20, this is 21 * 21 = 441 booleans, a very small memory footprint.

Key Takeaways ✨

Dynamic Programming (DP) for String Matching: Many string-related problems, especially those involving subproblems and choices (like * representing zero or more), are excellent candidates for DP.
Careful Base Cases: Correctly initializing your DP table, especially for empty strings and patterns, is crucial.
Handling Wildcards: Special characters like . and * require breaking down their behavior into distinct cases (. is simple, * involves "zero occurrences" vs. "one or more occurrences").
Building from Smaller Problems: The beauty of DP is seeing how dp[i][j] relies on previously computed dp values, allowing us to build up the complete solution efficiently.

This problem is a fantastic way to solidify your understanding of DP and string manipulation. Keep practicing, and you'll be a regex master in no time!

Author Account: p1Hzd8mRM8
Published: 2026-05-21 14:35:24

LeetCode Solution: 7. Reverse Integer

Hommies — Sun, 17 May 2026 06:36:46 +0000

Unlocking LeetCode 7: Reverse Integer (A Beginner's Guide to Digital Flipping!)

Hello Devs! Today, we're diving into a classic LeetCode problem that's perfect for honing your logical thinking and handling tricky integer constraints: Problem 7: Reverse Integer. It sounds simple, but there's a neat catch!

Problem Explanation

We're given a signed 32-bit integer (that's a number that can be positive or negative, fitting within a specific range, roughly -2 billion to +2 billion). Our goal is to return this integer with its digits reversed.

Sounds easy, right? Here's the catch: If reversing the digits causes the number to go outside the valid 32-bit integer range, we must return 0. Also, we can't use 64-bit integers, which means we need to be careful with intermediate results if we were using a fixed-size integer language.

Let's look at some examples:

x = 123 becomes 321
x = -123 becomes -321 (the sign stays!)
x = 120 becomes 21 (leading zeros are dropped when reversing)

Intuition

The "aha!" moment for this problem often comes from realizing that dealing with individual digits of a number is much easier when it's not a number. Think of it: how do you reverse "123"? You literally flip the order. What data type is great for flipping characters? Strings!

So, our core idea is:

Convert the integer to a string.
Reverse the string.
Convert it back to an integer.
Perform the all-important range check.

Approach

Let's break down the steps:

Handle the Sign: Before reversing, we need to know if the original number x was negative. If x is negative, we'll reverse its positive counterpart (e.g., 123 from -123) and then apply the negative sign back at the end.
Convert and Reverse:
- If x is negative, we first take its absolute value's string representation (str(x)[1:] effectively removes the - sign). Then, we reverse this substring using slicing ([::-1]).
- If x is positive, we simply convert x to a string (str(x)) and reverse it.
Convert Back to Integer: After reversing the string, we convert it back to an integer using int().
Apply Sign (if needed): If the original x was negative, multiply our res by -1.
The Critical Overflow Check: This is where many solutions fail! We need to check if our res is now outside the [-2^31, 2^31 - 1] range.
- The maximum 32-bit signed integer is 2**31 - 1.
- The minimum 32-bit signed integer is -2**31.
- If res is too large or too small, return 0. Otherwise, return res.

Code

Here's the Python implementation based on our approach:

class Solution:
    def reverse(self, x: int) -> int:
        # Define the 32-bit integer range boundaries
        MAX_INT = 2**31 - 1
        MIN_INT = -2**31

        res = 0
        if x < 0:
            # For negative numbers, remove the '-' sign, reverse, then re-apply '-'
            # Example: -123 -> "123" -> "321" -> -321
            res = int(str(x)[1:][::-1]) * -1
        else:
            # For positive numbers, simply convert to string, reverse, convert back
            # Example: 123 -> "123" -> "321" -> 321
            res = int(str(x)[::-1])

        # Check for 32-bit integer overflow
        if res > MAX_INT or res < MIN_INT:
            return 0

        return res

Time & Space Complexity Analysis

Time Complexity: O(log |x|)
- The operations involve converting the integer to a string, reversing it, and converting it back. The number of digits in x is proportional to log10(|x|). All these string operations take time proportional to the number of digits.
Space Complexity: O(log |x|)
- We create a string representation of x, which uses space proportional to the number of digits in x.

Key Takeaways

String Magic: For digit-based problems, converting integers to strings can often simplify reversal or digit manipulation.
Edge Cases are Crucial: Always consider negative inputs and, most importantly, the integer overflow/underflow boundaries.
Understand Data Types: Be aware of the maximum and minimum values your data types can hold, especially in competitive programming.

Happy coding!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 12:06:31

LeetCode Solution: 5. Longest Palindromic Substring

Hommies — Sat, 16 May 2026 18:44:09 +0000

Longest Palindromic Substring: A Core String Algorithm Explained

Welcome to another deep dive into a classic LeetCode problem! Today, we're tackling Problem 5: Longest Palindromic Substring. This problem is a fantastic way to sharpen your string manipulation and algorithmic thinking skills.

Problem Explanation

Given a string s, our goal is to find and return the longest substring within s that is a palindrome.

What's a palindrome? It's a sequence of characters that reads the same forwards and backward (e.g., "madam", "racecar", "level").
What's a substring? It's a contiguous sequence of characters within a string (e.g., for "apple", "app" is a substring, but "ale" is not).

Let's look at the examples:

Example 1:
- Input: s = "babad"
- Output: "bab"
- Explanation: "aba" is also a valid answer of the same length.
Example 2:
- Input: s = "cbbd"
- Output: "bb"

The string s will contain only digits and English letters, and its length will be between 1 and 1000 characters.

Intuition

The core idea behind finding palindromes is that they expand symmetrically from a center point. Think about "racecar" – the 'e' is the center, and 'c' expands to 'r'. Or "abba" – the center is between the two 'b's, and 'a' expands to 'a'.

This insight simplifies our search: instead of checking every single substring for palindromic properties (which is O(N^3) or O(N^2) with an O(N) check), we can iterate through every possible "center" and try to expand outwards.

There are two types of centers we need to consider:

Single character center: For palindromes with an odd length (e.g., "b*ab", "ra*cecar"). Here, s[i] itself is the center.
Two character center: For palindromes with an even length (e.g., "bb", "a*bb*a"). Here, s[i] and s[i+1] form the center.

Approach

We'll use an "Expand Around Center" approach:

Initialize: Keep track of the start and end indices of the longest palindrome found so far. Initialize them to 0, 0 (assuming a single character is the shortest possible palindrome).
Iterate Through Centers: Loop through each character in the string using an index i. Each i will serve as a potential center.
Expand for Odd Length Palindromes: Call a helper function expand_around_center(s, i, i). This tries to expand a palindrome assuming s[i] is its sole center.
Expand for Even Length Palindromes: Call the helper function expand_around_center(s, i, i + 1). This tries to expand a palindrome assuming s[i] and s[i+1] are its two central characters.
Helper Function expand_around_center(s, left, right):
- This function takes the string s and two indices, left and right.
- It expands outwards: left moves to the left (left-1) and right moves to the right (right+1).
- This expansion continues as long as left is within bounds (>= 0), right is within bounds (< len(s)), and the characters at s[left] and s[right] are equal.
- Once the loop terminates (either due to bounds or mismatch), the length of the palindrome found is right - left - 1.
Update Longest Palindrome: After getting len1 (odd center) and len2 (even center), determine max_len = max(len1, len2). If max_len is greater than the length of our current longest palindrome (end - start + 1), then update start and end.
- To calculate the new start and end from i and max_len:
  - start = i - (max_len - 1) // 2
  - end = i + max_len // 2
Return Result: After iterating through all possible centers, return the substring s[start : end + 1].

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start = 0
        end = 0

        # Helper function to expand around a given center
        def expand_around_center(s: str, left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # When the loop finishes, left and right are one step beyond the palindrome boundaries.
            # So, the length is (right - 1) - (left + 1) + 1 = right - left - 1
            return right - left - 1

        # Iterate through each character, treating it as a potential center
        for i in range(len(s)):
            # Case 1: Odd length palindrome (center is s[i])
            len1 = expand_around_center(s, i, i)

            # Case 2: Even length palindrome (center is s[i] and s[i+1])
            len2 = expand_around_center(s, i, i + 1)

            # Get the maximum length found from these two expansions
            max_len = max(len1, len2)

            # If this palindrome is longer than our current longest
            if max_len > end - start + 1:
                # Calculate the new start and end indices
                # For an odd length palindrome centered at i: start = i - (length-1)/2, end = i + (length-1)/2
                # For an even length palindrome centered between i and i+1: start = i - (length/2 - 1), end = i + length/2
                # The combined formula works for both:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2

        # Return the longest palindromic substring
        return s[start : end + 1]

Time & Space Complexity Analysis

Time Complexity: O(N^2)
- The main loop iterates N times, where N is the length of the string s.
- Inside the loop, expand_around_center is called twice. In the worst case, expand_around_center might traverse the entire string (e.g., for "aaaa...a").
- Thus, each call to expand_around_center takes O(N) time.
- Overall complexity: N * O(N) = O(N^2).
Space Complexity: O(1)
- We are only using a few variables (start, end, i, len1, len2, max_len, left, right) to store indices and lengths.
- The space used does not grow with the input string size.

Key Takeaways

Palindromes and Symmetry: The inherent symmetry of palindromes is key to efficient algorithms.
Expand Around Center: This is a powerful technique for palindrome problems, allowing us to find palindromes by growing them from every possible middle point.
Handling Odd and Even Lengths: Remember to consider both types of palindromes (odd-length with a single character center, and even-length with a two-character center).

This "Expand Around Center" approach is generally simpler to implement than dynamic programming solutions for this problem, while achieving the same O(N^2) time complexity.

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 00:13:54

LeetCode Solution: 4. Median of Two Sorted Arrays

Hommies — Sat, 16 May 2026 18:42:44 +0000

Unlock the Median Magic: Diving into Two Sorted Arrays!

Hey LeetCoders and aspiring developers! 👋

Today, we're tackling a classic LeetCode challenge that often pops up in interviews: 4. Median of Two Sorted Arrays. Don't let the "Hard" tag intimidate you! While the optimal solution is quite advanced, we'll walk through a very intuitive, step-by-step approach that makes perfect sense for beginners. Let's conquer this one together!

🚀 Problem Explanation: What are we actually doing?

Imagine you have two separate lists of numbers, nums1 and nums2, and here's the crucial part: both are already sorted! Your mission is to find the median of all the numbers if you were to combine these two lists into one big, sorted list.

What's a median?

If you have an odd number of elements in a sorted list, the median is simply the middle element. For [1, 2, 3], the median is 2.
If you have an even number of elements, the median is the average of the two middle elements. For [1, 2, 3, 4], the median is (2 + 3) / 2 = 2.5.

The problem throws a curveball: it asks for an overall runtime complexity of O(log(m+n)). We'll discuss this after exploring a more straightforward solution.

Example 1:

nums1 = [1,3], nums2 = [2]
If merged and sorted: [1,2,3]
Median: 2 (middle element)

Example 2:

nums1 = [1,2], nums2 = [3,4]
If merged and sorted: [1,2,3,4]
Median: (2+3)/2 = 2.5 (average of two middle elements)

🤔 Intuition: The "Aha!" Moment

The simplest way to find the median of two sorted arrays is to just... merge them! If we combine nums1 and nums2 into a single, sorted array, finding the median becomes trivial.

However, actually building a new merged array takes O(m+n) space and time. Can we do it without fully merging? Yes! We only need to find the element(s) at the median position(s). We can simulate the merge process by using two pointers, one for each array, and pick elements one by one until we reach the median position.

Think of it like this: you're trying to find the k-th smallest element in the combined list. Since the arrays are sorted, you can always compare the current smallest elements from nums1 and nums2 to find the overall next smallest element. We'll just keep doing this until we've "counted" up to our median position.

🪜 Approach: Simulating the Merge (O(m+n) Time)

Let's break down the step-by-step logic for our beginner-friendly O(m+n) approach:

Calculate Total Length & Median Positions:
- Find the total number of elements: total_len = len(nums1) + len(nums2).
- Determine if we need one median element (odd total_len) or two (even total_len). We'll need to iterate enough times to identify these elements.
Initialize Pointers and Median Candidates:
- Use two pointers, i for nums1 and j for nums2, both starting at 0.
- Introduce two variables, m1 and m2. m1 will store the current element identified as we iterate through the "merged" sequence. m2 will store the previous m1 value. This is crucial for when we need to average two middle elements (even total_len).
Iterate to the Median Position(s):
- We need to find elements up to total_len // 2 + 1. This ensures that for an even total_len, we capture both (total_len // 2) - 1 and (total_len // 2) elements (0-indexed).
- In each iteration:
  - First, m2 = m1. The current m1 becomes the "second to last" median candidate.
  - Then, compare the elements nums1[i] and nums2[j].
    - If nums1[i] is smaller (or nums2 is exhausted), pick nums1[i], assign it to m1, and increment i.
    - Otherwise (if nums2[j] is smaller or nums1 is exhausted), pick nums2[j], assign it to m1, and increment j.
Calculate and Return the Median:
- After the loop finishes, m1 will hold the element at total_len // 2 (0-indexed) and m2 will hold the element at (total_len // 2) - 1.
- If total_len is odd, m1 is our median.
- If total_len is even, the median is the average of m1 and m2.

This approach effectively "walks" through the merged sorted array without actually building it, stopping exactly when it finds the necessary median elements.

💻 Code: The O(m+n) Merge-Like Solution (Python)

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        total_len = m + n

        # m1 will store the element at the current "median" position
        # m2 will store the element at the "median-1" position (for even total_len)
        m1, m2 = 0, 0 

        i, j = 0, 0 # Pointers for nums1 and nums2

        # Iterate (m + n) // 2 + 1 times to find the median element(s)
        # We need to iterate one more time than total_len // 2 for even arrays
        # to capture both m1 and m2 correctly.
        for count in range(total_len // 2 + 1):
            m2 = m1 # m2 takes the value m1 had in the previous iteration

            # Logic to pick the next smallest element from either nums1 or nums2
            if i < m and (j >= n or nums1[i] < nums2[j]):
                m1 = nums1[i]
                i += 1 
            else: # j < n and (i >= m or nums2[j] <= nums1[i])
                m1 = nums2[j]
                j += 1

        # Check if the sum of n and m is odd.
        if (n + m) % 2 == 1:
            return float(m1)
        else:
            ans = float(m1) + float(m2)
            return ans / 2.0

⏱️ Time & Space Complexity Analysis

For the O(m+n) solution we just explored:

Time Complexity: O(m+n)
- We iterate through the arrays up to (m+n)/2 + 1 times in the worst case. This is directly proportional to the total number of elements.
Space Complexity: O(1)
- We only use a few extra variables (m1, m2, i, j, total_len). We don't create any new arrays proportional to the input size.

A Note on the O(log(m+n)) Requirement:
The problem statement does ask for an O(log(m+n)) runtime complexity. This typically points to a more advanced solution involving binary search on partitions. That approach is significantly more complex and often involves finding a "split point" in both arrays such that the elements to the left of the split form the lower half of the merged array, and elements to the right form the upper half.

While our O(m+n) solution is intuitive and a great starting point, mastering the O(log(m+n)) binary search approach is a fantastic next step once you're comfortable with this basic idea!

🌟 Key Takeaways

Simulate, Don't Always Build: For problems involving sorted arrays and finding specific elements (like the median or k-th smallest), you often don't need to physically merge them. Simulating the merge with pointers is efficient.
Median Logic: Remember the difference between odd and even total lengths for calculating the median. Keeping track of two "median candidate" variables (m1 and m2) helps simplify this.
Complexity Matters: Always be aware of the optimal time complexity required for a problem. While an O(m+n) solution is often a good first step, understanding the O(log(m+n)) binary search approach for this specific problem is key for interviews.

Happy coding, and keep practicing! You're doing great!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 00:12:16

LeetCode Solution: 3. Longest Substring Without Repeating Characters

Hommies — Sat, 16 May 2026 17:38:35 +0000

Sliding into Success: Solving LeetCode 3 - Longest Substring Without Repeating Characters

Hey there, aspiring competitive programmers and curious coders!

Today, we're diving into a classic LeetCode problem that's a fantastic introduction to a super useful technique: the Sliding Window. It's problem #3, "Longest Substring Without Repeating Characters," and it's a rite of passage for many!

Don't let the name intimidate you. By the end of this post, you'll not only understand it but also appreciate the elegance of its solution.

Problem Explanation: What are we actually trying to find?

The problem asks us to find the length of the longest substring within a given string s that doesn't have any repeating characters.

Let's break down some keywords:

String s: This is our input, like "abcabcbb" or "pwwkew".
Substring: This is a contiguous sequence of characters within a string. For example, in "abc", "a", "ab", "bc", "abc" are substrings. "ac" is not a substring because the characters aren't consecutive.
Without repeating characters: Every character in our substring must be unique. If we see 'a', we can't have another 'a' in the same substring.

Let's look at the examples:

s = "abcabcbb"
- "abc" is a substring without repeating characters (length 3).
- "bca" is also a substring without repeating characters (length 3).
- The longest such substring has a length of 3.
s = "bbbbb"
- "b" is the longest substring without repeating characters (length 1).
s = "pwwkew"
- "pw" (length 2)
- "wke" (length 3) - This is our winner!
- "kew" (length 3) - Another winner!
- IMPORTANT: "pwke" is not a substring, it's a subsequence. Remember, substrings must be contiguous. "wke" is valid because 'w', 'k', 'e' are consecutive.

Our goal is to return just the length of this longest unique-character substring.

Intuition: The "Aha!" Moment

Imagine you're looking at a street. You want to find the longest stretch of unique houses (characters). You start walking, adding each new house you see to your mental list.

If you see a house you've already listed, you know your current unique stretch has ended at or before this duplicate.
To continue, you can't just skip the duplicate. You need to "forget" houses from the beginning of your current stretch until the duplicate is no longer in your list. Then, you can add the current house and keep walking.

This "walking" and "forgetting" sounds like a Sliding Window! We'll have two pointers: left and right.

right expands our window, bringing new characters in.
left shrinks our window when we encounter a duplicate, removing characters from the start until the duplicate is gone.

At each step, we'll keep track of the maximum length our window has ever achieved.

Approach: Building Our Sliding Window

We'll use two pointers, left and right, to define our current "window" (substring). We also need a way to quickly check if a character is already in our current window. A Set (or HashSet in some languages) is perfect for this, as it allows for O(1) average time complexity for add, remove, and check operations.

Here's the step-by-step logic:

Initialize:
- left = 0: This pointer marks the beginning of our current unique substring.
- max_length = 0: This will store the maximum length we've found so far.
- char_set = set(): An empty set to store characters currently within our window [left, right].
Iterate with right pointer:
- We'll use a for loop, letting right traverse the input string s from 0 to len(s) - 1. This pointer expands our window to the right.
Check for Duplicates:
- Inside the loop, before adding s[right] to our char_set, we check if s[right] is already in char_set.
- If s[right] IS in char_set (duplicate found):
  - This means our current window s[left...right-1] has a duplicate if s[right] is added.
  - To resolve this, we need to shrink our window from the left side.
  - We enter a while loop:
    - Remove s[left] from char_set.
    - Increment left by 1.
    - Repeat this until s[right] is no longer in char_set. This ensures our window s[left...right-1] is unique before we add s[right].
- If s[right] IS NOT in char_set (unique character):
  - Great! We can safely add s[right] to char_set.
Update max_length:
- After s[right] has been added (and duplicates handled if any), our current window s[left...right] is guaranteed to be unique.
- The length of this current unique window is right - left + 1.
- Update max_length = max(max_length, right - left + 1).
Return:
- After the right pointer has traversed the entire string, max_length will hold the length of the longest substring without repeating characters. Return max_length.

Let's walk through s = "abcabcbb":

`right`	`s[right]`	`char_set` (before add)	Duplicate?	Actions (if duplicate)	`char_set` (after add)	`left`	Current Length (`right - left + 1`)	`max_length`
0	'a'	{}	No	-	{'a'}	0	1	1
1	'b'	{'a'}	No	-	{'a', 'b'}	0	2	2
2	'c'	{'a', 'b'}	No	-	{'a', 'b', 'c'}	0	3	3
3	'a'	{'a', 'b', 'c'}	Yes	`char_set.remove('a')`, `left=1`	{'b', 'c', 'a'}	1	3 (`3 - 1 + 1`)	3
4	'b'	{'b', 'c', 'a'}	Yes	`char_set.remove('b')`, `left=2`	{'c', 'a', 'b'}	2	3 (`4 - 2 + 1`)	3
5	'c'	{'c', 'a', 'b'}	Yes	`char_set.remove('c')`, `left=3`	{'a', 'b', 'c'}	3	3 (`5 - 3 + 1`)	3
6	'b'	{'a', 'b', 'c'}	Yes	`char_set.remove('a')`, `left=4`	{'b', 'c', 'b'}	4	3 (`6 - 4 + 1`)	3
				`char_set.remove('b')`, `left=5`	{'c', 'b'}	5	2 (`6 - 5 + 1`)	3

Final max_length is 3. This trace confirms the logic!

Code: Bringing it to life with Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # A set to keep track of characters in the current window
        char_set = set()

        # Left pointer of the sliding window
        left = 0

        # Variable to store the maximum length found so far
        max_length = 0

        # Right pointer iterates through the string
        for right in range(len(s)):
            # If the character at 'right' is already in our set,
            # it means we have a duplicate within the current window.
            # We need to shrink the window from the 'left' until the duplicate is removed.
            while s[right] in char_set:
                char_set.remove(s[left]) # Remove the character at 'left' from the set
                left += 1                # Move the 'left' pointer one step to the right

            # Now that the current character s[right] is guaranteed to be unique
            # in the window [left...right-1], we can add it to our set.
            char_set.add(s[right])

            # Update the maximum length found.
            # The current window length is (right - left + 1).
            max_length = max(max_length, right - left + 1)

        return max_length

Time & Space Complexity Analysis

Time Complexity: O(N)
- Both the left and right pointers traverse the string s at most once.
- The right pointer moves N times.
- The left pointer also moves at most N times across all iterations of the outer loop.
- Set operations (add, remove, check in) take O(1) average time.
- Therefore, the total time complexity is linear, O(N), where N is the length of the string s.
Space Complexity: O(min(M, N))
- We use a char_set to store unique characters within the window.
- In the worst case, if all characters in the string are unique (e.g., "abcdefg"), the set will store N characters.
- However, if the character set is limited (e.g., lowercase English letters, M=26), the set will store at most M characters.
- So, the space complexity is bounded by the smaller of the string's length N and the size of the character set M.

Key Takeaways

Sliding Window Technique: This problem is a prime example of the "sliding window" pattern, which is incredibly useful for array/string problems involving a contiguous subsegment. It helps optimize solutions from O(N^2) (e.g., checking every possible substring) to O(N).
Set for Uniqueness Checks: Using a hash set (set in Python) is crucial for efficient O(1) average-time lookups, insertions, and deletions, which allows the sliding window to perform optimally.
Two Pointers (Left and Right): The left pointer helps shrink the window when a condition is violated (duplicate found), while the right pointer expands it.

Keep practicing, and you'll master these patterns in no time! Happy coding!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-16 23:08:20

LeetCode Solution: 3. Longest Substring Without Repeating Characters

Hommies — Sat, 16 May 2026 17:30:51 +0000

Cracking LeetCode 3: The Longest Substring Without Repeating Characters (A Sliding Window Adventure!)

Hey Devs! 👋 Ever stumbled upon a LeetCode problem that looks simple but hides a powerful algorithmic pattern? Today, we're diving into LeetCode problem #3, "Longest Substring Without Repeating Characters." This classic problem is a fantastic introduction to a super common and efficient technique: the Sliding Window.

Don't worry if that sounds intimidating – we'll break it down piece by piece, like LEGOs! By the end of this post, you'll not only understand the solution but also gain a valuable tool for tackling similar string and array problems. Let's get started!

The Problem: Unpacking "Longest Substring Without Repeating Characters"

Imagine you're given a string, like "abcabcbb". Your mission, should you choose to accept it, is to find the longest substring within it that doesn't have any character repeated.

Let's clarify some terms:

Substring: A contiguous sequence of characters within a string. "abc" is a substring of "abcabcbb", but "acb" is not.
Without Repeating Characters: Every character in our chosen substring must be unique. No 'a' appearing twice, no 'b' appearing twice, etc.

Examples to make it crystal clear:

Input: s = "abcabcbb"
- "abc" is a substring without repeating characters (length 3).
- "bca" is also valid (length 3).
- "abcab" is NOT valid because 'a' and 'b' repeat.
- The longest one we can find is "abc" (or "bca", "cab"), with a length of 3.
Input: s = "bbbbb"
- The longest substring without repeating characters is just "b" (length 1).
Input: s = "pwwkew"
- "pwke" is NOT a substring; it's a subsequence (characters appear in order but not necessarily contiguously).
- "wke" IS a substring without repeating characters (length 3).
- "pww" has repeating 'w'.
- The longest is "wke" (length 3).

The goal is to return just the length of this longest unique substring.

The Intuition: Why a "Sliding Window"?

If you're new to competitive programming, your first thought might be: "Let's check every possible substring!" And that's a valid starting point. You could have two loops, i and j, generating all substrings s[i:j+1], and for each, check if it has repeating characters. This would work, but it's pretty slow (think O(N^3) or O(N^2) depending on how you check uniqueness). Can we do better? Absolutely!

The "aha!" moment comes when you realize that if you have a substring s[left...right] that contains duplicate characters, you don't need to re-examine the entire string from scratch. You just need to adjust your current substring until it becomes valid again.

This is where the Sliding Window technique shines! Imagine a window "sliding" over the string. This window represents our current substring.

We try to expand the window from the right.
If we add a character that causes a duplicate, we shrink the window from the left until the duplicate is gone.
At each valid step, we keep track of the maximum length our window has achieved.

The Approach: Two Pointers and a Set

Let's formalize our sliding window approach using two pointers, left and right, and a set to efficiently track characters within our current window.

Initialize:
- max_length = 0: This will store our answer.
- left = 0: This pointer marks the beginning of our current unique substring window.
- char_set = set(): This set will hold all characters currently inside our s[left...right] window. Sets are perfect because they only store unique items and offer super fast add, remove, and in (contains) operations (average O(1) time complexity).
Iterate with the right pointer:
- We'll use a for loop with right iterating from 0 to len(s) - 1. This pointer expands our window to the right.
Check for Duplicates and Shrink the Window:
- Inside the loop, before adding s[right] to our char_set, we need to check if s[right] is already in char_set.
- If s[right] is ALREADY in char_set: This means we have a duplicate! Our current window s[left...right-1] was unique, but s[right] broke the rule.
  - To fix this, we need to shrink the window from the left.
  - We repeatedly remove s[left] from char_set and increment left until s[right] is no longer a duplicate within our window.
  - Think of it as kicking out characters from the left until the culprit (the first instance of the duplicate) is gone.
Expand the Window and Update Max Length:
- Once s[right] is guaranteed to be unique within our current (possibly shrunken) window, add s[right] to char_set.
- Now, our current window s[left...right] is valid (all unique characters). Calculate its length: right - left + 1.
- Update max_length = max(max_length, right - left + 1).
Return max_length: After the right pointer has traversed the entire string, max_length will hold the length of the longest substring without repeating characters.

Let's trace s = "abcabcbb":

`right`	`s[right]`	`char_set` (before `s[right]` check)	`s[right]` in `char_set`?	`char_set` (after fix)	`left` (after fix)	`char_set` (after add `s[right]`)	Current Window (`s[left...right]`)	Current Length	`max_length`
`0`	`a`	`{}`	`False`	`{}`	`0`	`{a}`	`a`	`1`	`1`
`1`	`b`	`{a}`	`False`	`{a}`	`0`	`{a, b}`	`ab`	`2`	`2`
`2`	`c`	`{a, b}`	`False`	`{a, b}`	`0`	`{a, b, c}`	`abc`	`3`	`3`
`3`	`a`	`{a, b, c}`	`True` (a repeats)	`{b, c}`	`1`	`{b, c, a}`	`bca`	`3`	`3`
`4`	`b`	`{b, c, a}`	`True` (b repeats)	`{c, a}`	`2`	`{c, a, b}`	`cab`	`3`	`3`
`5`	`c`	`{c, a, b}`	`True` (c repeats)	`{a, b}`	`3`	`{a, b, c}`	`abc`	`3`	`3`
`6`	`b`	`{a, b, c}`	`True` (b repeats)	`{c}`	`5`	`{c, b}`	`cb`	`2`	`3`
`7`	`b`	`{c, b}`	`True` (b repeats)	`{}`	`7`	`{b}`	`b`	`1`	`3`

Finally, max_length is 3! This matches the example.

The Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set() # To store characters in the current window
        left = 0         # Left pointer of the sliding window
        max_length = 0   # Stores the maximum length found so far

        for right in range(len(s)):
            # While the character at 'right' is already in our set (duplicate detected)
            while s[right] in char_set:
                # Remove the character at 'left' from the set
                char_set.remove(s[left])
                # Move the 'left' pointer to shrink the window
                left += 1

            # Add the current character at 'right' to the set
            # Now, the window s[left...right] is guaranteed to have unique characters
            char_set.add(s[right])

            # Update the maximum length found
            max_length = max(max_length, right - left + 1)

        return max_length

Time & Space Complexity Analysis

This is where the sliding window truly shines!

Time Complexity: O(N)
- The right pointer iterates through the string s exactly once, performing N steps.
- The left pointer also iterates through the string at most once (it only moves forward).
- Each character is added to the char_set once and removed from the char_set at most once.
- set operations (add, remove, check in) take average O(1) time.
- Therefore, the total time complexity is linear, O(N), where N is the length of the string s. This is super efficient!
Space Complexity: O(min(N, M))
- char_set stores characters from the current window.
- In the worst case, if all characters are unique, the set could store up to N characters (where N is len(s)).
- However, the maximum size of the char_set is also limited by the size of the character set (e.g., 26 for lowercase English letters, 128 for ASCII, 256 for extended ASCII). Let M be the size of the alphabet.
- So, the space complexity is O(min(N, M)). For typical interview problems dealing with ASCII characters, this is often considered O(1) constant space because M (e.g., 128 or 256) is a fixed constant regardless of the input string's length.

Key Takeaways

Sliding Window Power: This problem is a perfect introduction to the sliding window pattern. Remember it for problems involving finding optimal subarrays or substrings.
Two Pointers: The left and right pointers are crucial for defining and moving the window efficiently.
Hash Set (Set) for Uniqueness: A set is your best friend when you need to quickly check for the presence of an element and ensure uniqueness. Its O(1) average time complexity for lookups, insertions, and deletions is key to the overall efficiency.
Distinguish Substring vs. Subsequence: Always pay attention to whether the problem asks for a substring (contiguous) or a subsequence (order preserved, not necessarily contiguous).

Congratulations! You've successfully navigated one of LeetCode's most popular problems and added the powerful Sliding Window technique to your algorithmic toolkit. Keep practicing, and these patterns will become second nature!

Published by p1Hzd8mRM8 on 2026-05-16 23:00:35

LeetCode Solution: 2. Add Two Numbers

Hommies — Sat, 16 May 2026 17:28:37 +0000

🚀 Cracking LeetCode #2: Adding Two Numbers Like a Pro (with Linked Lists!) 🚀

Hey there, future coding rockstars! 👋 Today, we're diving into a LeetCode classic that often stumps beginners but is incredibly satisfying once you "get" it. We're talking about LeetCode Problem #2: Add Two Numbers.

This problem is a fantastic introduction to manipulating linked lists and thinking about how computers handle fundamental operations like arithmetic. Ready to conquer it? Let's go!

The Problem Explained: Adding Numbers, But Backwards! 🤯

Imagine you want to add two big numbers, like 342 and 465. Normally, you'd write them down and add them from right to left (units, tens, hundreds, etc.), carrying over any extra digits.

Now, imagine these numbers aren't stored as regular integers but as linked lists. If you're new to linked lists, think of them as a chain of boxes (nodes), where each box holds a value and points to the next box in the chain.

The twist? The digits are stored in reverse order!

l1 = [2,4,3] actually represents the number 342. (3 -> 4 -> 2, but read from the head: 2 is units, 4 is tens, 3 is hundreds).
l2 = [5,6,4] actually represents the number 465.

Our goal is to add these two numbers (342 + 465) and return their sum (807) also as a linked list in reverse order: [7,0,8].

Let's look at the examples:

Example 1:
Input: l1 = [2,4,3] (342), l2 = [5,6,4] (465)
Output: [7,0,8] (807)
Explanation: 2 + 5 = 7. 4 + 6 = 10 (0 with carry 1). 3 + 4 + 1 (carry) = 8. So, [7, 0, 8].

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0.

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: This one shows longer lists and the need to handle a final carry! 9,999,999 + 9,999 = 10,009,998.

The "Aha!" Moment: Mimicking Manual Addition 💡

The key to solving this problem lies in realizing that since the digits are already in reverse order, the head of each linked list contains the least significant digit (the "ones" place). This is exactly where we start when we add numbers by hand!

So, the "aha!" moment is: we can simply iterate through both linked lists simultaneously, adding digits just like we would with pen and paper.

For each "place value":

Add the corresponding digits from l1 and l2.
Don't forget to add any carry from the previous addition!
The sum of these three numbers (digit1 + digit2 + carry) will give us a total_sum.
The new digit for our result list will be total_sum % 10 (the remainder when divided by 10).
The new carry for the next iteration will be total_sum // 10 (the quotient when divided by 10).

We continue this process until we've gone through both lists and handled any final carry.

The Step-by-Step Approach 🚶‍♂️

Let's break down the logic into concrete steps:

Initialize a Dummy Head: Create a dummy node. This is a common trick with linked lists! It acts as a placeholder for the beginning of our result list. We'll eventually return dummy.next to skip this placeholder.
Current Pointer for Result: Create a res pointer and point it to dummy. This res pointer will move along as we build our new linked list.
Initialize Carry: Set a carry variable to 0. This will store any carry-over digit from our additions.
Loop Until Done: We need to keep adding as long as there are digits in l1, digits in l2, or a carry remaining. So, our loop condition will be while l1 or l2 or carry:.
Get Current Digits:
- If l1 exists, get its val. Otherwise, consider it 0.
- If l2 exists, get its val. Otherwise, consider it 0.
- This handles lists of unequal lengths gracefully.
Calculate Sum: total_sum = val1 + val2 + carry.
New Digit and New Carry:
- The digit for our new node is total_sum % 10.
- The carry for the next iteration is total_sum // 10.
Create and Append New Node:
- Create a new ListNode with the calculated digit.
- Append this new node to our result list: res.next = new_node.
- Move our res pointer forward: res = res.next.
Advance Input Pointers:
- If l1 is not None, move l1 = l1.next.
- If l2 is not None, move l2 = l2.next.
Return Result: Once the loop finishes, return dummy.next. This skips our initial placeholder node and gives us the actual head of our sum list.

This approach perfectly mimics how we'd add numbers by hand, ensuring we handle carries and lists of different lengths.

The Code 🧑‍💻

Here's the Python implementation based on our approach:

# Definition for singly-linked list.
# This part is usually provided by LeetCode or you define it yourself.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        # 1. Initialize a dummy head for the result list
        dummy_head = ListNode()
        # 2. 'current' pointer to build the result list
        current = dummy_head 

        # 3. Initialize carry to 0
        carry = 0

        # 4. Loop as long as there are digits in either list OR a carry remains
        while l1 is not None or l2 is not None or carry != 0:
            # 5. Get current digits (or 0 if list is exhausted)
            val1 = l1.val if l1 is not None else 0
            val2 = l2.val if l2 is not None else 0

            # 6. Calculate the total sum for the current position
            total_sum = val1 + val2 + carry

            # 7. Determine the digit for the current node and the new carry
            new_digit = total_sum % 10
            carry = total_sum // 10

            # 8. Create a new node and append it to our result list
            current.next = ListNode(new_digit)
            # Move the 'current' pointer forward
            current = current.next

            # 9. Advance input list pointers if they exist
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next

        # 10. Return the actual head of the sum list (skipping the dummy_head)
        return dummy_head.next

Time & Space Complexity Analysis ⏱️📏

Understanding how much time and memory your solution uses is crucial for competitive programming!

Time Complexity: O(max(N, M))
- Where N is the number of nodes in l1 and M is the number of nodes in l2.
- We iterate through both linked lists at most once. The loop continues for a number of iterations equal to the length of the longer list, plus potentially one more if there's a final carry. Hence, the time taken scales linearly with the length of the longer input list.
Space Complexity: O(max(N, M))
- We create a new linked list to store the sum. In the worst case (e.g., adding two numbers like [9,9,9] and [1]), the result list can be one node longer than the longer input list ([0,0,0,1]).
- Therefore, the space used to store the result scales linearly with the length of the longer input list.

Key Takeaways ✨

Simulate Manual Processes: Many problems, especially arithmetic ones, can be solved by translating your "pen-and-paper" method into code.
The Power of a Dummy Node: A dummy head node is a fantastic pattern for simplifying linked list operations, especially when you're building a new list or might need to modify the original head. It avoids annoying edge cases where you'd have to handle the first node creation separately.
Handling Carries and Unequal Lengths: This problem is a great example of how to manage state (the carry) between iterations and gracefully handle inputs of different sizes.
Linked Lists for Big Numbers: Linked lists are often used in computer science to represent numbers of arbitrary length, exceeding what standard integer types can hold.

Congratulations! You've just walked through a fundamental LeetCode problem, learned about linked lists, and developed a solid approach. Keep practicing, and you'll be crushing those interviews in no time!

Authored by p1Hzd8mRM8. Published on 2026-05-16 22:58:14.

LeetCode Solution: 2. Add Two Numbers

Hommies — Sat, 16 May 2026 16:58:02 +0000

Unleash Your Inner Mathematician: Adding Numbers with Linked Lists (LeetCode #2)

Hey awesome developers! 👋 Ever wondered how computers perform basic arithmetic with a twist? Today, we're diving into a classic LeetCode problem that might seem simple on the surface but introduces some fundamental data structures and algorithmic thinking: "Add Two Numbers".

This problem is a fantastic way to sharpen your skills with linked lists and understand how to simulate everyday operations like addition programmatically. Don't worry if linked lists sound intimidating; we'll break it down piece by piece!

📚 Problem Explanation: Digits in Reverse!

Imagine you have two numbers, but instead of seeing them as regular integers like 342 or 465, their digits are stored in a special way: a linked list, and in reverse order!

Each "node" in our linked list holds a single digit. For example:

The number 342 would be represented as a linked list: 2 -> 4 -> 3
The number 465 would be: 5 -> 6 -> 4

Our mission? To add these two numbers together, digit by digit, and return their sum as another linked list, also in reverse order.

Let's look at Example 1:

Input: l1 = [2,4,3] (represents 342)
Input: l2 = [5,6,4] (represents 465)
Output: [7,0,8] (represents 807)

See? 342 + 465 = 807. The [7,0,8] linked list correctly gives us 807 in reverse!

A few important rules:

The lists are non-empty.
Digits are non-negative (0-9).
No leading zeros (unless the number itself is 0, like [0]).

🤔 Intuition: How Do We Add Numbers By Hand?

Before we jump into code, let's think about how you add numbers manually:

  342
+ 465
-----

Start from the rightmost digits: 2 + 5 = 7. Write down 7.
Move to the next digits (tens place): 4 + 6 = 10. Write down 0, and carry over 1 to the hundreds place.
Move to the next digits (hundreds place): 3 + 4 + (the carried-over 1) = 8. Write down 8.

The result is 807.

This "digit-by-digit, with a carry-over" strategy is exactly what we'll replicate with our linked lists! Since the digits are already in reverse order, it's like we're already starting from the rightmost digit (the units place)! This is a huge hint.

🪜 Approach: Step-by-Step with Linked Lists

Our approach will mimic manual addition:

Initialize:
- Create a dummy node. This is a common trick in linked list problems. It acts as a placeholder for the head of our new list. We'll eventually return dummy.next.
- Create a current pointer, initialized to dummy. This pointer will help us build our result list by moving forward.
- Initialize a carry variable to 0. This will store any carry-over from the previous sum.
Iterate through the lists: We need to keep adding digits as long as there are digits in either l1 or l2, or if there's still a carry left over from a previous addition. This while loop condition is crucial: while l1 or l2 or carry:
Calculate the sum for the current position:
- Start total_sum with the carry from the previous step.
- If l1 is not None (meaning there's a digit in the first number), add l1.val to total_sum and move l1 to its next node (l1 = l1.next).
- If l2 is not None (meaning there's a digit in the second number), add l2.val to total_sum and move l2 to its next node (l2 = l2.next).
Determine the current digit and new carry:
- The digit for our result list at the current position will be total_sum % 10 (the remainder after dividing by 10).
- The new carry will be total_sum // 10 (the integer division by 10).
Build the result list:
- Create a new ListNode with the calculated digit.
- Append this new node to our result list: current.next = new_node.
- Move current forward to this new node: current = current.next.
Return: Once the loop finishes, we've built our entire sum list. Return dummy.next to get the actual head of the sum list (skipping the initial placeholder dummy node).

This process continues until both input lists are exhausted AND there's no carry left.

💻 Code: Bringing It to Life (Python)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Create a dummy node to simplify handling the head of the result list
        dummy_head = ListNode()
        # 'current' pointer will build our new linked list
        current = dummy_head

        # Initialize carry to 0
        carry = 0

        # Loop as long as there are digits in either list or a carry exists
        while l1 or l2 or carry:
            # Get the value from l1 (or 0 if l1 is exhausted)
            val1 = l1.val if l1 else 0
            # Get the value from l2 (or 0 if l2 is exhausted)
            val2 = l2.val if l2 else 0

            # Calculate the total sum for the current position
            total_sum = val1 + val2 + carry

            # Determine the digit for the new node (units place of total_sum)
            digit = total_sum % 10
            # Determine the new carry (tens place of total_sum)
            carry = total_sum // 10

            # Create a new node with the calculated digit
            current.next = ListNode(digit)
            # Move our 'current' pointer forward to the new node
            current = current.next

            # Move l1 and l2 pointers forward if they are not exhausted
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        # The first node (dummy_head) was just a placeholder.
        # The actual result list starts from dummy_head.next.
        return dummy_head.next

⏱️ Time & Space Complexity Analysis

Time Complexity: O(max(m, n))

m is the number of nodes in l1.
n is the number of nodes in l2.
We iterate through both linked lists exactly once. The loop runs for a number of times proportional to the length of the longer list. This makes the time complexity linear with respect to the length of the longer input list.

Space Complexity: O(max(m, n))

In the worst-case scenario, the resulting linked list can have max(m, n) + 1 nodes (if there's a final carry-over). We are creating a new linked list to store the sum. Therefore, the space complexity is also linear with respect to the length of the longer input list.

🌟 Key Takeaways

Linked Lists for Arithmetic: This problem beautifully demonstrates how linked lists can be used to represent and manipulate numbers, especially useful when dealing with very large numbers that might exceed standard integer types.
The "Dummy Node" Trick: Using a dummy_head node is a super common and effective pattern in linked list problems. It simplifies code by always having a node to attach to, eliminating special checks for an empty result list or when adding the very first node.
Carry Handling: Understanding how to manage the carry digit is fundamental to correctly implementing addition, whether manually or programmatically.
Simulating Manual Processes: Many algorithmic problems can be solved by breaking them down into steps that mimic how we would solve them in real life.

This problem is a fantastic stepping stone for more complex linked list manipulations and numerical algorithms. Keep practicing, and you'll be a LeetCode master in no time! Happy coding!

Submission Details:
Author Account: p1Hzd8mRM8
Time Published: 2026-05-16 22:27:48

LeetCode Solution: 1. Two Sum

Hommies — Sat, 16 May 2026 16:56:40 +0000

The OG LeetCode Challenge: Cracking Two Sum with Python!

Hey there, future coding rockstars! 👋

Ever wondered what the very first problem on LeetCode is? It's a true classic, a rite of passage for many, and a fantastic way to introduce fundamental data structures and algorithms. Today, we're diving into Two Sum! Don't let the "easy" tag fool you; mastering this problem helps build crucial problem-solving muscles.

Let's break it down together!

🧐 What's the Problem All About? (Problem Explanation)

Imagine you're given a list of numbers, like [2, 7, 11, 15], and a specific target number, say 9. Your mission, should you choose to accept it, is to find two different numbers in that list that add up to your target.

Once you find them, you don't return the numbers themselves, but their positions (their "indices") in the original list.

Example Time!

Input: nums = [2, 7, 11, 15], target = 9
Think: Can we find two numbers that sum to 9?
- 2 + 7 = 9! Bingo!
Output: [0, 1] (Because 2 is at index 0, and 7 is at index 1)

Another Example:

Input: nums = [3, 2, 4], target = 6
Think:
- 3 + 2 = 5 (Nope)
- 3 + 4 = 7 (Nope)
- 2 + 4 = 6! Yes!
Output: [1, 2] (2 is at index 1, 4 is at index 2)

Key things to remember:

You'll always find exactly one solution.
You can't use the same number twice (e.g., if nums had 3 and target was 6, you couldn't use the same 3 to make 3+3). If there are two 3s, you use both distinct 3s.

🤔 Your "Aha!" Moment (Intuition)

How would you solve this as a human, without a computer?

You might pick the first number (2 from [2, 7, 11, 15]), then look at every other number to see if it adds up to 9.

2 + 7 = 9 (Found it!)
If not, you'd try 2 + 11, 2 + 15.
If 2 didn't work with any other number, you'd move to the next number (7) and repeat the process.

This is what we call a brute-force approach. It works, but it can be slow for very long lists. For every number, you're looking at almost all other numbers. If there are N numbers, you might do N * N (or N^2) checks in the worst case. Can we do better?

The Smarter Way: What are we really looking for?

Let's say we pick a number from our list, nums[i]. We know we need another number, let's call it complement, such that:

nums[i] + complement = target

This means complement = target - nums[i].

So, for each nums[i] we encounter, we don't need to try every other number. We just need to quickly check if its specific complement exists somewhere else in our list.

How do we check for existence super fast? With a hash map (or a dictionary in Python)! A hash map allows us to store key-value pairs and look up keys almost instantly.

🚀 The Game Plan (Approach)

We'll use a two-pass hash map approach. This means we'll go through our nums list twice.

First Pass: Build the Lookup Table
- We'll create an empty hashmap (a Python dictionary).
- We iterate through nums one time. For each number nums[i] we see, we'll store it in our hashmap along with its index i.
- So, our hashmap will look something like {number: index}.
  - Example nums = [2, 7, 11, 15]:
    - After this pass, hashmap might be: {2: 0, 7: 1, 11: 2, 15: 3}.
Second Pass: Find the Complement
- Now, we iterate through nums again.
- For each number nums[i]:
  - Calculate its complement: complement = target - nums[i].
  - Check if this complement exists as a key in our hashmap.
  - Crucially, we also need to make sure that the index associated with the complement in the hashmap is not the current index i. This prevents us from trying to use the same number twice.
  - If both conditions are met (complement found, and it's a different number), we've found our pair! Return [i, hashmap[complement]].

Because the problem guarantees exactly one solution, we know we'll find our answer and return from the function during this second pass.

💻 Let's Code!

Here's the Python solution implementing the two-pass hash map approach:

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Step 1: Initialize a hash map (Python dictionary) to store numbers and their indices
        hashmap = {} 

        # First Pass: Populate the hash map
        # We iterate through the array once to store each number and its index.
        # This makes subsequent lookups much faster.
        for i in range(len(nums)):
            hashmap[nums[i]] = i # Store: {number: index}

        # Second Pass: Find the complement
        # Now, we iterate through the array again. For each number, we calculate
        # what its 'complement' should be to reach the target.
        for i in range(len(nums)):
            complement = target - nums[i]

            # Check if the complement exists in our hash map:
            # - `complement in hashmap`: Is the required complement present in our stored numbers?
            # - `hashmap[complement] != i`: Is the complement not the current number itself (i.e., are their indices different)?
            #   This is important because we can't use the same element twice.
            if complement in hashmap and hashmap[complement] != i:
                # If both conditions are true, we found our pair!
                # Return the index of the current number (i) and the index of its complement.
                return [i, hashmap[complement]]

        # This line should ideally not be reached based on the problem constraints
        # (which state that exactly one solution exists).
        return []

⏰ Space and Time Efficiency (Complexity Analysis)

Understanding how efficient your code is, especially for large inputs, is a core skill!

Time Complexity: O(n)
- The first loop (for i in range(len(nums))) iterates n times to populate the hash map. On average, inserting an element into a hash map takes O(1) time. So, the first pass is O(n).
- The second loop (for i in range(len(nums))) also iterates n times. Inside this loop, calculating the complement is O(1), and looking up an element in a hash map takes O(1) time on average. So, the second pass is also O(n).
- Adding them up, O(n) + O(n) = O(2n), which simplifies to O(n). This is much faster than the O(n^2) brute-force approach!
Space Complexity: O(n)
- In the worst-case scenario, we might have to store all n numbers and their indices in our hashmap. Therefore, the space required grows linearly with the number of elements in the input array.

💡 Key Takeaways

Hash Maps are Your Friends: For problems involving quick lookups or checking for the existence of elements, hash maps (dictionaries) are incredibly powerful. They can transform a slow O(n) lookup into an average O(1) operation!
Think Complements: Many problems can be simplified by rephrasing what you're looking for. Instead of "find two numbers that sum to X", think "for each number, find its 'complement' (X - number)".
Optimize Iterations: While a brute-force approach (nested loops, O(n^2)) might be your first thought, always consider if you can reduce the number of passes or operations using a suitable data structure.

This problem, despite being "easy," introduces you to a fundamental pattern used in many more complex LeetCode challenges. Keep practicing, and you'll be solving harder problems in no time!

Happy coding! ✨

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-16 22:26:22