Using the definitions
implement a function
to return the k-th global element (starting at one) of the elements in the vector of vectors V. Let n = V.size(). For every 0 ≤ i < n, V[i] is sorted increasingly. Furthermore, there are no repeated elements in V.
For exemple, if k = 5, n = 3, and the three vectors are
then the answer is 2, which is the fifth smallest element inside all the vectors.
Let m = ∑0n−1 V[i].size(). Assume that k is between 1 and m, that n is between 2 and 500, and that some V[i] can be empty. If needed, you can implement auxiliar procedures. Take into account that, for the “large” test cases, k = Θ(n) and m = Θ(n2). The expected solution in this cas has cost Θ(n logn).
Observation You only need to submit the required procedure; your main program will be ignored.