Forem: Logixy

Median of Two Sorted Arrays — LeetCode #4 (Hard)

Shubham Gupta — Tue, 19 May 2026 09:30:58 +0000

The Problem

Given two sorted arrays, return the median of all their elements combined, in logarithmic time.

Example

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

merged array = [1,2,3] and median is 2.

Constraints

0 <= m, n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
Required runtime: O(log(m+n))

The Key Insight

Let's slow down. Look at what the merge throws away. We carefully ordered all eleven numbers. But we only needed the one in the middle. The rest was wasted effort.

Here's the real question. What does the median actually tell us about how the numbers are split? The median is the point where the numbers divide into a smaller half and a larger half. Equal sized halves when the total's even; otherwise the left half gets one extra.

So forget merging. What if we just drew a dividing line through each array, a left part and a right part? Eleven numbers total. We want six on the left, five on the right. That left count never changes.

Here's the move. If we cut the first array, the cut in the second is forced. Both left parts together must add up to six. So we only choose one thing: where to cut the smaller array. The other cut follows automatically.

When is a cut correct? Every number on the left must be less than or equal to every number on the right. Because both arrays are sorted, we only check the four numbers touching the cut lines: the two ends of the left, the two starts of the right.

The test is simple. The first array's left edge must not exceed the second array's right edge, and the other way around too. And to find the right cut, we don't try every spot. We binary search, like guessing a number while halving the range each time.

Watch out for one trap. You might pick the bigger array to search. Don't. Cut the smaller one, or its forced cut can fall off the edge. And when a cut sits at the very start or end, there's no number there. We treat a missing left edge as negative infinity, a missing right edge as positive infinity.

Why It Works

Notice what we never did. We never merged the lists. Each guess threw away half the remaining cut positions, so a few guesses were enough.

Walking Through It

Let's trace it. First list: one, three, eight, nine, fifteen. Second list: seven, eleven, eighteen, nineteen, twenty-one, twenty-five. Eleven numbers total. The left half needs six. We binary search the cuts of the smaller first array.

The cut in the first array can be anywhere from zero to five. Start the search: low is zero, high is five. Midpoint of the search is cut position two. That puts two numbers from the first array on the left, so the second gives four.

Now the four border numbers. First array: left edge three, right edge eight. Second array: left edge nineteen, right edge twenty-one. Check one: is the first array's left edge, three, less than or equal to the second's right edge, twenty-one? Yes.

Check two: is the second array's left edge, nineteen, less than or equal to the first's right edge, eight? No. Nineteen is way too big. So this cut is wrong. The second array put too many numbers on its left. We need more from the first array instead.

Move the search to the right. Low becomes three. Try again. New midpoint cut: position four. Four numbers from the first array on the left, so the second gives just two.

Border numbers now. First array: left edge nine, right edge fifteen. Second array: left edge eleven, right edge eighteen. Check one: first array's left edge nine, less than or equal to the second's right edge eighteen? Yes.

Check two: second array's left edge eleven, less than or equal to the first's right edge fifteen? Yes. Both pass. This cut is valid. The left half holds the six smallest numbers, the right half the five largest.

The total, eleven, is odd. The median is the largest number on the left: the bigger of nine and eleven, which is eleven.

Complexity

Each step halves the cuts still worth considering. So the number of steps grows with the logarithm of the smaller array's length. And we only ever store a few border values, never a merged list. The memory stays constant no matter how big the inputs grow.

The Code

OK, same logic in Python. Swap so A is the smaller array, work out the left half size, and set the search bounds on A's cut. Each loop pass picks a cut in A, and the cut in B follows automatically, since the left half size is fixed.

Read the four border values. When a cut sits at an edge, fall back to negative or positive infinity. If both checks pass, the cut is valid. An odd total returns the largest left value, an even total averages the two middle ones.

Otherwise shift the search. If A's left edge is too big, go left. Otherwise go right, and try again.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        A, B = nums1, nums2
        if len(A) > len(B):
            A, B = B, A
        m, n = len(A), len(B)
        half = (m + n + 1) // 2
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
            left1 = A[i - 1] if i > 0 else float('-inf')
            right1 = A[i] if i < m else float('inf')
            left2 = B[j - 1] if j > 0 else float('-inf')
            right2 = B[j] if j < n else float('inf')
            if left1 <= right2 and left2 <= right1:
                if (m + n) % 2:
                    return max(left1, left2)
                return (max(left1, left2) + min(right1, right2)) / 2.0
            elif left1 > right2:
                hi = i - 1
            else:
                lo = i + 1

Wrap-up

And that's the trick. Stop merging, start cutting. When a problem demands O(log n) time, ask what you can throw away each step.

📺 Watch the full walkthrough on YouTube: https://youtu.be/6e5TLbzYyaw

Narration uses an AI-generated voice (Supertonic TTS).

Longest Substring Without Repeating Characters — LeetCode #3 (Medium)

Shubham Gupta — Mon, 18 May 2026 19:32:33 +0000

The Problem

Given a string s, return the length of the longest substring that contains no duplicate characters.

Example

Input: s = "abcabcbb"

Output: 3

The answer is "abc", with the length of 3. Note that
"bca"
and
"cab"
are also correct answers.

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces

The Key Insight

Here's what we're throwing away. When we hit the duplicate 'a', we already knew the window held 'a', 'b', 'c'. We had that information. What if instead of restarting, we just nudged the left edge forward until the duplicate was gone?

That's the sliding window. A left pointer and a right pointer. Right grows the window, left shrinks it. We need instant answers: is this character already in the window? That's a set. Think of a guest list, names only, no duplicates.

You might think to add the character first, then check. Don't. Check first, then add, or you'd match a character against itself. The rule: while right's character is in the set, remove from the left and slide left forward. Then add right's character.

Why It Works

Notice what happened. Both pointers only ever moved right. Every character entered the set once and left once. No backtracking.

Walking Through It

Left and right both start at zero. 'a' is not in the empty set. We add it. Window is one wide. Max is one. Right moves to one. 'b' is not in the set. Add it. Window spans zero to one. Max is two.

Right to two. 'c' is not in the set. Add it. Window is three wide. Max becomes three. Right to three. That's 'a' again. 'a' is already in the set. Duplicate.

Remove 'a' at index zero, slide left to one. 'a' is out of the set. Add the new 'a'. Window spans one to three. Right to four. 'b' is in the set. Remove 'b' at left, slide to two. Add new 'b'. Window is two to four. Max still three.

Right to five. 'c' repeats. Remove 'c' at left, slide to three. Add 'c'. Window three to five. Max still three. Right to six. 'b' is in the set. Remove 'a' at left, slide. 'b' is still there. Remove 'b' too, slide again.

Now 'b' is clear. Add it. Window is just two wide. Right finishes at seven the same way. Max never exceeded three.

Complexity

Each character enters the window once and leaves once. The set holds only the current window. Time and memory both grow with the string's length.

The Code

OK, same logic in Python. We initialize the set, the left pointer, and the running max. The outer loop walks right one step at a time through every character.

The inner while keeps removing from the left until the repeat is out of the set. Then we add the new character and check if this window beats our best.

Hand back the best length we found.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        max_len = 0
        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])
            max_len = max(max_len, right - left + 1)
        return max_len

Wrap-up

And that's the pattern. Grow until you can't, shrink until you can. You'll see this shape again.

📺 Watch the full walkthrough on YouTube: https://youtu.be/DgPbYhD4FMw

Narration uses an AI-generated voice (Supertonic TTS).

Add Two Numbers — LeetCode #2 (Medium)

Shubham Gupta — Mon, 18 May 2026 14:16:25 +0000

The Problem

Add two numbers whose digits are stored as nodes of two linked lists in reverse order, and return the sum as a linked list.

Example

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

342 + 465 = 807.

Constraints

Each list has 1 to 100 nodes
Each node value is a single digit, 0 to 9
No leading zeros except the number 0 itself

The Key Insight

Now think about how you'd add by hand. You don't glue the digits into one number first. You go column by column. So what if we do exactly that here? Take the two matching digits, add just those, write down one result, and move on.

That's the move. Column-by-column addition. And since the digits are already reversed, the ones column comes first. That lines up perfectly. One catch. Four plus six is ten. Ten doesn't fit in a single digit slot, so we keep the last digit and carry the one forward.

That carry is the only memory we need. It's just one small number, handed from each column to the next one. Watch out for one mistake. You might think to stop once both lists run out. But if the last column carried a one, you still owe one more digit.

Why It Works

Notice what we never did. We never built those big numbers. Each digit got touched once, and the carry held the only memory we needed.

Walking Through It

Let's run it. Carry starts at zero. We also keep a fake starting node, so attaching the very first digit needs no special handling. First column. Two plus five is seven, plus a carry of zero. Nothing spills over, so we attach a node holding seven.

Next column. Four plus six is ten. Ten won't fit in one digit slot, so something has to give. We keep the last digit, which is zero, and attach a node holding zero. The leftover one becomes the carry into the next column.

Last column. Three plus four is seven, plus the carried one, that makes eight. We attach a node holding eight. Both lists are empty now, and the carry is zero. There's nothing left to add, so we stop.

Drop the fake node, and the answer starts at seven. Read it out as a whole, eight hundred seven. Correct.

Complexity

We walk each list one time, so the time grows with the longer list. The answer holds one node per digit, so the memory grows the same way.

The Code

Same logic, now in Python. We make a fake starting node, a pointer to build from, and set the carry to zero. The loop keeps running while either list still has a digit, or there's a leftover carry. That last part catches the final one.

Inside, we read each digit. If a list has already run out, we treat its digit as zero, so two different lengths just work. We add the two digits and the carry. The new carry is whatever spilled past ten, and the new node takes the last digit.

Then we step all the pointers forward. When the loop ends, we hand back the list that starts right after the fake node.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode()
        curr = dummy
        carry = 0
        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            total = x + y + carry
            carry = total // 10
            curr.next = ListNode(total % 10)
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

Wrap-up

And that's it. Column by column, carry the one. It's the same addition you learned in grade school, just walking a list.

📺 Watch the full walkthrough on YouTube: https://youtu.be/wz9Dhg5LYqI

Two Sum — LeetCode #1 (Easy)

Shubham Gupta — Sun, 17 May 2026 12:39:39 +0000

TL;DR

Single-pass hash map lookup: store each number's index as you go, check for the complement before storing. O(n) time, O(n) space.

The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

The answer is indices 0 and 1 because nums[0] + nums[1] == 9. Note: return indices, not values.

Constraints

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Exactly one valid answer exists.

Naive Approach

Fix one number, scan every number after it for the complement. Repeat for each starting index.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

O(n²) time, O(1) space — ~50 million pair checks on a 10,000-element array.

Key Insight

At every index i, you already know the complement you need: target - nums[i]. The only question is whether that value appeared earlier. Instead of scanning backwards, keep a hash map that answers "have I seen value v?" in O(1).

Two things to get right: use the value as the key and the index as the value (you look up by value, you want to retrieve the index); and check the map before inserting the current number, so a value can't match itself.

Optimal Solution

One pass. For each element, compute need = target - x. If need is already in seen, you're done. Otherwise, record x → i and continue.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i

Step-by-step on [2, 7, 11, 15], target 9:

i=0, x=2 — need=7. seen={}, not found. Store seen[2]=0.
i=1, x=7 — need=2. seen={2:0}, found. Return [seen[2], 1] → [0, 1].

The loop never reaches indices 2 or 3.

Complexity

Approach	Time	Space
Naive (nested loops)	O(n²)	O(1)
Hash map (one pass)	O(n)	O(n)

Pattern Recognition

This is the complement lookup pattern: when a problem asks for a pair satisfying some condition, storing what you've seen in a hash map turns a second scan into a O(1) lookup. You'll find the same structure in 3Sum (reduce to Two Sum), subarray sum equals k, and any problem where "what do I need to complete this?" has a clear formula.

In Interviews

The brute force buys you nothing here — interviewers expect the hash map solution immediately. What they're actually watching for: correct key/value orientation in the map, and the check-before-insert rule (if seen[x] = i runs before the lookup, x + x == target would return [i, i] — wrong).

Common follow-ups:

What if multiple valid pairs exist — return all of them? Collect results instead of returning early; decide whether to deduplicate.
What if the array is sorted? Two-pointer from both ends achieves O(n) time with O(1) space — no hash map needed.

📺 Watch the full walkthrough on YouTube: https://youtu.be/4JUNrRN16gM