Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### DoubleMedian

Given two slices of sorted arrays, find the median. Repeat for many such slices, return the median of the results.

The median of a sequence of numbers X, X, ..., X[N] is the middle element in terms of their values. More formally, the median of X, X, ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:

X = 7 X = 2 X = 5 X = 2 X = 8

is 5; the median of the following sequence:

X = 2 X = 2 X = 5 X = 2

is 2; and the following sequence:

X = 1 X = 5 X = 7 X = 4 X = 2 X = 8

has two medians: 4 and 5.

Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.

Write a function:

class Solution { public int solution(int[] A, int[] B, int[] P, int[] Q, int[] R, int[] S); }

that, given:

• two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
• two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
• two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K

computes medians of K sequences of the form:

A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]

for 0 ≤ I < K, and returns the median of all such medians.

For example, given the following arrays:

A = -2 A = 4 A = 10 A = 13 B = 5 B = 6 B = 8 B = 12 B = 13 P = 2 P = 1 P = 0 Q = 3 Q = 2 Q = 3 R = 0 R = 0 R = 1 S = 4 S = 0 S = 3

the function should return 8, since:

• the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
• the median of [4, 10, 5] equals 5,
• the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
• the median of [10, 5, 8] equals 8.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..100,000];
• K is an integer within the range [1..10,000];
• each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
• array A is sorted in non-decreasing order;
• array B is sorted in non-decreasing order;
• each element of arrays P and Q is an integer within the range [0..N-1];
• each element of arrays R and S is an integer within the range [0..M-1];
• P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
• K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.