Skip to the code
cf.
+50 XP

#165 Median of Two Sorted Feeds

hard

Two monitoring services each return response times as sorted arrays, a and b. The dashboard needs the median of all the times together.

Write medianOfFeeds(a, b) that returns the median of the combined values. If the combined count is odd, it is the middle value. If it is even, it is the average of the two middle values.

Do it in O(log(min(m, n))) time without merging the arrays.

Example 1

Input: a = [1,3,8], b = [2,7]
Output: 3

Together: [1, 2, 3, 7, 8]. The middle value is 3.

Example 2

Input: a = [1,2], b = [3,4]
Output: 2.5

Together: [1, 2, 3, 4]. The two middle values are 2 and 3.

Constraints

  • 0 <= a.length, b.length <= 1000
  • 1 <= a.length + b.length
  • Both arrays are sorted ascending.
  • -10^6 <= a[i], b[i] <= 10^6
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).