Median of Two Sorted Arrays

▶

Steps

setup

Ensure nums1 is smaller array

Check if nums1 is larger than nums2. If so, swap them to minimize binary search range.

💡 Binary search is performed on the smaller array to optimize performance.

Line:

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1

💡 Ensures binary search is done on the smaller array for efficiency.

setup

Initialize binary search boundaries

Set low and high pointers for binary search on nums1 indices from 0 to length of nums1.

💡 Binary search boundaries define the search space for partition index i.

Line:

m, n = len(nums1), len(nums2)
low, high = 0, m
half_len = (m + n + 1) // 2

💡 Initial boundaries cover all possible partition indices in nums1.

compare

Calculate partition indices i and j

Calculate i as midpoint of low and high, and j as half_len - i to partition nums1 and nums2.

💡 Partition indices split arrays into left and right halves for median calculation.

Line:

i = (low + high) // 2
j = half_len - i

💡 Partitions are complementary to cover half the total elements.

compare

Determine max_left and min_right for nums1

Find max_left_nums1 as nums1[i-1] and min_right_nums1 as nums1[i], handling edge cases.

💡 These values define the boundary elements around the partition in nums1.

Line:

max_left_nums1 = nums1[i - 1] if i != 0 else float('-inf')
min_right_nums1 = nums1[i] if i != m else float('inf')

💡 Edge cases use infinities to simplify comparisons.

compare

Determine max_left and min_right for nums2

Find max_left_nums2 as nums2[j-1] and min_right_nums2 as nums2[j], handling edge cases.

💡 These values define the boundary elements around the partition in nums2.

Line:

max_left_nums2 = nums2[j - 1] if j != 0 else float('-inf')
min_right_nums2 = nums2[j] if j != n else float('inf')

💡 Edge cases use infinities to simplify comparisons.

compare

Check if partition is valid

Check if max_left_nums1 ≤ min_right_nums2 and max_left_nums2 ≤ min_right_nums1 to validate partition.

💡 Valid partition means left halves contain smaller elements than right halves.

Line:

if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:

💡 Correct partition found to compute median.

reconstruct

Compute median for odd total length

Since total length is odd, median is max(max_left_nums1, max_left_nums2).

💡 Median is the middle element of merged sorted array.

Line:

if (m + n) % 2 == 1:
    return float(max(max_left_nums1, max_left_nums2))

💡 Median is 2.0, the maximum of left partition elements.

reconstruct

Return median result

Return the computed median value 2.0 as the final answer.

💡 The algorithm terminates with the correct median.

Line:

return 2.0

💡 Median successfully found using binary search partition.

reconstruct

Final state with answer

Final visualization state showing the answer 2.0 and no active pointers.

💡 This final state confirms the median found.

💡 The algorithm completed successfully.

compare

Confirm no further binary search needed

Since partition is valid and median found, no further binary search iterations are needed.

💡 This step clarifies the binary search loop termination condition.

Line:

while low <= high:
    ...
    if partition valid:
        return median
    else adjust low/high

💡 Understanding loop termination is key to grasping algorithm efficiency.

def findMedianSortedArrays(nums1, nums2):  # STEP 1
    if len(nums1) > len(nums2):  # STEP 1
        nums1, nums2 = nums2, nums1  # STEP 1
    m, n = len(nums1), len(nums2)  # STEP 2
    low, high = 0, m  # STEP 2
    half_len = (m + n + 1) // 2  # STEP 2
    while low <= high:  # STEP 3
        i = (low + high) // 2  # STEP 3
        j = half_len - i  # STEP 3
        max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]  # STEP 4
        min_right_nums1 = float('inf') if i == m else nums1[i]  # STEP 4
        max_left_nums2 = float('-inf') if j == 0 else nums2[j - 1]  # STEP 5
        min_right_nums2 = float('inf') if j == n else nums2[j]  # STEP 5
        if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:  # STEP 6
            if (m + n) % 2 == 1:  # STEP 7
                return float(max(max_left_nums1, max_left_nums2))  # STEP 7
            else:  # STEP 7
                return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2.0  # STEP 7
        elif max_left_nums1 > min_right_nums2:  # STEP 6
            high = i - 1  # STEP 6
        else:  # STEP 6
            low = i + 1  # STEP 6

📊

Median of Two Sorted Arrays - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison reveals how the algorithm efficiently finds the median without merging arrays.

setup

1

0

3

1

setup

low

1

0

3

1

compare

low

1

0

i

3

1

compare

1

0

i

3

1

compare

2

0

compare

1

0

j

3

1

record

1

0

j

3

1

Result: 2

record

1

0

3

1

Result: 2

record

1

0

3

1

Result: 2

compare

1

0

3

1

Result: 2

Key Takeaways

✓ Binary search on the smaller array efficiently finds the correct partition for median calculation.

This insight is hard to see from code alone because the partition logic is subtle and involves complementary indices.

✓ Using infinities for edge cases simplifies boundary comparisons without extra conditionals.

Visualizing these sentinel values clarifies how the algorithm handles partitions at array ends.

✓ The median is computed directly from partition boundary elements without merging arrays.

Seeing the partition elements highlighted helps understand how the median relates to these values.

Practice

1. Consider the following Python function that finds the kth positive missing number from a sorted array arr. What is the returned value when calling findKthPositive([2, 4, 7], 3)?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

easy

A. 5

B. 8

C. 9

D. 7

Solution

1. Step 1: Calculate total missing numbers

   Array length n=3, arr[-1]=7, total_missing = 7 - 3 = 4. Since k=3 ≤ 4, proceed with binary search.

2. Step 2: Perform binary search iterations

   Initial left=0, right=2. - mid=1, missing=arr[1] - (1+1) = 4 - 2 = 2 < 3 -> left=2 - mid=2, missing=arr[2] - (2+1) = 7 - 3 = 4 ≥ 3 -> right=1 Loop ends as left=2 > right=1. Return arr[right] + (k - (arr[right] - (right + 1))) = arr[1] + (3 - (4 - 2)) = 4 + (3 - 2) = 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search narrows to index 1, final missing number is 5 [OK]

Hint: Trace missing count at mid carefully [OK]

Common Mistakes:

• Off-by-one in missing calculation
• Returning arr[left] instead of arr[right]
• Miscomputing missing count as arr[mid] - mid

2. You are given a 2D matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. You need to determine if a target value exists in the matrix. Which approach guarantees the most efficient search in this scenario?

easy

A. Perform a binary search on each row individually to find the target.

B. Use a brute force nested loop to check every element until the target is found.

C. Start from the bottom-left corner and move only upwards or rightwards to find the target.

D. Use dynamic programming to build a table of reachable values and check for the target.

Solution

1. Step 1: Understand matrix properties

   Each row and column is sorted ascending, allowing binary search on rows.

2. Step 2: Evaluate approaches

   Brute force is O(m*n), bottom-left approach is staircase search but not binary search, DP is unrelated here. Binary search on each row yields O(m*log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on rows exploits sorted rows efficiently [OK]

Hint: Sorted rows allow binary search per row [OK]

Common Mistakes:

• Confusing staircase search with binary search on rows
• Assuming DP applies here
• Thinking brute force is optimal

3. Consider the following recursive binary search code for finding the insert position of target = 2 in nums = [1, 3, 5, 6]. What is the final returned value?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace binary_search(0, 3)

   mid = (0+3)//2 = 1, nums[1] = 3 > 2, recurse left: binary_search(0, 0)

2. Step 2: Trace binary_search(0, 0)

   mid = (0+0)//2 = 0, nums[0] = 1 < 2, recurse right: binary_search(1, 0)

3. Step 3: Base case binary_search(1, 0)

   left > right, return left = 1 as insertion index

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Target 2 fits between 1 and 3 at index 1 [OK]

Hint: Follow recursive calls and base case carefully [OK]

Common Mistakes:

• Returning right instead of left at base case
• Off-by-one in mid calculation
• Confusing left and right updates

4. Suppose you want to find the first occurrence of a target value in a sorted array that may contain duplicates. Which modification to the classic binary search algorithm correctly achieves this?

hard

A. Return the first index where nums[mid] == target and check if previous element is different or mid == 0

B. Return any index where nums[mid] == target without further checks

C. Use linear search after binary search to find first occurrence

D. Modify binary search to always move low to mid + 1 when nums[mid] == target

Solution

1. Step 1: Understand problem with duplicates

   Classic binary search returns any matching index, not necessarily first occurrence.

2. Step 2: Modify binary search to check if mid is first occurrence

   When nums[mid] == target, check if mid == 0 or nums[mid-1] != target; if not, continue searching left half.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ensures first occurrence by verifying previous element [OK]

Hint: Check previous element to find first occurrence [OK]

Common Mistakes:

• Returning any occurrence
• Linear search after binary search wastes time
• Moving low forward on match loses first occurrence

5. Suppose the rotated sorted array may contain duplicates, which can cause nums[mid] == nums[right]. The original binary search breaks in this case. Which modification correctly handles duplicates while maintaining O(log n) average time?

hard

A. When nums[mid] == nums[right], reduce right by one (right -= 1) and continue

B. When nums[mid] == nums[right], move left to mid + 1

C. When nums[mid] == nums[right], return nums[left] immediately

D. When nums[mid] == nums[right], perform linear scan from left to right

Solution

1. Step 1: Understand problem with duplicates

   Duplicates cause ambiguity when nums[mid] == nums[right], so we cannot decide which side to discard.

2. Step 2: Correct approach reduces right by one

   Reducing right by one shrinks the search space safely without missing the minimum, maintaining average O(log n) time.

3. Step 3: Other options either skip elements or degrade to linear scan

   Moving left or returning early risks missing the minimum; linear scan is correct but O(n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Reducing right by one handles duplicates safely [OK]

Hint: Shrink right pointer when duplicates cause ambiguity [OK]

Common Mistakes:

• Moving left pointer loses minimum
• Returning early misses cases
• Linear scan loses O(log n) advantage