Skip to main content

Weighted Median Partition Threshold

hard
ArrayBinary SearchDivide And ConquerBinary Search On Answer
Asked atGoogleAmazonMetaMicrosoftBloomberg

Problem Description

You are given two sorted arrays `groupA` and `groupB` of integers (not necessarily the same length). Each element has an associated weight of 1. Find the **median** of the combined dataset formed by merging both arrays.

If the combined count of elements is odd, return the single middle value. If even, return the average of the two middle values.

You must solve this in **O(log(min(m, n)))** time, where `m` and `n` are the lengths of `groupA` and `groupB`.

**Example 1:**
```
Input: groupA = [1, 4, 8], groupB = [2, 6, 9, 11]
Output: 6.0
Explanation: Merged sorted array: [1, 2, 4, 6, 8, 9, 11]
Median (7 elements): index 3 → 6.
```

**Example 2:**
```
Input: groupA = [3, 10], groupB = [5, 7]
Output: 6.0
Explanation: Merged sorted array: [3, 5, 7, 10]
Median (even): (5 + 7) / 2 = 6.0.
```

Constraints

  • 0 <= groupA.length <= 1000
  • 0 <= groupB.length <= 1000
  • groupA.length + groupB.length >= 1
  • -10^6 <= groupA[i], groupB[i] <= 10^6
  • groupA and groupB are each sorted in non-decreasing order

Follow-up

Extend this to find the k-th smallest element across the two sorted arrays in O(log(min(m,n))) time.

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.