Find Median of K Sorted Arrays

▶

Steps

setup

Initialize total length and search range

Calculate the total number of elements across all arrays. Find the global minimum and maximum values to set the initial binary search range.

💡 Knowing the total length and value range is essential to perform binary search on the value domain instead of indices.

Line:

total_len = sum(len(arr) for arr in arrays)
min_val = min((arr[0] for arr in arrays if arr), default=0)
max_val = max((arr[-1] for arr in arrays if arr), default=0)

💡 Establishes the search boundaries for the median value based on input arrays.

setup

Calculate median positions mid1 and mid2

Compute the indices for the median positions based on total length: mid1 for lower median, mid2 for upper median.

💡 These positions determine how many elements we need to count to find the median values.

Line:

mid1 = (total_len - 1) // 2
mid2 = total_len // 2

💡 Defines the target counts for the binary search to find median values.

expand

Start binary search for median1: left=1, right=9

Initialize left and right pointers for the first binary search to find median1.

💡 Binary search will narrow down the value that has at least mid1+1 elements less or equal to it.

Line:

left, right = min_val, max_val

💡 Sets up the binary search boundaries for the first median value.

compare

Binary search iterations for median1 with counts and adjustments

Perform binary search iterations to find median1 by counting elements ≤ mid and adjusting search range accordingly.

💡 Each iteration tests a mid value, counts elements ≤ mid, and narrows the search space based on comparison with mid1.

Line:

while left <= right:
    mid = (left + right) // 2
    c = count_less_equal(mid)
    if c <= mid1:
        left = mid + 1
    else:
        right = mid - 1

💡 Counting elements ≤ mid guides the binary search to converge on median1.

insert

Assign median1 = left = 5

After binary search ends, assign median1 to left, which is 5.

💡 This is the first median candidate found by binary search.

Line:

median1 = left

💡 Median1 is confirmed as 5 based on counting logic.

expand

Reset left and right for median2 binary search

Reset search boundaries to min_val and max_val to find median2.

💡 Median2 is the upper median position for even or odd total length.

Line:

left, right = min_val, max_val

💡 Prepare for second binary search to find median2.

compare

Binary search iterations for median2 with counts and adjustments

Perform binary search iterations to find median2 by counting elements ≤ mid and adjusting search range accordingly.

💡 Each iteration tests a mid value, counts elements ≤ mid, and narrows the search space based on comparison with mid2.

Line:

while left <= right:
    mid = (left + right) // 2
    c = count_less_equal(mid)
    if c <= mid2:
        left = mid + 1
    else:
        right = mid - 1

💡 Counting elements ≤ mid guides the binary search to converge on median2.

insert

Assign median2 = left = 5

After binary search ends, assign median2 to left, which is 5.

💡 This is the second median candidate found by binary search.

Line:

median2 = left

💡 Median2 is confirmed as 5 based on counting logic.

reconstruct

Calculate final median from median1 and median2

Since total length is odd, median is median2 as float. Return 5.0 as the median.

💡 For odd total length, median is the middle element found.

Line:

if total_len % 2 == 1:
    return float(median2)
else:
    return (median1 + median2) / 2

💡 Median value is 5, the middle element of combined sorted arrays.

import bisect

def find_median_k_sorted_arrays(arrays):
    total_len = sum(len(arr) for arr in arrays)  # STEP 1
    if total_len == 0:
        raise ValueError('No elements to find median')
    min_val = min((arr[0] for arr in arrays if arr), default=0)  # STEP 1
    max_val = max((arr[-1] for arr in arrays if arr), default=0)  # STEP 1

    mid1 = (total_len - 1) // 2  # STEP 2
    mid2 = total_len // 2       # STEP 2

    def count_less_equal(x):
        count = 0
        for arr in arrays:
            count += bisect.bisect_right(arr, x)
        return count

    left, right = min_val, max_val  # STEP 3
    while left <= right:             # STEPS 4-11
        mid = (left + right) // 2    # STEP 4,6,8,10
        c = count_less_equal(mid)    # STEP 4,6,8,10
        if c <= mid1:                # STEP 5,7,9,11
            left = mid + 1
        else:
            right = mid - 1
    median1 = left                   # STEP 12

    left, right = min_val, max_val  # STEP 13
    while left <= right:             # STEPS 14-21
        mid = (left + right) // 2    # STEP 14,16,18,20
        c = count_less_equal(mid)    # STEP 14,16,18,20
        if c <= mid2:                # STEP 15,17,19,21
            left = mid + 1
        else:
            right = mid - 1
    median2 = left                   # STEP 22

    if total_len % 2 == 1:          # STEP 23
        return float(median2)
    else:
        return (median1 + median2) / 2

if __name__ == '__main__':
    arrays = [[1,3,5],[2,4,6],[7,8,9]]
    print(find_median_k_sorted_arrays(arrays))  # Output: 5.0

📊

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

Watching the binary search on value range with counting across arrays reveals how the median is found without merging all arrays explicitly.

peekmin-heap

1

0

9

1

peekmin-heap

1

0

9

1

peekmin-heap

1

0

9

1

peekmin-heap

5

0

4

1

2

2

3

3

4

4

5

5

Added: 5

insertmin-heap

5

0

Added: 5

peekmin-heap

1

0

9

1

peekmin-heap

5

0

4

1

2

2

3

3

4

4

5

5

Added: 5

insertmin-heap

5

0

Added: 5

peekmin-heap

5

0

Added: 5

Key Takeaways

✓ Binary searching on the value range instead of merging arrays is efficient and elegant.

Reading code alone hides how the search narrows down the median value by counting elements ≤ mid.

✓ Counting elements ≤ mid across all arrays using binary search is the core operation guiding the search.

Visualizing each count clarifies why the search boundaries move up or down.

✓ The algorithm finds two median candidates (median1 and median2) to handle both even and odd total lengths.

Seeing both searches side by side helps understand how the median is computed precisely.

Practice

1. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution with efficient time complexity?

easy

A. Use a min-heap to track the current minimum element among the heads of each list while maintaining the current maximum, updating the range as you iterate.

B. Apply a greedy approach by always picking the smallest element from any list and expanding the range until all lists are covered.

C. Sort all elements from all lists into one array and use a dynamic programming approach to find the minimal range covering all lists.

D. Use a brute force approach enumerating all combinations of elements from each list and selecting the minimal range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a range that covers at least one element from each of the k sorted lists, minimizing the range size.

2. Step 2: Identify the optimal approach

   Using a min-heap to track the smallest current element from each list and maintaining the maximum element seen so far allows efficient updates of the range while iterating through the lists.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks min and max for optimal range [OK]

Hint: Min-heap tracks min and max for optimal range [OK]

Common Mistakes:

• Thinking brute force is feasible for large k
• Assuming greedy picking smallest element always works
• Confusing DP applicability here

2. Consider the following buggy code for finding the nth ugly number. Which line contains the subtle bug that causes incorrect results or performance issues?

medium

A. Line 3: heap initialization with [1]

B. Line 4: Missing initialization of the 'seen' set

C. Line 7: Loop runs n times popping from heap

D. Line 10: Multiplying ugly by factors 2, 3, and 5

Solution

1. Step 1: Identify missing duplicate check

   The 'seen' set is not initialized and the check to avoid pushing duplicates is missing, causing duplicates to be pushed repeatedly.

2. Step 2: Understand impact of missing 'seen'

   Without 'seen', the heap grows unnecessarily large with duplicates, causing performance degradation and possibly incorrect nth number due to repeated values.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing 'seen' set causes duplicates and performance issues [OK]

Hint: Always track seen elements to avoid duplicates in heap [OK]

Common Mistakes:

• Forgetting to initialize or use 'seen'
• Assuming heap automatically avoids duplicates

3. Suppose jobs can be reused multiple times (i.e., the same job can be assigned repeatedly), and you want to assign jobs to machines minimizing start delays as before. Which modification to the optimal algorithm is necessary to handle this scenario correctly?

hard

A. No change needed; the existing algorithm handles reuse naturally by sorting jobs once and assigning sequentially.

B. Sort jobs by duration instead of start time to prioritize shorter jobs for reuse.

C. Use a brute force approach checking all possible assignments since reuse breaks heap assumptions.

D. Maintain a priority queue of job instances and re-insert jobs after completion to simulate reuse, updating start times accordingly.

Solution

1. Step 1: Understand job reuse impact

   Reusing jobs means after a job finishes, it can be assigned again, so jobs are not fixed once but can appear multiple times.

2. Step 2: Modify algorithm to handle reuse

   Maintain a priority queue of job instances with their next available start times. After a job finishes, re-insert it with updated start time to simulate reuse.

3. Step 3: Why other options fail

   No change ignores reuse; brute force is inefficient; sorting by duration ignores start times and scheduling constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Re-inserting jobs after completion models reuse correctly [OK]

Hint: Re-insert jobs with updated start times to simulate reuse [OK]

Common Mistakes:

• Assuming reuse needs no algorithm change
• Switching sort order breaks scheduling correctness
• Using brute force is inefficient and unnecessary

4. Suppose you want to merge k sorted lists but now each list can contain duplicate values that must be preserved, and you want to return the top M smallest elements overall efficiently. Which modification to the standard divide and conquer approach is best?

hard

A. Continue using divide and conquer merging all lists fully, then slice the first M elements from the merged list.

B. Use dynamic programming to memoize merged prefixes and retrieve top M elements.

C. Concatenate all lists, sort them fully, then return first M elements.

D. Use a min heap to always extract the smallest current node among all lists until M elements are collected.

Solution

1. Step 1: Understand the requirement for top M elements

   We only need the first M smallest elements, not the full merged list.

2. Step 2: Analyze approaches for efficiency

   Divide and conquer merges all lists fully (O(N log k)), which is wasteful if M << N. Concatenation and sort is O(N log N). Min heap approach extracts smallest nodes one by one, stopping after M elements, achieving O(M log k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min heap approach efficiently returns top M elements without full merge [OK]

Hint: Min heap extracts smallest nodes incrementally, ideal for top M [OK]

Common Mistakes:

• Merging all lists fully then slicing wastes time
• Sorting all nodes is inefficient for partial results
• Dynamic programming is not applicable here

5. Suppose the problem is modified so that elements in the lists can be reused multiple times (i.e., you can pick the same element multiple times from the same list). Which modification to the optimal min-heap approach correctly handles this variant?

hard

A. Continue using the min-heap approach but do not advance the index in the list after pushing the next element, allowing reuse of the same element.

B. Use a min-heap but track counts of elements used per list and only advance indices when all elements have been used once.

C. Modify the algorithm to allow pushing the same element multiple times without advancing the index, but update current_max accordingly to avoid infinite loops.

D. The min-heap approach cannot be adapted; instead, use a dynamic programming approach to handle reuse.

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means the same element can be counted multiple times, so indices alone do not track usage.

2. Step 2: Modify tracking mechanism

   Tracking counts of usage per list and advancing indices only after all elements are used once prevents infinite loops and ensures coverage.

3. Step 3: Why other options fail

   Not advancing indices leads to infinite loops; pushing same element multiple times without control breaks correctness; DP is inefficient here.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking usage counts ensures correct reuse handling [OK]

Hint: Track usage counts per list to handle reuse correctly [OK]

Common Mistakes:

• Not advancing indices causing infinite loops
• Pushing duplicates without control
• Switching to DP unnecessarily