DSA sheet · Recursion · Divide and conquer pattern

Median of Two Sorted Arrays

This question comes right after binary search and merge sort in the divide and conquer pattern. The teacher says merge sort is a prerequisite, because the whole solution is the merge step of merge sort: two arrays that are already sorted, walked with two pointers. The new trick is that we don't build the merged array. We just count our way to the middle and stop there.

She mentions that the best solution uses binary search, but in this video she teaches the merge approach. So this page covers: the brute force she rejects, her merge walk (in full), the same walk written as recursion, and, beyond the video, the binary search "split" solution, explained step by step for when you're ready.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Before starting: recursion, median, and the merge step
• Part A · Brute force: join, sort, pick the middle
• Part B · Merge walk, counting to the middle (the teacher's solution)
• Part C · The same walk as recursion
• Part D · Going further: split both arrays by binary search (not in the video)
• Part E · Revision page

Part 0 · Before starting

1. Recursion in five ideas

• A function calling itself: it solves a problem by asking itself the same question on a smaller input.
• Base case: the smallest input, answered directly with no further call. It must exist. Without it, the calls never stop, and Python raises RecursionError after about 1000 nested calls.
• Recursive case: the call on a smaller input. Each call must move closer to the base case.
• Leap of faith: when you write the recursive call, trust that it returns the right answer for the smaller input. Only think about how to use that answer.
• Call stack: every call that has started but not finished sits on a stack. A new call is pushed on top and the caller waits. A returning call is popped and hands its answer down. The tallest the stack gets (the depth) is the memory the recursion uses.

Work can happen on the way down (before the smaller call, often carried along in parameters) or on the way back up (after the smaller call returns). Part C does all its work on the way down. Merge sort, below, does its merging on the way back up.

2. What is a median?

Put all the numbers in sorted order. The median is the middle one.

• Odd count: there is exactly one middle element. [1, 2, 3, 4, 5] → median 3 (index 2).
• Even count: there are two middle elements, so take their average. [1, 2, 3, 4] → (2 + 3) / 2 = 2.5.

For a total of total numbers (indexes 0 to total − 1), the middle index is total // 2. When total is even, the other middle one is just before it, at total // 2 − 1.

3. The merge step from merge sort (the prerequisite)

Merge sort is divide and conquer: it splits an array into two halves, sorts each half by recursion, then merges the two sorted halves on the way back up. Look at how it splits the teacher's numbers:

               [4 6 7 1 2 5]
               /           \
        [4 6 7]             [1 2 5]       ← each half sorted (by recursion)
               \           /
             merge two sorted lists
                     ↓
               [1 2 4 5 6 7]

The last step is exactly our problem: two lists that are each sorted, to be combined in order. Merging uses two pointers, i on the first list and j on the second. Each time, compare the two front elements, take the smaller one, and move only that pointer forward. When one list runs out, take the rest of the other.

The teacher also says this merge idea will come back later, for example when merging sorted linked lists. It's worth learning well.

Part A · Brute force: join, sort, pick the middle

LeetCode 4 · Median of Two Sorted Arrays

1The question in simple words

You get two arrays, nums1 (size m) and nums2 (size n). Each one is sorted on its own. Return the median of all m + n numbers together, as a decimal number.

2What the constraints tell us

• 0 ≤ m, n ≤ 1000 and 1 ≤ m + n ≤ 2000: one array may be empty (but never both). Our code must handle an empty list.
• Values from −10⁶ to 10⁶: the sum of two of them fits easily in a normal int.
• Sizes are small (2000 in total), so even sorting is fast. But the problem asks for O(log(m + n)), and the arrays being sorted is a hint that binary search is possible (Part D).

3Intuition

The simplest idea: put both arrays into one list, then find the median of that list.

4Building the logic: why simply joining is not enough

In the first two examples, joining happens to give a sorted list. That's only luck. "Each array is sorted" doesn't mean the last number of nums1 is smaller than the first number of nums2. With nums1 = [4, 6, 7] and nums2 = [1, 2, 5], joining gives [4, 6, 7, 1, 2, 5]: not sorted, and its "middle" (7 and 1) means nothing. A median only makes sense on a sorted list, so we must sort the joined list first: [1, 2, 4, 5, 6, 7] → (4 + 5) / 2 = 4.5 ✓.

5Approach steps

1. merged = sorted(nums1 + nums2).
2. total = len(merged), mid = total // 2.
3. Odd → return merged[mid]. Even → return (merged[mid − 1] + merged[mid]) / 2.

6Code (Python)

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        merged = sorted(nums1 + nums2)   # join, then sort the whole thing
        total = len(merged)
        mid = total // 2
        if total % 2 == 1:               # odd: one middle element
            return float(merged[mid])
        return (merged[mid - 1] + merged[mid]) / 2   # even: average of two

7Code line by line

8Dry run

nums1 = [4, 6, 7], nums2 = [1, 2, 5] → joined [4, 6, 7, 1, 2, 5] → sorted [1, 2, 4, 5, 6, 7]. total = 6 (even), mid = 3 → (merged[2] + merged[3]) / 2 = (4 + 5) / 2 = 4.5 ✓. (No recursion in this part.)

9Complexity & remember

• Time O((m + n) log(m + n)): the sort. It throws away the fact that each array was already sorted.
• Space O(m + n): the merged list.

Part B · Merge walk, counting to the middle (the teacher's solution)

1The question

The same question. Now we want to use the fact that both arrays are sorted, and avoid building a new array.

2What the constraints tell us

One array can be empty, so the pointer on it is "out of range" from the very start. The code must handle a pointer running off the end of its array. That case turns out to be the main detail of this solution.

3Intuition: how the problem is split

The merge from Part 0 hands us numbers in sorted order, one at a time: smallest first, then the next smallest, and so on. The median sits at a known position in that order. So:

• Split the merged order into two parts: the part up to the middle and the part after it.
• We only need the first part. Run the merge walk, count how many numbers we've taken, and stop as soon as we reach the middle. The second half is never touched.
• We don't need to store the numbers either. We only need the last one taken (curr) and, for an even total, the one before it (prev).

4Building the logic from examples

How many numbers must we take?

The teacher counts positions on [1, 2, 4, 5, 6, 7] (total 6, even). The two middles are at indexes 2 and 3, i.e. the 3rd and 4th numbers taken. So we take 4 numbers: the 4th is curr, the 3rd is prev.

So the counting loop runs for count = 0, 1, …, total // 2: that's total // 2 + 1 rounds. The teacher writes it as count <= total / 2 and explains the "equal to" part: for total = 5, 5 / 2 is 2 in integer division, and we need rounds 0, 1 and 2.

Remember the previous number before taking a new one

At the start of every round, copy curr into prev. Then find the new curr. When the loop stops, prev is automatically the number right before the middle one.

Taking the smaller front number

While both pointers are still inside their arrays, compare nums1[i] with nums2[j]. Take the smaller one and move only that pointer. (If they're equal, either is fine. The teacher takes nums1 with <=.)

When one pointer runs off the end

The teacher shows this with examples:

• nums1 = [1, 2], nums2 = [3, 4, 5, 6]: 1 and 2 are taken from nums1. Now i = 2 is past the end of nums1. There's nothing to compare against, so we just keep taking from nums2: 3, then 4. Total 6 → 3rd and 4th → (3 + 4) / 2 = 3.5.
• nums1 = [1, 2, 3, 4], nums2 = [5]: total 5, we want the 3rd number. Comparisons 1 vs 5, 2 vs 5, 3 vs 5 give 1, 2, 3, and we stop at 3. j never even runs out.
• nums1 = [5, 6, 7, 8, 9], nums2 = [4]: 4 is smaller and taken first. Now j is past the end of nums2, so we can't compare 5 or 6 with anything there. We just keep taking from nums1 (i++), counting until we reach the middle: 4, 5, 6, 7 → total 6, so (6 + 7) / 2 = 6.5.

So there are three cases each round: both in range → compare; only i in range → take nums1[i]; otherwise → take nums2[j].

5Approach steps

1. m, n = sizes; total = m + n; i = j = 0; prev = curr = 0.
2. Repeat total // 2 + 1 times: prev = curr, then: both in range → take the smaller of nums1[i], nums2[j] into curr and move that pointer; only i in range → curr = nums1[i], i += 1; else → curr = nums2[j], j += 1.
3. Odd total → return curr. Even total → return (prev + curr) / 2.

6Code (Python)

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        total = m + n
        i = j = 0
        prev = curr = 0
        for count in range(total // 2 + 1):   # count = 0 .. total // 2
            prev = curr                       # keep the old middle candidate
            if i < m and j < n:               # both arrays still have numbers
                if nums1[i] <= nums2[j]:
                    curr = nums1[i]
                    i += 1
                else:
                    curr = nums2[j]
                    j += 1
            elif i < m:                       # nums2 used up
                curr = nums1[i]
                i += 1
            else:                             # nums1 used up
                curr = nums2[j]
                j += 1
        if total % 2 == 1:                    # odd: the middle number
            return float(curr)
        return (prev + curr) / 2              # even: average of the two middles

7Code line by line

8Dry run: nums1 = [4, 6, 7], nums2 = [1, 2, 5]

total = 6 → take 6 // 2 + 1 = 4 numbers.

9Complexity & remember

• Time O(m + n): the loop runs (m + n) / 2 + 1 times. Halving a linear amount is still linear. (If k = m + n, k / 2 is O(k).)
• Space O(1): just a few variables, no merged array.

Part C · The same walk as recursion

This page is in the recursion notebook, so let's write Part B's loop as a recursive function. We use the same conversion rules as for binary search: the loop's changing variables (i, j, how many are left to take, prev, curr) become parameters, the loop's end becomes the base case, and each round becomes one call.

1–2Question & constraints

The same. One new Python concern: the walk takes up to 2000 / 2 + 1 = 1001 numbers, so there can be 1001 nested calls. That's more than Python's default limit of about 1000. We must raise it with sys.setrecursionlimit.

3Intuition: how each call splits the problem

The question each call answers is: "Starting at positions i and j, take left more numbers in sorted order. What are the last two?" Each call splits off one number (the smaller front) and hands the rest, the same question with left − 1, to the next call. This is linear recursion: one call per call, and the input shrinks by 1 each time.

4Building the logic

• Base case: left == 0: we've taken enough. The answer is in the parameters already: return (prev, curr).
• Take from nums1 when nums2 is used up (j == len(nums2)), or when both have numbers and nums1's front is smaller or equal.
• Otherwise take from nums2.
• Taking a number = calling again with that pointer + 1, left − 1, prev = old curr, curr = the number taken.

5Approach steps

1. Call walk(i = 0, j = 0, left = total // 2 + 1, prev = 0, curr = 0).
2. walk: if left == 0 → return (prev, curr).
3. If nums1 should give the next number → return walk(i + 1, j, left − 1, curr, nums1[i]).
4. Else → return walk(i, j + 1, left − 1, curr, nums2[j]).
5. Finally: odd → curr, even → (prev + curr) / 2.

6Code (Python)

import sys
sys.setrecursionlimit(5000)    # up to 1001 nested calls when m + n = 2000

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        total = len(nums1) + len(nums2)
        prev, curr = self.walk(nums1, nums2, 0, 0, total // 2 + 1, 0, 0)
        if total % 2 == 1:
            return float(curr)
        return (prev + curr) / 2

    def walk(self, nums1, nums2, i, j, left, prev, curr):
        if left == 0:                                  # base case: took enough
            return prev, curr
        if j == len(nums2) or (i < len(nums1) and nums1[i] <= nums2[j]):
            return self.walk(nums1, nums2, i + 1, j, left - 1, curr, nums1[i])
        return self.walk(nums1, nums2, i, j + 1, left - 1, curr, nums2[j])

7Code line by line

8Dry run: nums1 = [4, 6, 7], nums2 = [1, 2, 5]

Recursion tree (a single chain). Each node shows walk(i, j, left, prev, curr) and what it returns:

walk(0,0, left=4, prev=0, curr=0) → (4,5)
   |  1 < 4 → take 1 from nums2
walk(0,1, left=3, prev=0, curr=1) → (4,5)
   |  2 < 4 → take 2 from nums2
walk(0,2, left=2, prev=1, curr=2) → (4,5)
   |  4 <= 5 → take 4 from nums1
walk(1,2, left=1, prev=2, curr=4) → (4,5)
   |  5 < 6 → take 5 from nums2
walk(1,3, left=0, prev=4, curr=5) → (4,5)   ← base case

1. Going down: each call compares the two fronts, takes one number, and calls the next with left one smaller. Each call is pushed and waits.
2. The 5th call has left = 0 → returns (4, 5).
3. Coming up: every call passes (4, 5) back unchanged. Nothing is computed on the way up.
4. total = 6 is even → (4 + 5) / 2 = 4.5 ✓.

9Complexity & remember

• Calls: exactly total // 2 + 2 (one per number taken, plus the base case). For 6 numbers that's 5. For 2000 numbers it's 1002.
• Time O(m + n), space O(m + n) for the stack. That's worse than the loop's O(1), which is why the loop is the version to submit.

Part D · Going further: split both arrays by binary search

Not taught in this video. The teacher only mentions that, because the arrays are sorted, binary search gives the most optimized code. Here it is, written as divide and conquer recursion. Learn Parts A–C first.

1The question

The same question, but now in O(log(min(m, n))) time, which is what LeetCode's follow-up asks for.

2What the constraints tell us

m and n up to 1000, so log₂ 1000 ≈ 10 steps. Either array may be empty, so the code must deal with "nothing on this side".

3Intuition: think about the split, not the merge

Picture the merged sorted list cut into a left half and a right half. If the count is odd, the left half gets the extra one:

merged:   1  2  4 | 5  6  7          left half = 3 numbers
                    ↑ the cut

The median comes straight from the numbers next to the cut: the largest on the left (odd count), or that number averaged with the smallest on the right (even count).

Now the key observation. The left half is "the smallest half numbers overall". Since each array is sorted, its smallest numbers are at its front. So the left half is always some front part of nums1 plus some front part of nums2:

nums1:   4        |  6  7        i = 1 number from nums1
nums2:   1  2     |  5           j = 2 numbers from nums2
                                 i + j = 3 = half  ✓

So the whole problem becomes: how many numbers (i) does nums1 put into the left half? Once i is chosen, j = half − i is forced. And i can only be 0, 1, …, m, so we can binary search on i.

4Building the logic: how to tell whether a split is right

Call the four numbers next to the cut:

• a_left = nums1[i − 1] (last of nums1 on the left), a_right = nums1[i] (first of nums1 on the right)
• b_left = nums2[j − 1], b_right = nums2[j]

Inside each array the order is already correct (a_left ≤ a_right, b_left ≤ b_right). The split is right only if everything on the left ≤ everything on the right, and that needs the two cross checks:

half = (m + n + 1) // 2. The "+1" puts the extra number on the left when the total is odd, so then the median is simply max(a_left, b_left).

5Approach steps

1. Make nums1 the shorter array (swap if needed). half = (m + n + 1) // 2.
2. cut(lo, hi): i = (lo + hi) // 2, j = half − i.
3. Read a_left, a_right, b_left, b_right (with ±∞ at the edges).
4. Both checks pass → odd: max(a_left, b_left); even: (max(a_left, b_left) + min(a_right, b_right)) / 2.
5. a_left > b_right → cut(lo, i − 1). Else → cut(i + 1, hi).

6Code (Python)

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        if len(nums1) > len(nums2):            # binary search the shorter one
            nums1, nums2 = nums2, nums1
        half = (len(nums1) + len(nums2) + 1) // 2
        return self.cut(nums1, nums2, 0, len(nums1), half)

    def cut(self, a, b, lo, hi, half):
        i = (lo + hi) // 2                     # how many from a go left
        j = half - i                           # the rest come from b
        a_left = a[i - 1] if i > 0 else float('-inf')
        a_right = a[i] if i < len(a) else float('inf')
        b_left = b[j - 1] if j > 0 else float('-inf')
        b_right = b[j] if j < len(b) else float('inf')
        if a_left <= b_right and b_left <= a_right:      # correct split
            if (len(a) + len(b)) % 2 == 1:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:                   # too many from a
            return self.cut(a, b, lo, i - 1, half)
        return self.cut(a, b, i + 1, hi, half) # too few from a

7Code line by line

8Dry run

nums1 = [1, 3, 8, 9, 15] (m = 5), nums2 = [7, 11, 18, 19, 21, 25] (n = 6). nums1 is already the shorter. total = 11 (odd), half = 6. (Merged: 1 3 7 8 9 11 15 18 19 21 25 → the median is 11.)

cut(lo=0, hi=5)  i=2, j=4                         → 11
   |   left:  nums1 [1 3]        nums2 [7 11 18 19]
   |   a_left=3  a_right=8   b_left=19  b_right=21
   |   b_left 19 > a_right 8  →  too few from nums1, go right
cut(lo=3, hi=5)  i=4, j=2                         → 11
       left:  nums1 [1 3 8 9]    nums2 [7 11]
       a_left=9  a_right=15  b_left=11  b_right=18
       9 <= 18 ✓ and 11 <= 15 ✓  →  correct split
       odd → max(9, 11) = 11   ← base case

1. cut(0, 5): try i = 2 → j = 4. The left side would hold 19, but the right side holds 8. 19 > 8 is wrong, so nums1 must give more. Throw away i = 0…2 and call cut(3, 5).
2. cut(3, 5): try i = 4 → j = 2. Both cross checks pass. The total is odd → return max(9, 11) = 11.
3. cut(0, 5) returns 11 unchanged. Answer 11.0 ✓.

An example with an edge: nums1 = [5, 6, 7, 8, 9], nums2 = [4] → swapped so a = [4], b = [5, 6, 7, 8, 9], half = 3. cut(0, 1): i = 0, j = 3 → a_left = −∞, a_right = 4, b_left = 7 > 4 → go right. cut(1, 1): i = 1, j = 2 → a_left = 4, a_right = +∞, b_left = 6, b_right = 7 → both pass → even → (max(4, 6) + min(+∞, 7)) / 2 = (6 + 7) / 2 = 6.5 ✓ (the same as the teacher's example in Part B).

9Complexity & remember

• Each call halves the range of possible i (0…m), so there are at most about log₂(min(m, n)) + 1 calls: about 11 when m = 1000.
• Time O(log(min(m, n))), space O(log(min(m, n))) for the stack (O(1) if written as a loop).

Part E · Revision page

s = Solution()
print(s.findMedianSortedArrays([1, 3], [2]))           # 2.0
print(s.findMedianSortedArrays([1, 2], [3, 4]))        # 2.5
print(s.findMedianSortedArrays([4, 6, 7], [1, 2, 5]))  # 4.5
print(s.findMedianSortedArrays([1, 2], [3, 4, 5, 6]))  # 3.5
print(s.findMedianSortedArrays([5, 6, 7, 8, 9], [4]))  # 6.5
print(s.findMedianSortedArrays([], [7]))               # 7.0

Based on this video: Median of Two Sorted Arrays | Divide and Conquer (merge approach)