DEV Community: Hommies

LeetCode Solution: 2. Add Two Numbers

Hommies — Sun, 31 May 2026 17:16:54 +0000

Add Two Numbers 🟡 Medium: Summing Up Linked Lists Like a Pro!

Hey there, aspiring algorithm wizards! 👋 ahB1IK4YXF here, ready to demystify another classic LeetCode challenge. Today, we're tackling "Add Two Numbers," a fantastic problem that combines linked lists with some good old-fashioned arithmetic. Don't let the "Medium" tag scare you; we'll break it down step by step, and you'll see it's quite approachable once you grasp the core idea.

The Problem: Adding Numbers Represented by Linked Lists

Imagine you're back in elementary school, learning to add two multi-digit numbers. You line them up, add digit by digit from right to left, and carry over any extra tens. This problem is exactly that, but with a twist: our numbers are represented by linked lists, and their digits are stored in reverse order!

You're given two non-empty linked lists, l1 and l2. Each node contains a single digit (0-9). The digits are stored in reverse order, meaning the head of the list represents the "ones" place, the next node the "tens" place, and so on.

Your task? Add these two numbers and return the sum as a new linked list, also in reverse order.

Example 1: The Magic Reveal

l1 = [2,4,3] represents the number 342.
l2 = [5,6,4] represents the number 465.

If we add 342 + 465, we get 807.
The problem expects the output as [7,0,8], which is 807 in reverse order. Perfect!

Example 2: Simple Zeroes

l1 = [0], l2 = [0]
Output: [0]
(0 + 0 = 0)

Example 3: Handling Carries and Different Lengths

l1 = [9,9,9,9,9,9,9] (represents 9,999,999)
l2 = [9,9,9,9] (represents 9,999)
Output: [8,9,9,9,0,0,0,1] (represents 10,009,998)

Notice how the output list is longer than l2 and even l1 in some cases. This is crucial!

Intuition: Back to Basics (but with pointers!)

At its heart, this problem is just basic addition. Think about how you'd add 15 + 7:

Add the ones digits: 5 + 7 = 12.
Write down '2'.
Carry over '1' to the tens place.
Add the tens digits (including the carry): 1 (from 15) + 0 (from 7) + 1 (carry) = 2.
Write down '2'. Result: 22.

The fact that the linked list digits are in reverse order actually simplifies things for us! The head of the list (l1->val, l2->val) is already our "ones" place. So, we can just iterate through the lists from head to tail, performing digit-by-digit addition just like we would on paper, moving from right to left (which is left to right in our linked lists).

We need a variable to keep track of the carry as we move from one pair of digits to the next.

The Approach: A Step-by-Step Construction

We'll build our result linked list node by node. Here's the plan:

Initialize a Dummy Head: Creating a "dummy" node for our result list is a common and super handy trick in linked list problems. Instead of worrying about creating the very first node of the result list and handling it specially, we create a dummy node, attach our results to dummy.next, and then return dummy.next at the end. This keeps our code clean and consistent.
- ListNode* dummy = new ListNode();
- ListNode* current = dummy; (We'll use current to traverse and add new nodes to the result list).
Initialize Carry: We'll need a variable, carry, initialized to 0, to store any carry-over from previous additions.
- int carry = 0;
Iterate Through the Lists: We'll use a while loop that continues as long as there are digits in l1, or digits in l2, or a carry still needs to be processed. This handles lists of different lengths and the final carry if the sum results in an extra digit (e.g., 99 + 1 = 100).
- while (l1 || l2 || carry)
Calculate the Sum for Current Digits:
- Start total with the carry from the previous step.
- If l1 is not null, add its current digit (l1->val) to total and advance l1 to its next node.
- If l2 is not null, add its current digit (l2->val) to total and advance l2 to its next node.
- This gracefully handles cases where one list is shorter than the other – the if (l1) and if (l2) checks ensure we only add existing digits.
Determine the New Digit and Carry:
- The digit for our new result node is total % 10 (the remainder when divided by 10).
- The new carry is total / 10 (the quotient when divided by 10).
Create and Append New Node:
- Create a new ListNode with the calculated digit.
- Attach this new node to current->next.
- Move current forward to this newly added node: current = current->next; This prepares current to append the next digit.
Return the Result: After the loop finishes, all digits (and any final carry) will have been processed. Our dummy node's next pointer will point to the head of our actual result linked list.
- return dummy->next;
- Important C++ detail: The solution code also includes delete res; where res was the original dummy pointer. This is good practice to free the memory allocated for the initial dummy node itself, as we're returning res->next (the actual result list head) and no longer need the dummy.

The Code

Let's put it all together in C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // Create a dummy node to simplify list construction
        ListNode* dummy = new ListNode();
        ListNode* current = dummy; // 'current' will traverse and build the new list

        int carry = 0; // Initialize carry-over to 0

        // Loop as long as there are digits in either list or a carry remains
        while (l1 || l2 || carry) {
            int total = carry; // Start sum with any carry from previous addition

            // Add digit from l1 if it exists
            if (l1) {
                total += l1->val;
                l1 = l1->next; // Move to the next digit in l1
            }

            // Add digit from l2 if it exists
            if (l2) {
                total += l2->val;
                l2 = l2->next; // Move to the next digit in l2
            }

            // Calculate the digit for the new node and the new carry
            int digit = total % 10; // The current digit is the remainder
            carry = total / 10;   // The new carry is the quotient

            // Create a new node with the calculated digit
            current->next = new ListNode(digit);
            current = current->next; // Move 'current' to the newly added node
        }

        // The actual result list starts from dummy->next
        // We delete the initial dummy node to prevent memory leak (good practice in C++)
        ListNode* result = dummy->next;
        delete dummy; // 'res' in the original code snippet was 'dummy' here
        return result;      
    }
};

Note: The provided solution code snippet uses res as the initial dummy and dummy as the current pointer. My version uses dummy as the initial dummy and current as the traversing pointer, which is a common naming convention. The logic is identical.

Time & Space Complexity Analysis

Time Complexity: O(max(N, M))
- N is the number of nodes in l1, and M is the number of nodes in l2.
- We iterate through both linked lists exactly once. The loop runs for a number of times equal to the length of the longer list (plus possibly one more iteration if there's a final carry).
- Each operation inside the loop (addition, modulo, division, node creation) takes constant time.
- Therefore, the time complexity is directly proportional to 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, the sum list can be one node longer than the maximum length of l1 or l2 (e.g., adding 99 and 1 results in 100, which is three digits while the inputs were two and one).
- So, the number of new nodes created is proportional to the length of the longer input list.

Key Takeaways

Dummy Nodes: A powerful pattern for building new linked lists or modifying existing ones, eliminating edge cases for the head of the list.
Iterative Traversal: For problems requiring processing linked lists linearly, an iterative approach with pointers is often the most straightforward and efficient.
Handling Carries: This problem perfectly illustrates how to manage carry-over values in digit-by-digit operations, a fundamental concept in arithmetic and computer science.
Flexible Loop Conditions: The while (l1 || l2 || carry) condition is elegant. It ensures all digits from both lists are processed, and crucially, accounts for any final carry that might extend the result list.
Modular Arithmetic: Using % 10 to get the current digit and / 10 to get the carry is a classic trick for working with digits.

This problem is a fantastic introduction to linked lists and showcases how data structures can represent everyday concepts in interesting ways. Keep practicing, and you'll be a linked list master in no time!

Submission Details

Author: ahB1IK4YXF
Publishing Time: 2026-05-31 22:46:31
Problem Link: https://leetcode.com/problems/add-two-numbers/

LeetCode Solution: 1. Two Sum

Hommies — Sun, 31 May 2026 17:08:59 +0000

Two Sum 🟢 Easy: Your First Step into LeetCode Magic!

2. Problem Explanation: The Quest for the Perfect Pair

Imagine you have a list of numbers, like [2, 7, 11, 15]. Your goal is to find two numbers from this list that, when added together, equal a specific target number, say 9.

Sounds simple, right? But there's a catch! You don't just return the numbers themselves, you need to return their positions (or indices) in the original list.

Let's look at our example: nums = [2, 7, 11, 15], target = 9.

If we take 2 (at index 0) and 7 (at index 1), their sum is 2 + 7 = 9. Bingo!
So, our answer would be [0, 1].

A few important rules:

Exactly one solution: You're guaranteed to find one pair that works. No need to worry about multiple pairs or no pairs at all.
No duplicates: You can't use the same number twice. If nums = [3, 3] and target = 6, you use the 3 at index 0 and the 3 at index 1. You can't use the 3 at index 0 with itself.
Order doesn't matter: [0, 1] is the same as [1, 0].

This problem, "Two Sum," is often the very first problem people encounter on coding platforms like LeetCode. It's a fantastic way to start building your algorithmic thinking!

3. Intuition: From Brute Force to Brilliant!

When faced with a problem like this, the first thought for many beginners (and even seasoned pros!) is often: "How can I check every single possibility?"

The "Brute Force" Idea (and why we want something better):
You could pick the first number, then go through all the other numbers to see if any of them add up to the target. Then pick the second number, and again, check all subsequent numbers. This looks like nested loops:

For each number 'num1' in the array:
    For each *other* number 'num2' in the array (that hasn't been checked with num1):
        If num1 + num2 == target:
            Return their indices!

This approach works! But imagine our list nums has 10,000 numbers. The outer loop runs 10,000 times, and the inner loop also runs nearly 10,000 times for each outer loop iteration. That's roughly 10,000 * 10,000 = 100,000,000 operations! That's a lot, and for larger lists, it becomes too slow. We call this a O(n^2) (read as "O of n squared") solution, and we can do better!

The "Aha!" Moment: What are we really looking for?

Let's say we pick a number num. If we want num + another_num = target, then another_num must be equal to target - num.

So, for every num we encounter, we're not just looking for any other number. We're looking for a very specific complement number: target - num.

If we could quickly ask, "Hey, have I seen complement before, and if so, where was it?", we could solve this much faster! This is where the magic of a Hash Map (or unordered_map in C++ and dictionary in Python) comes in.

4. Approach: Leveraging the Power of Hash Maps

A hash map is like a super-fast dictionary. You give it a key (like a word), and it immediately tells you its value (like the definition), or if it hasn't seen that key before. This "immediate" lookup usually takes constant time, O(1), which is incredibly efficient!

Here's how we can use a hash map to solve Two Sum in a single pass:

Initialize an empty hash map: This map will store numbers we've seen so far, along with their indices. So, number_value -> its_index.
- Example: {2: 0, 7: 1} means "the number 2 was found at index 0, and the number 7 was found at index 1".
Iterate through the nums array, one number at a time, along with its index.
For each num at current_index:
a. Calculate the complement we need: complement = target - num.
b. Check if complement exists in our hash map.
* If YES, it means we've previously encountered the complement number. We've found our pair!
* The current number is num (at current_index).
* The other number is complement (whose index is stored in the hash map).
* Return [current_index, hash_map[complement]].
* If NO, the complement is not in our map yet. This means num isn't part of a pair with any number we've seen so far.
* So, we add num and its current_index to our hash map: hash_map[num] = current_index. This way, if a future number needs num as its complement, it can find it quickly.

Let's walk through nums = [2, 7, 11, 15], target = 9:

Start: map = {} (empty)
Iteration 1:
- num = 2, current_index = 0
- complement = 9 - 2 = 7
- Is 7 in map? No.
- Add 2 to map: map = {2: 0}
Iteration 2:
- num = 7, current_index = 1
- complement = 9 - 7 = 2
- Is 2 in map? YES! Its index is 0.
- We found the pair! Return [current_index (1), map[2] (0)], which is [1, 0]. (Remember, order doesn't matter, so [0, 1] is also correct).

And just like that, we found the pair in a single pass through the array!

5. Code: Bringing it to Life in C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // We'll use an unordered_map (hash map) to store numbers
        // we've seen and their corresponding indices.
        // Key: The number itself
        // Value: The index where that number was found
        unordered_map<int, int> pairIdx;

        // Iterate through the array `nums` from left to right
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i]; // Get the current number

            // Calculate the 'complement' needed:
            // If num + complement = target, then complement = target - num
            int complement = target - num;

            // Check if this 'complement' already exists in our map.
            // If it does, we've found our pair!
            if (pairIdx.find(complement) != pairIdx.end()) {
                // If complement is found, return its index (from the map)
                // and the current number's index (i).
                return {pairIdx[complement], i}; 
            }

            // If the complement wasn't found, it means the current 'num'
            // doesn't form a pair with any number we've seen so far.
            // So, we add the current 'num' and its 'index' to our map
            // for future numbers to potentially find it as their complement.
            pairIdx[num] = i;
        }

        // According to the problem constraints, there's always exactly one solution,
        // so this line should technically never be reached in a valid test case.
        return {}; 
    }
};

6. Time & Space Complexity Analysis

Understanding how efficient our code is crucial for competitive programming and real-world development! We measure efficiency using "Big O" notation.

Brute Force Approach (nested loops):

Time Complexity: O(n^2)
- We have two nested loops. If n is the number of elements in nums, the outer loop runs n times, and the inner loop runs approximately n times for each outer iteration. This leads to n * n operations in the worst case.
Space Complexity: O(1)
- This approach uses a constant amount of extra space (just a few variables for loop counters, etc.), regardless of the input array size.

Hash Map Approach (our solution):

Time Complexity: O(n)
- We iterate through the nums array only once.
- Inside the loop, hash map operations (find and insertion []) take O(1) time on average. In the worst case (due to hash collisions), they can degrade to O(n), but this is rare with good hash functions and typically averaged out.
- Since we do a constant amount of work for each of the n elements, the total time complexity is linear, O(n). This is significantly faster than O(n^2) for large n!
Space Complexity: O(n)
- In the worst-case scenario, if no pair is found until the very last element, our hash map could end up storing all n elements from the nums array. Each element stored takes up some memory. Thus, the space required grows linearly with the input size n.

This is a classic example of a time-space trade-off: by using extra space (for the hash map), we dramatically reduce the time it takes to find the solution!

7. Key Takeaways

The Power of Hash Maps: For problems requiring fast lookups (checking if an element exists, or getting its associated value), hash maps (or hash tables) are your best friend! They can often turn O(n) or O(n^2) search problems into O(1) average-time lookups.
Complementary Thinking: Many "sum" or "difference" problems can be reframed. Instead of searching for any two numbers, think: if I have X, what Y do I need (target - X)? Then, how fast can I find Y?
Time-Space Trade-off: Sometimes, using more memory (space) can lead to much faster execution times. This is a common design pattern in algorithms.
Foundation Problem: Two Sum is a fundamental problem. Mastering it builds a strong foundation for tackling more complex algorithmic challenges! It teaches you to look beyond the obvious brute-force and consider data structures that optimize specific operations.

8. Submission Details

Author Account: ahB1IK4YXF
Publishing Time: 2026-05-31 22:38:38

LeetCode Solution: 17. Letter Combinations of a Phone Number

Hommies — Sun, 31 May 2026 17:05:55 +0000

Cracking the Code: Phone Number Letter Combinations (LeetCode 17) 🟡 Medium

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-31 22:35:29

Hey fellow coders! 👋 Have you ever wondered how old-school phone keypads could translate into a fun coding challenge? Today, we're diving into LeetCode problem 17: "Letter Combinations of a Phone Number." It's a fantastic problem to introduce you to the powerful concept of backtracking – a fundamental technique in competitive programming!

Don't worry if "backtracking" sounds intimidating. We'll break it down step-by-step, making it super clear and enjoyable. Let's get started! 🚀

2. Problem Explanation

Imagine an old-fashioned telephone keypad. Each digit (from 2 to 9) corresponds to a set of letters:

2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz

(Note: 1 doesn't map to any letters in this problem, just like on actual keypads for letters.)

The problem asks us to take a string of digits (e.g., "23") and return all possible letter combinations that these digits could represent.

Example 1: digits = "23"

2 maps to a, b, c
3 maps to d, e, f

If we combine them, we get:
ad, ae, af
bd, be, bf
cd, ce, cf
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2: digits = "2"

2 maps to a, b, c Output: ["a","b","c"]

Constraints:

The input digits string will have a length between 1 and 4.
Each character in digits will be a digit from '2' to '9'.

These constraints are quite friendly, meaning we don't have to worry about huge inputs, which is great for our chosen approach!

3. Intuition: Building Blocks and Choices

How do we even begin to generate all these combinations? Let's think about digits = "23":

We start with the first digit, '2'. What are our choices? a, b, or c.
Let's pick 'a'. Now, we move to the next digit, '3'. What are our choices for '3'? d, e, or f.
If we picked 'a' and then 'd', we get "ad". We've used all digits, so "ad" is a valid combination!
But what if after 'a', we picked 'e'? We get "ae".
And then 'f'? We get "af".

Notice a pattern? For each digit, we explore all its possible letters. This sounds a lot like building a tree of choices!

Level 0 (Start): Empty string
Level 1 (Digit '2'):
- Choose 'a'
- Choose 'b'
- Choose 'c'
Level 2 (Digit '3'):
- If 'a' was chosen, then choose 'd', 'e', 'f'
- If 'b' was chosen, then choose 'd', 'e', 'f'
- If 'c' was chosen, then choose 'd', 'e', 'f'

This "explore all possibilities" and then "build up the result" is the core idea behind backtracking (or recursion).

4. Approach: The Backtracking Magic ✨

Backtracking is essentially a refined brute-force approach. You systematically try every possible path to find a solution. If a path doesn't lead to a solution (or leads to an invalid one), you "backtrack" (undo your last choice) and try another path.

For this problem, we'll use a recursive function:

Mapping: First, we need a way to quickly look up letters for each digit. A dictionary (or hash map) is perfect for this.

digit_to_letters = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}

The Recursive Helper Function (backtrack):
- It will take two main arguments:
  - idx: The index of the digit we are currently processing in the input digits string.
  - current_combination: The string built so far.
- It also needs access to digits (the input string) and res (the list where we'll store our final combinations).
Base Case:
- When do we know we've formed a complete combination? When idx (our current digit index) reaches the len(digits). This means we've processed all the digits.
- At this point, we add our current_combination to our res list and return (stop this path of recursion).
Recursive Step:
- Get the current_digit using digits[idx].
- Look up its corresponding letters using our digit_to_letters map.
- Now, iterate through each letter in these letters:
  - For each letter, we make a choice: append it to our current_combination.
  - Then, we make a recursive call to backtrack, moving to the next digit (idx + 1) and passing our updated combination (current_combination + letter).
- Crucially, when the recursive call returns, because we are passing new strings (current_combination + letter), Python handles the "backtracking" part automatically. The current_combination in the current function call remains unchanged for the next iteration of the loop, allowing us to explore other choices from the current_digit.

Let's trace digits = "23" again with this logic:

backtrack(0, "")
idx = 0, current_combination = ""
current_digit = '2', letters = "abc"
* Loop for 'a':
backtrack(1, "a")
idx = 1, current_combination = "a"
current_digit = '3', letters = "def"
* Loop for 'd':
backtrack(2, "ad")
idx = 2, len(digits) = 2. idx == len(digits) is TRUE.
res.append("ad")
return
* Loop for 'e':
backtrack(2, "ae")
idx = 2. res.append("ae"). return
* Loop for 'f':
backtrack(2, "af"). res.append("af"). return
return (from backtrack(1, "a"))
* Loop for 'b':
backtrack(1, "b")
... (similar process for "bd", "be", "bf") ...
return
* Loop for 'c':
backtrack(1, "c")
... (similar process for "cd", "ce", "cf") ...
return
return res (from initial call)

This methodical exploration ensures we hit every single possible combination!

5. Code

Here's the Python implementation based on our backtracking approach:

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # Handle the edge case where the input is an empty string
        # Although constraints say 1 <= digits.length, it's good practice.
        if not digits:
            return []

        # Mapping of digits to letters
        digit_to_letters = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        # This list will store all the final combinations
        res = []

        # The backtracking recursive helper function
        # idx: current digit index we are processing
        # current_combination: the string built so far
        def backtrack(idx: int, current_combination: str):
            # Base case: If we have processed all digits
            # The length of our current_combination should be equal to the
            # total number of digits in the input.
            if idx == len(digits):
                res.append(current_combination)
                return

            # Get the current digit and its corresponding letters
            current_digit = digits[idx]
            letters = digit_to_letters[current_digit]

            # Iterate through each letter for the current digit
            for letter in letters:
                # Make a choice: append the letter to our combination
                # Then, recursively call backtrack for the next digit
                # with the updated combination.
                backtrack(idx + 1, current_combination + letter)

        # Start the backtracking process from the first digit (index 0)
        # with an empty initial combination string.
        backtrack(0, "")

        return res

6. Time & Space Complexity Analysis

Let N be the length of the input digits string.
Let M be the maximum number of letters a digit can map to (which is 4 for '7' and '9', and 3 for others).

Time Complexity: `O(M^N * N)`

In the worst case, each digit can map to M (approximately 4) letters.
Since we have N digits, and for each digit, we explore M choices, the total number of combinations generated will be roughly M^N.
- For digits = "23", N=2, M=3 (avg). Combinations: 3 * 3 = 9.
- For digits = "79", N=2, M=4. Combinations: 4 * 4 = 16.
For each combination, we are building a string of length N. Appending characters to a string (or concatenating strings) in Python takes O(length_of_new_string) time. In our case, current_combination + letter creates a new string.
Therefore, generating each of the M^N combinations takes O(N) time.
Total time complexity: O(M^N * N).

Given N is very small (max 4), this M^N * N complexity is perfectly acceptable. For N=4 and M=4, 4^4 * 4 = 256 * 4 = 1024 operations, which is incredibly fast!

Space Complexity: `O(M^N * N)`

Recursion Stack Space: The maximum depth of the recursion is N (one call for each digit). So, the space for the call stack is O(N).
Result Storage: We store all the generated combinations in the res list.
- There are M^N total combinations.
- Each combination string has a length of N.
- Therefore, the space required to store the results is O(M^N * N).

Combining these, the dominant factor is storing the results, so the overall space complexity is O(M^N * N).

7. Key Takeaways

Backtracking for Combinations: This problem is a classic example of when to use backtracking. Whenever you need to find all possible combinations or all possible paths by making a series of choices, backtracking is your go-to.
Recursive Structure: Backtracking problems are inherently recursive. Identify your:
- Base Case: When do you stop recursing and record a result? (Here: when idx == len(digits)).
- Recursive Step: How do you make a choice, recurse, and then potentially undo/try another choice? (Here: loop through letters, append, recurse).
State Management: Pay attention to how you pass and update your current_combination. In Python, string concatenation (+) creates new strings, which simplifies "undoing" (as the previous string state remains intact in the caller's scope).
Mapping: Using a dictionary (digit_to_letters) for quick lookups is efficient and clean.
Complexity: While backtracking can look exponential (M^N), it's often the nature of combinatoric problems. Always check constraints (N up to 4 here) to ensure your exponential solution is feasible.

8. Submission Details

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-31 22:35:29

This problem is an excellent stepping stone for understanding more complex backtracking problems like N-Queens, Sudoku Solver, or Permutations. Master this one, and you're well on your way! Keep coding and happy problem-solving! 🥳

LeetCode Solution: 15. 3Sum

Hommies — Sun, 31 May 2026 16:53:35 +0000

Cracking the Code: Solving LeetCode's 3Sum Problem with Two Pointers 🟡 Medium

Hey there, fellow coders! 👋 Today, we're diving into a classic LeetCode problem that might seem daunting at first glance but becomes a satisfying puzzle with the right approach: 15. 3Sum. It's a fantastic problem to sharpen your problem-solving skills, especially with arrays and pointers.

Problem Explanation

We're given an array of integers, nums. Our mission is to find all unique triplets [nums[i], nums[j], nums[k]] such that:

i, j, and k are distinct indices (meaning i != j, i != k, and j != k).
The sum of the three numbers nums[i] + nums[j] + nums[k] equals zero.
The final solution set must not contain duplicate triplets. For example, [-1, 0, 1] and [0, -1, 1] are considered the same triplet.

Let's look at an example:

Input: nums = [-1,0,1,2,-1,-4]

Here, we need to find three numbers that add up to 0. Some possibilities are:

(-1) + 0 + 1 = 0 (indices 0, 1, 2)
(-1) + 2 + (-1) = 0 (indices 0, 3, 4)

The distinct triplets in the output would be [[-1,-1,2], [-1,0,1]].

Constraints are also important:

The array will have between 3 and 3000 elements.
Numbers range from -10^5 to 10^5.

Intuition

First thoughts often lead to brute force: three nested loops to check every possible combination of i, j, and k. This would be an O(N^3) solution, which is usually too slow for arrays up to 3000 elements (3000^3 is huge!). We need a smarter way.

What if we could fix one number and then find two others? This reminds us of the "Two Sum" problem! If we fix nums[i], we then need to find two other numbers, nums[j] and nums[k], such that nums[j] + nums[k] = -nums[i].

How can we efficiently find two numbers that sum to a target? This is where sorting and the Two-Pointer technique shine!

Approach

Here's the step-by-step breakdown of an efficient approach:

Sort the Array:
- This is the cornerstone. Sorting nums allows us to easily move pointers and efficiently skip duplicate numbers. It also makes it simple to adjust our sum (if it's too small, increase a number; if too large, decrease a number).
Iterate and Fix the First Element (nums[i]):
- We'll use a single loop (for i in range(n)) to pick the first number of our potential triplet.
- Skip Duplicates for nums[i]: Since we want unique triplets, if nums[i] is the same as the previous nums[i-1], we've already considered all triplets starting with nums[i-1]. So, we can continue to the next i. This is crucial for avoiding duplicate triplets like [-1, 0, 1] and [-1, 0, 1] if -1 appears multiple times at the start of the array.
Use the Two-Pointer Technique for the Remaining Two Elements:
- Once nums[i] is fixed, our target sum for the remaining two numbers nums[j] and nums[k] becomes target = -nums[i].
- Initialize two pointers: j starting at i + 1 (the element right after nums[i]) and k starting at n - 1 (the last element of the array).
- Enter a while j < k loop:
  - Calculate the current_sum = nums[j] + nums[k].
  - If current_sum < target: The sum is too small. To increase the sum, we need a larger number. Since the array is sorted, increment j (move the left pointer to the right).
  - If current_sum > target: The sum is too large. To decrease the sum, we need a smaller number. Decrement k (move the right pointer to the left).
  - If current_sum == target: We found a triplet! [nums[i], nums[j], nums[k]]. Add it to our ans list.
    - Then, we need to move both pointers to find other potential triplets. Increment j and decrement k.
    - Skip Duplicates for nums[j] and nums[k]: After finding a valid triplet, nums[j] and nums[k] might have duplicates. To ensure unique triplets, we need to advance j as long as nums[j] is equal to the previous nums[j-1], and similarly for k (as long as nums[k] is equal to nums[k+1]).

This combined strategy transforms an O(N^3) brute force into a much more efficient O(N^2) solution!

Code

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        ans = []
        n = len(nums)
        nums.sort() # Step 1: Sort the array

        for i in range(n): # Step 2: Iterate fixing the first element
            # Skip duplicate for the first element
            # We check i > 0 to avoid index out of bounds on the first element
            if i > 0 and nums[i] == nums[i-1]:
                continue

            j = i + 1 # Left pointer starts after i
            k = n - 1 # Right pointer starts at the end of the array

            # Step 3: Two-pointer approach
            while j < k:
                total_sum = nums[i] + nums[j] + nums[k]

                if total_sum < 0:
                    j += 1 # Need a larger sum, move left pointer right
                elif total_sum > 0:
                    k -= 1 # Need a smaller sum, move right pointer left
                else: # total_sum == 0, found a triplet!
                    ans.append([nums[i], nums[j], nums[k]])

                    # Move pointers and skip duplicates for j and k
                    j += 1
                    k -= 1
                    # Skip duplicates for j
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                    # Skip duplicates for k
                    while j < k and nums[k] == nums[k+1]:
                        k -= 1
        return ans

Time & Space Complexity Analysis

Time Complexity:
- Sorting the array: This takes O(N log N) time.
- Outer loop (for i): This loop runs N times.
- Inner while loop (Two Pointers j and k): In the worst case, the j and k pointers traverse the remaining array once for each i. This takes O(N) time.
- Skipping duplicates: These while loops also run at most N times in total across all j and k movements for a fixed i.
- Combining these, the dominant part is N (for i) multiplied by N (for j and k traversal), which is O(N^2).
- Therefore, the total time complexity is O(N log N + N^2), which simplifies to O(N^2).
Space Complexity:
- Sorting: Python's list.sort() typically uses Timsort, which can take O(N) auxiliary space in the worst case (though often less). If we consider the algorithm itself beyond the standard library sort implementation, an in-place sort would be O(1) auxiliary space.
- Result list (ans): The space required to store the output triplets depends on the number of unique triplets. In the worst case, this could be O(N^2). However, typically, when we talk about space complexity, we're referring to auxiliary space used by the algorithm, not including the input or the required output.
- Excluding the output, the auxiliary space complexity is primarily due to sorting, which is O(N) for Python's default sort, or O(log N) for certain in-place sorts.

Key Takeaways

Sort First! For many array problems involving searching for combinations or manipulating relative order, sorting is often the key preprocessing step.
Two Pointers for Sorted Arrays: This technique is a workhorse! It efficiently finds pairs or helps reduce search space in sorted arrays.
Handle Duplicates Carefully: Unique results often mean adding extra checks to skip elements that would lead to redundant calculations or duplicate outputs. This is a common pitfall in these types of problems.

Submission Details

Authored by: p1Hzd8mRM8
Published: 2026-05-31 22:23:04

That's it for 3Sum! This problem is a fantastic way to practice combining sorting with the two-pointer technique and mastering duplicate handling. Keep coding, and happy problem-solving! ✨

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

DEV Community: Hommies

LeetCode Solution: 2. Add Two Numbers

The Problem: Adding Numbers Represented by Linked Lists

Intuition: Back to Basics (but with pointers!)

The Approach: A Step-by-Step Construction

The Code

Time & Space Complexity Analysis

Key Takeaways

Submission Details

LeetCode Solution: 1. Two Sum

2. Problem Explanation: The Quest for the Perfect Pair

3. Intuition: From Brute Force to Brilliant!

4. Approach: Leveraging the Power of Hash Maps

5. Code: Bringing it to Life in C++

6. Time & Space Complexity Analysis

7. Key Takeaways

8. Submission Details

LeetCode Solution: 17. Letter Combinations of a Phone Number

Cracking the Code: Phone Number Letter Combinations (LeetCode 17) 🟡 Medium

2. Problem Explanation

3. Intuition: Building Blocks and Choices

4. Approach: The Backtracking Magic ✨

5. Code

6. Time & Space Complexity Analysis

Time Complexity: O(M^N * N)

Space Complexity: O(M^N * N)

7. Key Takeaways

8. Submission Details

LeetCode Solution: 15. 3Sum

Cracking the Code: Solving LeetCode's 3Sum Problem with Two Pointers 🟡 Medium

Problem Explanation

Intuition

Approach

Code

Time & Space Complexity Analysis

Key Takeaways

Submission Details

LeetCode Solution: 13. Roman to Integer

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

The Roman Numeral Mystery (Problem Explanation)

The "Aha!" Moment (Intuition)

Your Step-by-Step Guide (Approach)

The Code (Python)

Performance Check (Time & Space Complexity)

Key Takeaways

LeetCode Solution: 12. Integer to Roman

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

🧐 Problem Explanation: What are Roman Numerals Anyway?

🤔 Intuition: The "Aha!" Moment

✍️ Approach: Step-by-Step Greedy Conversion

💻 Code

⏱️ Time & Space Complexity Analysis

🎯 Key Takeaways

LeetCode Solution: 10. Regular Expression Matching

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

The Puzzle: Regular Expression Matching

The "Aha!" Moment: Intuition

Our Strategy: Dynamic Programming Grid

Step 1: Initialize the DP Table

Step 2: Fill the DP Table

Step 3: The Result

The Code

Time and Space Complexity Analysis

Key Takeaways

LeetCode Solution: 10. Regular Expression Matching

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

The Problem: Regular Expression Matching 🤯

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

The Approach: Building Our DP Table 🏗️

1. Initialization (Base Cases)

2. Filling the DP Table (Iterative Logic)

The Code ✨

Time & Space Complexity Analysis ⏱️

Key Takeaways ✨

LeetCode Solution: 7. Reverse Integer

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

Problem Explanation

Intuition

Approach

Code

Time Complexity: `O(M^N * N)`

Space Complexity: `O(M^N * N)`