Login/Register
How to find the kth smallest element in the union of two sorted arrays?
Asked Answered
Solved arraysalgorithmbinary-searchdivide-and-conquer
V

17

116

This is a homework question, binary search has already been introduced:

Given two arrays, respectively N and M elements in ascending order, not necessarily unique:
What is a time efficient algorithm to find the kth smallest element in the union of both arrays?

They say it takes O(logN + logM) where N and M are the arrays lengths.

Let's name the arrays a and b. Obviously we can ignore all a[i] and b[i] where i > k.
First let's compare a[k/2] and b[k/2]. Let b[k/2] > a[k/2]. Therefore we can discard also all b[i], where i > k/2.

Now we have all a[i], where i < k and all b[i], where i < k/2 to find the answer.

What is the next step?

Viewable answered 5/1, 2011 at 18:43 Comment(6)
Is O(logN + logM) only referring to the time it takes to find the kth element? Can preprocessing be done to the union beforehand? – Rotl
@David. No preprocessing is expected. – Viewable
Are duplicates allowed in the arrays? – Rotl
possible duplicate of nth smallest number among two databases of size n each using divide and conquer – Chester
@David Yes, duplicates are allowed. – Viewable
Ok what if N and/or M is less than k/2? – Lionize
R
55

You've got it, just keep going! And be careful with the indexes...

To simplify a bit I'll assume that N and M are > k, so the complexity here is O(log k), which is O(log N + log M).

Pseudo-code:

i = k/2
j = k - i
step = k/4
while step > 0
    if a[i-1] > b[j-1]
        i -= step
        j += step
    else
        i += step
        j -= step
    step /= 2

if a[i-1] > b[j-1]
    return a[i-1]
else
    return b[j-1]

For the demonstration you can use the loop invariant i + j = k, but I won't do all your homework :)

Reprehension answered 5/1, 2011 at 19:21 Comment(13)
When initializing j, did you mean j = k-i ? – Rotl
Do you have a correctness proof for this? I want to believe that this works but honestly I don't see why this should give you the right answer. Can you provide a more detailed explanation or a link to a proof? – Axial
This is not a real proof, but the idea behind the algorithm is that we maintain i + j = k, and find such i and j so that a[i-1] < b[j-1] < a[i] (or the other way round). Now since there are i elements in 'a' smaller than b[j-1], and j-1 elements in 'b' smaller than b[j-1], b[j-1] is the i + j-1 + 1 = kth smallest element. To find such i,j the algorithm does a dichotomic search on the arrays. Makes sense? – Lamblike
How come O(log k) is O(log n + log m) ? – Masonry
Is this the same as follows: Trim the size of A and B to k elements each, then find the median of A[1..k] and B[1..k] ? Thus, kth smallest element in A and B will be the median of A[1..k] and B[1..k]. – Cloudland
This doesn't work if all of the values in array 1 come before the values in array 2. – Barbour
Why did you use k/4 as a step at first? – Lepido
This is plain wrong. If you use the arrays {3, 12, 13, 14, 21, 29, 35, 36, 38, 40, 41} and {-5, -3, 1, 5, 7, 9, 10, 11, 13, 14, 19} then the algorithm returns 7 as the result of the 5th smallest element, while the correct answer is 5. Also the algorithm returns 14 as the 10th smallest element while the correct answer is 12. If you ask for the 14th smallest element then it just simply throws out of bound exception. – Embitter
If anybody interested in the correct answer, look at @Fei's explanation below. – Embitter
@CaptainFogetti there must be something wrong in your implementation, I get the correct results with exactly the algo above as you can see here (Python) – Lamblike
@Jules Yup, that's right. Sorry about that. I was writing j = k - 1 instead of j = k - i. My bad. – Embitter
As @JohnKurlak mentioned it doesn't work for values where whole a is smaller than b see repl.it/HMYf/0 – Chook
The correct complexity is log(k) = log (m+n). log (m+n) is not equal to log(m) + log (n) – Emoryemote
V
87

I hope I am not answering your homework, as it has been over a year since this question was asked. Here is a tail recursive solution that will take log(len(a)+len(b)) time.

Assumption: The inputs are correct, i.e., k is in the range [0, len(a)+len(b)].

Base cases:

  • If length of one of the arrays is 0, the answer is kth element of the second array.

Reduction steps:

  • If mid index of a + mid index of b is less than k:
    • If mid element of a is greater than mid element of b, we can ignore the first half of b, adjust k.
    • Otherwise, ignore the first half of a, adjust k.
  • If k is less than sum of mid indices of a and b:
    • If mid element of a is greater than mid element of b, we can safely ignore second half of a.
    • Otherwise, we can ignore second half of b.

Code:

def kthlargest(arr1, arr2, k):
    if len(arr1) == 0:
        return arr2[k]
    elif len(arr2) == 0:
        return arr1[k]

    mida1 = len(arr1) // 2  # integer division
    mida2 = len(arr2) // 2
    if mida1 + mida2 < k:
        if arr1[mida1] > arr2[mida2]:
            return kthlargest(arr1, arr2[mida2+1:], k - mida2 - 1)
        else:
            return kthlargest(arr1[mida1+1:], arr2, k - mida1 - 1)
    else:
        if arr1[mida1] > arr2[mida2]:
            return kthlargest(arr1[:mida1], arr2, k)
        else:
            return kthlargest(arr1, arr2[:mida2], k)

Please note that my solution is creating new copies of smaller arrays in every call, this can be easily eliminated by only passing start and end indices on the original arrays.

Vaulting answered 20/1, 2012 at 0:2 Comment(12)
why do you call it kthlargest() it returns (k+1)-th smallest elements e.g., 1 is the second smallest element in 0,1,2,3 i.e., your function returns sorted(a+b)[k]. – Freberg
I've converted your code to C++. It seems to work – Freberg
Won't it be kth smallest instead of kth largest? – Spinach
could you please explain why is it important to compare sum of mid indexes of a and b with k? – Lepido
In the reduction steps, it is important to get rid of a number of elements in one of the arrays proportional to its length in order to make the run-time logarithmic. (Here we are getting rid of half). In order to do that, we need to select one array whose one of the halves we can safely ignore. How do we do that? By confidently eliminating the half we know for sure is not going to have the kth element. – Vaulting
Comparing k with the sum of half-lengths of the arrays gives us information about which half of one of the arrays can be eliminated. If k is larger than sum of half-lengths, we know that first half of one of the arrays can be eliminated. Opposite if k is smaller. Note that we can't eliminate one half from each array at once. For deciding which half of which array to eliminate, we take advantage of the fact that both arrays are sorted, so if k is larger than sum of half-lengths, we can eliminate first half of the array whose middle element is the smaller of the two middle elements. Vice versa. – Vaulting
This won't work for a = (0,2,9,10,12,13,14,16) and b = (8) and k = 4 – Synsepalous
@JacksonTale, it works for me. I get 10 as the answer, which is expected with 0 based indexing. – Vaulting
@Vaulting could you please explain how the run time is log(len(a)+len(b)) ? – Castleberry
@PrashantBhanarkar It looks like it should be log(len(a))+log(len(B)), not log(len(a)+len(b) as lambdapilgrim describes. The algorithm cuts A or B in half each iteration, until A or B is of length 0. So, in the worst cast, the algorithm will cut A to length 1 (log(len(a)) recursions) and B to length 0 (log(len(B)) recursions). This would be log(len(a))+log(len(B)). – Humph
@AdityaJoshee it returns 40 which is correct if you take indexes starting from 0. And this function actually returns the kth smallest element – Peipeiffer
In the python code why is it "arr2[mida2+1:]" rather than just "arr2[mida2:]". That seems to remove 1 extra element from the half we're trying to keep – Alyssaalyssum
R
55

You've got it, just keep going! And be careful with the indexes...

To simplify a bit I'll assume that N and M are > k, so the complexity here is O(log k), which is O(log N + log M).

Pseudo-code:

i = k/2
j = k - i
step = k/4
while step > 0
    if a[i-1] > b[j-1]
        i -= step
        j += step
    else
        i += step
        j -= step
    step /= 2

if a[i-1] > b[j-1]
    return a[i-1]
else
    return b[j-1]

For the demonstration you can use the loop invariant i + j = k, but I won't do all your homework :)

Reprehension answered 5/1, 2011 at 19:21 Comment(13)
When initializing j, did you mean j = k-i ? – Rotl
Do you have a correctness proof for this? I want to believe that this works but honestly I don't see why this should give you the right answer. Can you provide a more detailed explanation or a link to a proof? – Axial
This is not a real proof, but the idea behind the algorithm is that we maintain i + j = k, and find such i and j so that a[i-1] < b[j-1] < a[i] (or the other way round). Now since there are i elements in 'a' smaller than b[j-1], and j-1 elements in 'b' smaller than b[j-1], b[j-1] is the i + j-1 + 1 = kth smallest element. To find such i,j the algorithm does a dichotomic search on the arrays. Makes sense? – Lamblike
How come O(log k) is O(log n + log m) ? – Masonry
Is this the same as follows: Trim the size of A and B to k elements each, then find the median of A[1..k] and B[1..k] ? Thus, kth smallest element in A and B will be the median of A[1..k] and B[1..k]. – Cloudland
This doesn't work if all of the values in array 1 come before the values in array 2. – Barbour
Why did you use k/4 as a step at first? – Lepido
This is plain wrong. If you use the arrays {3, 12, 13, 14, 21, 29, 35, 36, 38, 40, 41} and {-5, -3, 1, 5, 7, 9, 10, 11, 13, 14, 19} then the algorithm returns 7 as the result of the 5th smallest element, while the correct answer is 5. Also the algorithm returns 14 as the 10th smallest element while the correct answer is 12. If you ask for the 14th smallest element then it just simply throws out of bound exception. – Embitter
If anybody interested in the correct answer, look at @Fei's explanation below. – Embitter
@CaptainFogetti there must be something wrong in your implementation, I get the correct results with exactly the algo above as you can see here (Python) – Lamblike
@Jules Yup, that's right. Sorry about that. I was writing j = k - 1 instead of j = k - i. My bad. – Embitter
As @JohnKurlak mentioned it doesn't work for values where whole a is smaller than b see repl.it/HMYf/0 – Chook
The correct complexity is log(k) = log (m+n). log (m+n) is not equal to log(m) + log (n) – Emoryemote
D
40

Many people answered this "kth smallest element from two sorted array" question, but usually with only general ideas, not a clear working code or boundary conditions analysis.

Here I'd like to elaborate it carefully with the way I went though to help some novices to understand, with my correct working Java code. A1 and A2 are two sorted ascending arrays, with size1 and size2 as length respectively. We need to find the k-th smallest element from the union of those two arrays. Here we reasonably assume that (k > 0 && k <= size1 + size2), which implies that A1 and A2 can't be both empty.

First, let's approach this question with a slow O(k) algorithm. The method is to compare the first element of both array, A1[0] and A2[0]. Take the smaller one, say A1[0] away into our pocket. Then compare A1[1] with A2[0], and so on. Repeat this action until our pocket reached k elements. Very important: In the first step, we can only commit to A1[0] in our pocket. We can NOT include or exclude A2[0]!!!

The following O(k) code gives you one element before the correct answer. Here I use it to show my idea, and analysis boundary condition. I have correct code after this one:

private E kthSmallestSlowWithFault(int k) {
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0;
    // base case, k == 1
    if (k == 1) {
        if (size1 == 0) {
            return A2[index2];
        } else if (size2 == 0) {
            return A1[index1];
        } else if (A1[index1].compareTo(A2[index2]) < 0) {
            return A1[index1];
        } else {
            return A2[index2];
        }
    }

    /* in the next loop, we always assume there is one next element to compare with, so we can
     * commit to the smaller one. What if the last element is the kth one?
     */
    if (k == size1 + size2) {
        if (size1 == 0) {
            return A2[size2 - 1];
        } else if (size2 == 0) {
            return A1[size1 - 1];
        } else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) {
            return A1[size1 - 1];
        } else {
            return A2[size2 - 1];
        }
    }

    /*
     * only when k > 1, below loop will execute. In each loop, we commit to one element, till we
     * reach (index1 + index2 == k - 1) case. But the answer is not correct, always one element
     * ahead, because we didn't merge base case function into this loop yet.
     */
    int lastElementFromArray = 0;
    while (index1 + index2 < k - 1) {
        if (A1[index1].compareTo(A2[index2]) < 0) {
            index1++;
            lastElementFromArray = 1;
            // commit to one element from array A1, but that element is at (index1 - 1)!!!
        } else {
            index2++;
            lastElementFromArray = 2;
        }
    }
    if (lastElementFromArray == 1) {
        return A1[index1 - 1];
    } else {
        return A2[index2 - 1];
    }
}

The most powerful idea is that in each loop, we always use the base case approach. After committed to the current smallest element, we get one step closer to the target: the k-th smallest element. Never jump into the middle and make yourself confused and lost!

By observing the above code base case k == 1, k == size1+size2, and combine with that A1 and A2 can't both be empty. We can turn the logic into below more concise style.

Here is a slow but correct working code:

private E kthSmallestSlow(int k) {
    // System.out.println("this is an O(k) speed algorithm, very concise");
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0;
    while (index1 + index2 < k - 1) {
        if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
            index1++; // here we commit to original index1 element, not the increment one!!!
        } else {
            index2++;
        }
    }
    // below is the (index1 + index2 == k - 1) base case
    // also eliminate the risk of referring to an element outside of index boundary
    if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
        return A1[index1];
    } else {
        return A2[index2];
    }
}

Now we can try a faster algorithm runs at O(log k). Similarly, compare A1[k/2] with A2[k/2]; if A1[k/2] is smaller, then all the elements from A1[0] to A1[k/2] should be in our pocket. The idea is to not just commit to one element in each loop; the first step contains k/2 elements. Again, we can NOT include or exclude A2[0] to A2[k/2] anyway. So in the first step, we can't go more than k/2 elements. For the second step, we can't go more than k/4 elements...

After each step, we get much closer to k-th element. At the same time each step get smaller and smaller, until we reach (step == 1), which is (k-1 == index1+index2). Then we can refer to the simple and powerful base case again.

Here is the working correct code:

private E kthSmallestFast(int k) {
    // System.out.println("this is an O(log k) speed algorithm with meaningful variables name");
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0, step = 0;
    while (index1 + index2 < k - 1) {
        step = (k - index1 - index2) / 2;
        int step1 = index1 + step;
        int step2 = index2 + step;
        if (size1 > step1 - 1
                && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) {
            index1 = step1; // commit to element at index = step1 - 1
        } else {
            index2 = step2;
        }
    }
    // the base case of (index1 + index2 == k - 1)
    if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
        return A1[index1];
    } else {
        return A2[index2];
    }
}

Some people may worry what if (index1+index2) jump over k-1? Could we miss the base case (k-1 == index1+index2)? That's impossible. You can add up 0.5+0.25+0.125..., and you will never go beyond 1.

Of course, it is very easy to turn the above code into recursive algorithm:

private E kthSmallestFastRecur(int k, int index1, int index2, int size1, int size2) {
    // System.out.println("this is an O(log k) speed algorithm with meaningful variables name");

    // the base case of (index1 + index2 == k - 1)
    if (index1 + index2 == k - 1) {
        if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
            return A1[index1];
        } else {
            return A2[index2];
        }
    }

    int step = (k - index1 - index2) / 2;
    int step1 = index1 + step;
    int step2 = index2 + step;
    if (size1 > step1 - 1 && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) {
        index1 = step1;
    } else {
        index2 = step2;
    }
    return kthSmallestFastRecur(k, index1, index2, size1, size2);
}

Hope the above analysis and Java code could help you to understand. But never copy my code as your homework! Cheers ;)

Daystar answered 30/3, 2015 at 17:34 Comment(9)
Thank you so much for your great explanations and answer, +1 :) – Overcome
In first code, shouldn't be else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) instead of else if (A1[size1 - 1].compareTo(A2[size2 - 1]) > 0) ? (In kthSmallestSlowWithFault code) – Overcome
Thank you @Fei. Great explanation. It's astonishing how many wrong answers are circulating over the internet regarding this problem. It's even more astonishing that the accepted answer her on SO regarding this question is always the wrong one. Seems like nobody cares to test the answers. – Embitter
Maybe cutoff to the O(k) solution after some steps (said 15), as steps range decrease pretty fast. – Proud
@Daystar what is the reason for "size2 <= step2 - 1" in the if block in O(log k) algorithm ? – Jemmy
@SyncMaster: Because what we had compared is the element at A2[step2 - 1]. – Daystar
In none of the recursive calls the sizes of A1 or A2 are reduced. – Hershey
I don't understand the necessity for step -1 – Bingen
people answered this "kth smallest element from two sorted array" question - the explicit question after presentation of the first steps of an approach being What is the next step? – Pralltriller
F
5

Here's a C++ iterative version of @lambdapilgrim's solution (see the explanation of the algorithm there):

#include <cassert>
#include <iterator>

template<class RandomAccessIterator, class Compare>
typename std::iterator_traits<RandomAccessIterator>::value_type
nsmallest_iter(RandomAccessIterator firsta, RandomAccessIterator lasta,
               RandomAccessIterator firstb, RandomAccessIterator lastb,
               size_t n,
               Compare less) {
  assert(issorted(firsta, lasta, less) && issorted(firstb, lastb, less));
  for ( ; ; ) {
    assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb)));
    if (firsta == lasta) return *(firstb + n);
    if (firstb == lastb) return *(firsta + n);

    size_t mida = (lasta - firsta) / 2;
    size_t midb = (lastb - firstb) / 2;
    if ((mida + midb) < n) {
      if (less(*(firstb + midb), *(firsta + mida))) {
        firstb += (midb + 1);
        n -= (midb + 1);
      }
      else {
        firsta += (mida + 1);
        n -= (mida + 1);
      }
    }
    else {
      if (less(*(firstb + midb), *(firsta + mida)))
        lasta = (firsta + mida);
      else
        lastb = (firstb + midb);
    }
  }
}

It works for all 0 <= n < (size(a) + size(b)) indexes and has O(log(size(a)) + log(size(b))) complexity.

Example

#include <functional> // greater<>
#include <iostream>

#define SIZE(a) (sizeof(a) / sizeof(*a))

int main() {
  int a[] = {5,4,3};
  int b[] = {2,1,0};
  int k = 1; // find minimum value, the 1st smallest value in a,b

  int i = k - 1; // convert to zero-based indexing
  int v = nsmallest_iter(a, a + SIZE(a), b, b + SIZE(b),
                         SIZE(a)+SIZE(b)-1-i, std::greater<int>());
  std::cout << v << std::endl; // -> 0
  return v;
}
Freberg answered 28/7, 2012 at 5:51 Comment(0)
S
4

My attempt for first k numbers, kth number in 2 sorted arrays, and in n sorted arrays:

// require() is recognizable by node.js but not by browser;
// for running/debugging in browser, put utils.js and this file in <script> elements,
if (typeof require === "function") require("./utils.js");

// Find K largest numbers in two sorted arrays.
function k_largest(a, b, c, k) {
    var sa = a.length;
    var sb = b.length;
    if (sa + sb < k) return -1;
    var i = 0;
    var j = sa - 1;
    var m = sb - 1;
    while (i < k && j >= 0 && m >= 0) {
        if (a[j] > b[m]) {
            c[i] = a[j];
            i++;
            j--;
        } else {
            c[i] = b[m];
            i++;
            m--;
        }
    }
    debug.log(2, "i: "+ i + ", j: " + j + ", m: " + m);
    if (i === k) {
        return 0;
    } else if (j < 0) {
        while (i < k) {
            c[i++] = b[m--];
        }
    } else {
        while (i < k) c[i++] = a[j--];
    }
    return 0;
}

// find k-th largest or smallest number in 2 sorted arrays.
function kth(a, b, kd, dir){
    sa = a.length; sb = b.length;
    if (kd<1 || sa+sb < kd){
        throw "Mission Impossible! I quit!";
    }

    var k;
    //finding the kd_th largest == finding the smallest k_th;
    if (dir === 1){ k = kd;
    } else if (dir === -1){ k = sa + sb - kd + 1;}
    else throw "Direction has to be 1 (smallest) or -1 (largest).";

    return find_kth(a, b, k, sa-1, 0, sb-1, 0);
}

// find k-th smallest number in 2 sorted arrays;
function find_kth(c, d, k, cmax, cmin, dmax, dmin){

    sc = cmax-cmin+1; sd = dmax-dmin+1; k0 = k; cmin0 = cmin; dmin0 = dmin;
    debug.log(2, "=k: " + k +", sc: " + sc + ", cmax: " + cmax +", cmin: " + cmin + ", sd: " + sd +", dmax: " + dmax + ", dmin: " + dmin);

    c_comp = k0-sc;
    if (c_comp <= 0){
        cmax = cmin0 + k0-1;
    } else {
        dmin = dmin0 + c_comp-1;
        k -= c_comp-1;
    }

    d_comp = k0-sd;
    if (d_comp <= 0){
        dmax = dmin0 + k0-1;
    } else {
        cmin = cmin0 + d_comp-1;
        k -= d_comp-1;
    }
    sc = cmax-cmin+1; sd = dmax-dmin+1;

    debug.log(2, "#k: " + k +", sc: " + sc + ", cmax: " + cmax +", cmin: " + cmin + ", sd: " + sd +", dmax: " + dmax + ", dmin: " + dmin + ", c_comp: " + c_comp + ", d_comp: " + d_comp);

    if (k===1) return (c[cmin]<d[dmin] ? c[cmin] : d[dmin]);
    if (k === sc+sd) return (c[cmax]>d[dmax] ? c[cmax] : d[dmax]);

    m = Math.floor((cmax+cmin)/2);
    n = Math.floor((dmax+dmin)/2);

    debug.log(2, "m: " + m + ", n: "+n+", c[m]: "+c[m]+", d[n]: "+d[n]);

    if (c[m]<d[n]){
        if (m === cmax){ // only 1 element in c;
            return d[dmin+k-1];
        }

        k_next = k-(m-cmin+1);
        return find_kth(c, d, k_next, cmax, m+1, dmax, dmin);
    } else {
        if (n === dmax){
            return c[cmin+k-1];
        }

        k_next = k-(n-dmin+1);
        return find_kth(c, d, k_next, cmax, cmin, dmax, n+1);
    }
}

function traverse_at(a, ae, h, l, k, at, worker, wp){
    var n = ae ? ae.length : 0;
    var get_node;
    switch (at){
        case "k": get_node = function(idx){
                var node = {};
                var pos = l[idx] + Math.floor(k/n) - 1;
                if (pos<l[idx]){ node.pos = l[idx]; }
                else if (pos > h[idx]){ node.pos = h[idx];}
                else{ node.pos = pos; }

                node.idx = idx;
                node.val = a[idx][node.pos];
                debug.log(6, "pos: "+pos+"\nnode =");
                debug.log(6, node);
                return node;
            };
            break;
        case "l": get_node = function(idx){
                debug.log(6, "a["+idx+"][l["+idx+"]]: "+a[idx][l[idx]]);
                return a[idx][l[idx]];
            };
            break;
        case "h": get_node = function(idx){
                debug.log(6, "a["+idx+"][h["+idx+"]]: "+a[idx][h[idx]]);
                return a[idx][h[idx]];
            };
            break;
        case "s": get_node = function(idx){
                debug.log(6, "h["+idx+"]-l["+idx+"]+1: "+(h[idx] - l[idx] + 1));
                return h[idx] - l[idx] + 1;
            };
            break;
        default: get_node = function(){
                debug.log(1, "!!! Exception: get_node() returns null.");
                return null;
            };
            break;
    }

    worker.init();

    debug.log(6, "--* traverse_at() *--");

    var i;
    if (!wp){
        for (i=0; i<n; i++){
            worker.work(get_node(ae[i]));
        }    
    } else {
        for (i=0; i<n; i++){
            worker.work(get_node(ae[i]), wp);
        }
    }

    return worker.getResult();
}

sumKeeper = function(){
    var res = 0;
    return {
        init     : function(){ res = 0;},
        getResult: function(){
                debug.log(5, "@@ sumKeeper.getResult: returning: "+res);
                return res;
            },
        work     : function(node){ if (node!==null) res += node;}
    };
}();

maxPicker = function(){
    var res = null;
    return {
        init     : function(){ res = null;},
        getResult: function(){
                debug.log(5, "@@ maxPicker.getResult: returning: "+res);
                return res;
            },
        work     : function(node){
            if (res === null){ res = node;}
            else if (node!==null && node > res){ res = node;}
        }
    };    
}();

minPicker = function(){
    var res = null;
    return {
        init     : function(){ res = null;},
        getResult: function(){
                debug.log(5, "@@ minPicker.getResult: returning: ");
                debug.log(5, res);
                return res;
            },
        work     : function(node){
            if (res === null && node !== null){ res = node;}
            else if (node!==null &&
                node.val !==undefined &&
                node.val < res.val){ res = node; }
            else if (node!==null && node < res){ res = node;}
        }
    };  
}();

// find k-th smallest number in n sorted arrays;
// need to consider the case where some of the subarrays are taken out of the selection;
function kth_n(a, ae, k, h, l){
    var n = ae.length;
    debug.log(2, "------**  kth_n()  **-------");
    debug.log(2, "n: " +n+", k: " + k);
    debug.log(2, "ae: ["+ae+"],  len: "+ae.length);
    debug.log(2, "h: [" + h + "]");
    debug.log(2, "l: [" + l + "]");

    for (var i=0; i<n; i++){
        if (h[ae[i]]-l[ae[i]]+1>k) h[ae[i]]=l[ae[i]]+k-1;
    }
    debug.log(3, "--after reduction --");
    debug.log(3, "h: [" + h + "]");
    debug.log(3, "l: [" + l + "]");

    if (n === 1)
        return a[ae[0]][k-1]; 
    if (k === 1)
        return traverse_at(a, ae, h, l, k, "l", minPicker);
    if (k === traverse_at(a, ae, h, l, k, "s", sumKeeper))
        return traverse_at(a, ae, h, l, k, "h", maxPicker);

    var kn = traverse_at(a, ae, h, l, k, "k", minPicker);
    debug.log(3, "kn: ");
    debug.log(3, kn);

    var idx = kn.idx;
    debug.log(3, "last: k: "+k+", l["+kn.idx+"]: "+l[idx]);
    k -= kn.pos - l[idx] + 1;
    l[idx] = kn.pos + 1;
    debug.log(3, "next: "+"k: "+k+", l["+kn.idx+"]: "+l[idx]);
    if (h[idx]<l[idx]){ // all elements in a[idx] selected;
        //remove a[idx] from the arrays.
        debug.log(4, "All elements selected in a["+idx+"].");
        debug.log(5, "last ae: ["+ae+"]");
        ae.splice(ae.indexOf(idx), 1);
        h[idx] = l[idx] = "_"; // For display purpose only.
        debug.log(5, "next ae: ["+ae+"]");
    }

    return kth_n(a, ae, k, h, l);
}

function find_kth_in_arrays(a, k){

    if (!a || a.length<1 || k<1) throw "Mission Impossible!";

    var ae=[], h=[], l=[], n=0, s, ts=0;
    for (var i=0; i<a.length; i++){
        s = a[i] && a[i].length;
        if (s>0){
            ae.push(i); h.push(s-1); l.push(0);
            ts+=s;
        }
    }

    if (k>ts) throw "Too few elements to choose from!";

    return kth_n(a, ae, k, h, l);
}

/////////////////////////////////////////////////////
// tests
// To show everything: use 6.
debug.setLevel(1);

var a = [2, 3, 5, 7, 89, 223, 225, 667];
var b = [323, 555, 655, 673];
//var b = [99];
var c = [];

debug.log(1, "a = (len: " + a.length + ")");
debug.log(1, a);
debug.log(1, "b = (len: " + b.length + ")");
debug.log(1, b);

for (var k=1; k<a.length+b.length+1; k++){
    debug.log(1, "================== k: " + k + "=====================");

    if (k_largest(a, b, c, k) === 0 ){
      debug.log(1, "c = (len: "+c.length+")");
      debug.log(1, c);
    }

    try{
        result = kth(a, b, k, -1);
        debug.log(1, "===== The " + k + "-th largest number: " + result);
    } catch (e) {
        debug.log(0, "Error message from kth(): " + e);
    }
    debug.log("==================================================");
}

debug.log(1, "################# Now for the n sorted arrays ######################");
debug.log(1, "####################################################################");

x = [[1, 3, 5, 7, 9],
     [-2, 4, 6, 8, 10, 12],
     [8, 20, 33, 212, 310, 311, 623],
     [8],
     [0, 100, 700],
     [300],
     [],
     null];

debug.log(1, "x = (len: "+x.length+")");
debug.log(1, x);

for (var i=0, num=0; i<x.length; i++){
    if (x[i]!== null) num += x[i].length;
}
debug.log(1, "totoal number of elements: "+num);

// to test k in specific ranges:
var start = 0, end = 25;
for (k=start; k<end; k++){
    debug.log(1, "=========================== k: " + k + "===========================");

    try{
        result = find_kth_in_arrays(x, k);
        debug.log(1, "====== The " + k + "-th smallest number: " + result);
    } catch (e) {
        debug.log(1, "Error message from find_kth_in_arrays: " + e);
    }
    debug.log(1, "=================================================================");
}
debug.log(1, "x = (len: "+x.length+")");
debug.log(1, x);
debug.log(1, "totoal number of elements: "+num);

The complete code with debug utils can be found at: https://github.com/brainclone/teasers/tree/master/kth

Schlesinger answered 25/9, 2012 at 0:52 Comment(1)
Funny approach when the question asks for the next step in find the kth smallest. (Then again, had values been unique, you could use k2 = N+M-k.) – Pralltriller
M
3

Most of the answers I found here focus on both arrays. while it's good but it's harder to implement as there are a lot of edge cases that we need to take care of. Besides that most of the implementations are recursive which adds the space complexity of recursion stack. So instead of focusing on both arrays I decided to just focus on the smaller array and do the binary search on just the smaller array and adjust the pointer for the second array based on the value of the pointer in the first Array. By the following implementation, we have the complexity of O(log(min(n,m)) with O(1) space complexity. 

    public static int kth_two_sorted(int []a, int b[],int k){
    if(a.length > b.length){
        return kth_two_sorted(b,a,k);
    }
    if(a.length + a.length < k){
        throw new RuntimeException("wrong argument");
    }
    int low = 0;
    int high = k;
    if(a.length <= k){
        high = a.length-1;
    }
    while(low <= high){
        int sizeA = low+(high - low)/2;
        int sizeB = k - sizeA;
        boolean shrinkLeft = false;
        boolean extendRight = false;
        if(sizeA != 0){
            if(sizeB !=b.length){
                if(a[sizeA-1] > b[sizeB]){
                    shrinkLeft = true;
                    high = sizeA-1;
                }
            }
        }
        if(sizeA!=a.length){
            if(sizeB!=0){
                if(a[sizeA] < b[sizeB-1]){
                    extendRight = true;
                    low = sizeA;
                }
            }
        }
        if(!shrinkLeft && !extendRight){
            return Math.max(a[sizeA-1],b[sizeB-1]) ;
        }
    }
    throw  new IllegalArgumentException("we can't be here");
}

We have a range of [low, high] for array a and we narrow this range as we go further through the algorithm. sizeA shows how many of items from k items are from array a and it derives from the value of low and high. sizeB is the same definition except we calculate the value such a way that sizeA+sizeB=k. The based on the values on those two borders with conclude that we have to extend to the right side in array a or shrink to the left side. if we stuck in the same position it means that we found the solution and we will return the max of values in the position of sizeA-1 from a and sizeB-1 from b.

Motoneuron answered 25/5, 2020 at 5:8 Comment(1)
if(a.length + a.length < k) should that have been b in one place? – Pralltriller
C
2

Here's my code based on Jules Olleon's solution:

int getNth(vector<int>& v1, vector<int>& v2, int n)
{
    int step = n / 4;

    int i1 = n / 2;
    int i2 = n - i1;

    while(!(v2[i2] >= v1[i1 - 1] && v1[i1] > v2[i2 - 1]))
    {                   
        if (v1[i1 - 1] >= v2[i2 - 1])
        {
            i1 -= step;
            i2 += step;
        }
        else
        {
            i1 += step;
            i2 -= step;
        }

        step /= 2;
        if (!step) step = 1;
    }

    if (v1[i1 - 1] >= v2[i2 - 1])
        return v1[i1 - 1];
    else
        return v2[i2 - 1];
}

int main()  
{  
    int a1[] = {1,2,3,4,5,6,7,8,9};
    int a2[] = {4,6,8,10,12};

    //int a1[] = {1,2,3,4,5,6,7,8,9};
    //int a2[] = {4,6,8,10,12};

    //int a1[] = {1,7,9,10,30};
    //int a2[] = {3,5,8,11};
    vector<int> v1(a1, a1+9);
    vector<int> v2(a2, a2+5);


    cout << getNth(v1, v2, 5);
    return 0;  
}
Christoforo answered 5/3, 2011 at 6:45 Comment(2)
This will not work for some cases. For example, int a2[] = {1,2,3,4, 5}; int a1[] = {5,6,8,10,12}; getNth( a1, a2, 7 ). The index of the array will go out of boundary. – Casting
@Jay: The index of the array will go out of [bounds] … in vector<int> v1(a1, a1+9)? Bummer :-/ (It does fail with one of the arrays shorter than half k (n): downvoting.) – Pralltriller
E
2

Here is my implementation in C, you can refer to @Jules Olléon 's explains for the algorithm: the idea behind the algorithm is that we maintain i + j = k, and find such i and j so that a[i-1] < b[j-1] < a[i] (or the other way round). Now since there are i elements in 'a' smaller than b[j-1], and j-1 elements in 'b' smaller than b[j-1], b[j-1] is the i + j-1 + 1 = kth smallest element. To find such i,j the algorithm does a dichotomic search on the arrays.

int find_k(int A[], int m, int B[], int n, int k) {
   if (m <= 0 )return B[k-1];
   else if (n <= 0) return A[k-1];
   int i =  ( m/double (m + n))  * (k-1);
   if (i < m-1 && i<k-1) ++i;
   int j = k - 1 - i;

   int Ai_1 = (i > 0) ? A[i-1] : INT_MIN, Ai = (i<m)?A[i]:INT_MAX;
   int Bj_1 = (j > 0) ? B[j-1] : INT_MIN, Bj = (j<n)?B[j]:INT_MAX;
   if (Ai >= Bj_1 && Ai <= Bj) {
       return Ai;
   } else if (Bj >= Ai_1 && Bj <= Ai) {
       return Bj;
   }
   if (Ai < Bj_1) { // the answer can't be within A[0,...,i]
       return find_k(A+i+1, m-i-1, B, n, j);
   } else { // the answer can't be within A[0,...,i]
       return find_k(A, m, B+j+1, n-j-1, i);
   }
 }
Evocative answered 11/12, 2013 at 17:16 Comment(0)
L
2

Here's my solution. The C++ code prints the kth smallest value as well as the number of iterations to get the kth smallest value using a loop, which in my opinion is in the order of log(k). The code however requires k to be smaller than the length of the first array which is a limitation.

#include <iostream>
#include <vector>
#include<math.h>
using namespace std;

template<typename comparable>
comparable kthSmallest(vector<comparable> & a, vector<comparable> & b, int k){

int idx1; // Index in the first array a
int idx2; // Index in the second array b
comparable maxVal, minValPlus;
float iter = k;
int numIterations = 0;

if(k > a.size()){ // Checks if k is larger than the size of first array
    cout << " k is larger than the first array" << endl;
    return -1;
}
else{ // If all conditions are satisfied, initialize the indexes
    idx1 = k - 1;
    idx2 = -1;
}

for ( ; ; ){
    numIterations ++;
    if(idx2 == -1 || b[idx2] <= a[idx1] ){
        maxVal = a[idx1];
        minValPlus = b[idx2 + 1];
        idx1 = idx1 - ceil(iter/2); // Binary search
        idx2 = k - idx1 - 2; // Ensures sum of indices  = k - 2
    }
    else{
        maxVal = b[idx2];
        minValPlus = a[idx1 + 1];
        idx2 = idx2 - ceil(iter/2); // Binary search
        idx1 = k - idx2 - 2; // Ensures sum of indices  = k - 2
    }
    if(minValPlus >= maxVal){ // Check if kth smallest value has been found
        cout << "The number of iterations to find the " << k << "(th) smallest value is    " << numIterations << endl;
        return maxVal;

    }
    else
        iter/=2; // Reduce search space of binary search
   }
}

int main(){
//Test Cases
    vector<int> a = {2, 4, 9, 15, 22, 34, 45, 55, 62, 67, 78, 85};
    vector<int> b = {1, 3, 6, 8, 11, 13, 15, 20, 56, 67, 89};
    // Input k < a.size()
    int kthSmallestVal;
    for (int k = 1; k <= a.size() ; k++){
        kthSmallestVal = kthSmallest<int>( a ,b ,k );
        cout << k <<" (th) smallest Value is " << kthSmallestVal << endl << endl << endl;
    }
}
Lowercase answered 5/3, 2014 at 23:9 Comment(0)
A
2

Basically, via this approach you can discard k/2 elements at each step. The K will recursively change from k => k/2 => k/4 => ... till it reaches 1. So, Time Complexity is O(logk)

At k=1 , we get the lowest of the two arrays.

The following code is in JAVA. Please note that the we are subtracting 1 (-1) in the code from the indices because Java array's index starts from 0 and not 1, eg. k=3 is represented by the element in 2nd index of an array.

private int kthElement(int[] arr1, int[] arr2, int k) {
        if (k < 1 || k > (arr1.length + arr2.length))
            return -1;
        return helper(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k);
    }


private int helper(int[] arr1, int low1, int high1, int[] arr2, int low2, int high2, int k) {
    if (low1 > high1) {
        return arr2[low2 + k - 1];
    } else if (low2 > high2) {
        return arr1[low1 + k - 1];
    }
    if (k == 1) {
        return Math.min(arr1[low1], arr2[low2]);
    }
    int i = Math.min(low1 + k / 2, high1 + 1);
    int j = Math.min(low2 + k / 2, high2 + 1);
    if (arr1[i - 1] > arr2[j - 1]) {
        return helper(arr1, low1, high1, arr2, j, high2, k - (j - low2));
    } else {
        return helper(arr1, i, high1, arr2, low2, high2, k - (i - low1));
    }
}
Amalbergas answered 25/8, 2017 at 15:55 Comment(0)
Q
1

The first pseudo code provided above, does not work for many values. For example, here are two arrays. int[] a = { 1, 5, 6, 8, 9, 11, 15, 17, 19 }; int[] b = { 4, 7, 8, 13, 15, 18, 20, 24, 26 };

It did not work for k=3 and k=9 in it. I have another solution. It is given below.

private static void traverse(int pt, int len) {
int temp = 0;

if (len == 1) {
    int val = 0;
    while (k - (pt + 1) - 1 > -1 && M[pt] < N[k - (pt + 1) - 1]) {

    if (val == 0)
        val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1]
            : M[pt];
    else {
        int t = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1]
            : M[pt];
        val = val < t ? val : t;

    }

    ++pt;
    }

    if (val == 0)
    val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt];

    System.out.println(val);
    return;
}

temp = len / 2;

if (M[pt + temp - 1] < N[k - (pt + temp) - 1]) {
    traverse(pt + temp, temp);

} else {
    traverse(pt, temp);
}

}

But... it is also not working for k=5. There is this even/odd catch of k which is not letting it to be simple.

Quadrivial answered 19/9, 2015 at 11:0 Comment(0)
W
1
public class KthSmallestInSortedArray {

    public static void main(String[] args) {
        int a1[] = {2, 3, 10, 11, 43, 56},
                a2[] = {120, 13, 14, 24, 34, 36},
                k = 4;

        System.out.println(findKthElement(a1, a2, k));

    }

    private static int findKthElement(int a1[], int a2[], int k) {

        /** Checking k must less than sum of length of both array **/
        if (a1.length + a2.length < k) {
            throw new IllegalArgumentException();
        }

        /** K must be greater than zero **/
        if (k <= 0) {
            throw new IllegalArgumentException();
        }

        /**
         * Finding begin, l and end such that
         * begin <= l < end
         * a1[0].....a1[l-1] and
         * a2[0]....a2[k-l-1] are the smallest k numbers
         */
        int begin = Math.max(0, k - a2.length);
        int end = Math.min(a1.length, k);

        while (begin < end) {
            int l = begin + (end - begin) / 2;

            /** Can we include a1[l] in the k smallest numbers */
            if ((l < a1.length) &&
                    (k - l > 0) &&
                    (a1[l] < a2[k - l - 1])) {

                begin = l + 1;

            } else if ((l > 0) &&
                    (k - l < a2.length) &&
                    (a1[l - 1] > a2[k - 1])) {

                /**
                 * This is the case where we can discard
                 * a[l-1] from the set of k smallest numbers
                 */
                end = l;

            } else {

                /**
                 * We found our answer since both inequalities were
                 * false
                 */
                begin = l;
                break;
            }
        }

        if (begin == 0) {
            return a2[k - 1];
        } else if (begin == k) {
            return a1[k - 1];
        } else {
            return Math.max(a1[begin - 1], a2[k - begin - 1]);
        }
    }
}
Wood answered 6/11, 2016 at 7:34 Comment(0)
I
1

Here is mine solution in java . Will try to further optimize it

  public class FindKLargestTwoSortedArray {

    public static void main(String[] args) {
        int[] arr1 = { 10, 20, 40, 80 };
        int[] arr2 = { 15, 35, 50, 75 };

    FindKLargestTwoSortedArray(arr1, 0, arr1.length - 1, arr2, 0,
            arr2.length - 1, 6);
    }


    public static void FindKLargestTwoSortedArray(int[] arr1, int start1,
            int end1, int[] arr2, int start2, int end2, int k) {

        if ((start1 <= end1 && start1 >= 0 && end1 < arr1.length)
                && (start2 <= end2 && start2 >= 0 && end2 < arr2.length)) {

            int midIndex1 = (start1 + (k - 1) / 2);
            midIndex1 = midIndex1 >= arr1.length ? arr1.length - 1 : midIndex1;
            int midIndex2 = (start2 + (k - 1) / 2);
            midIndex2 = midIndex2 >= arr2.length ? arr2.length - 1 : midIndex2;


            if (arr1[midIndex1] == arr2[midIndex2]) {
                System.out.println("element is " + arr1[midIndex1]);
            } else if (arr1[midIndex1] < arr2[midIndex2]) {

                if (k == 1) {
                    System.out.println("element is " + arr1[midIndex1]);
                    return;
                } else if (k == 2) {
                    System.out.println("element is " + arr2[midIndex2]);
                    return;
                }else if (midIndex1 == arr1.length-1 || midIndex2 == arr2.length-1 ) {
                    if(k==(arr1.length+arr2.length)){
                    System.out.println("element is " + arr2[midIndex2]);
                    return;
                    }else if(k==(arr1.length+arr2.length)-1){
                        System.out.println("element is " + arr1[midIndex1]);
                        return;
                    }

                }

                int remainingElementToSearch = k - (midIndex1-start1);
                FindKLargestTwoSortedArray(
                        arr1,
                        midIndex1,
                        (midIndex1 + remainingElementToSearch) >= arr1.length ? arr1.length-1
                                : (midIndex1 + remainingElementToSearch), arr2,
                        start2, midIndex2, remainingElementToSearch);

            } else if (arr1[midIndex1] > arr2[midIndex2]) {
                FindKLargestTwoSortedArray(arr2, start2, end2, arr1, start1,
                        end1, k);
            }

        } else {
            return;
        }

    }
}

This is inspired from Algo at wonderful youtube video

Ioab answered 30/12, 2016 at 14:15 Comment(0)
P
1

Link to code complexity (log(n)+log(m))

Link to Code (log(n)*log(m))

Implementation of (log(n)+log(m)) solution

I would like to add my explanation to the problem. This is a classic problem where we have to use the fact that the two arrays are sorted . we have been given two sorted arrays arr1 of size sz1 and arr2 of size sz2

a)Lets suppose if

Checking If k is valid

k is > (sz1+sz2)

then we cannot find kth smallest element in union of both sorted arrays ryt So return Invalid data. b)Now if above condition holds false and we have valid and feasible value of k,

Managing Edge Cases

We will append both the arrays by -infinity values at front and +infinity values at end to cover the edge cases of k = 1,2 and k = (sz1+sz2-1),(sz1+sz2)etc.

Now both the arrays have size (sz1+2) and (sz2+2) respectively

Main Algorithm

Now,we will do binary search on arr1 .We will do binary search on arr1 looking for an index i , startIndex <= i <= endIndex

such that if we find corresponding index j in arr2 using constraint {(i+j) = k},then if

if (arr2[j-1] < arr1[i] < arr2[j]),then arr1[i] is the kth smallest (Case 1)

else if (arr1[i-1] < arr2[j] < arr1[i]) ,then arr2[i] is the kth smallest (Case 2)

else signifies either arr1[i] < arr2[j-1] < arr2[j] (Case3)

or arr2[j-1] < arr2[j] < arr1[i] (Case4)

Since we know that the kth smallest element has (k-1) elements smaller than it in union of both the arrays ryt? So,

In Case1, what we did , we ensured that there are a total of (k-1) smaller elements to arr1[i] because elements smaller than arr1[i] in arr1 array are i-1 in number than we know (arr2[j-1] < arr1[i] < arr2[j]) and number of elements smaller than arr1[i] in arr2 is j-1 because j is found using (i-1)+(j-1) = (k-1) So kth smallest element will be arr1[i]

But answer may not always come from the first array ie arr1 so we checked for case2 which also satisfies similarly like case 1 because (i-1)+(j-1) = (k-1) . Now if we have (arr1[i-1] < arr2[j] < arr1[i]) we have a total of k-1 elements smaller than arr2[j] in union of both the arrays so its the kth smallest element.

In case3 , to form it to any of case 1 or case 2, we need to increment i and j will be found according using constraint {(i+j) = k} ie in binary search move to right part ie make startIndex = middleIndex

In case4, to form it to any of case 1 or case 2, we need to decrement i and j will be found according using constraint {(i+j) = k} ie in binary search move to left part ie make endIndex = middleIndex.

Now how to decide startIndex and endIndex at beginning of binary search over arr1 with startindex = 1 and endIndex = ??.We need to decide.

If k > sz1,endIndex = (sz1+1) , else endIndex = k;

Because if k is greater than the size of the first array we may have to do binary search over the entire array arr1 else we only need to take first k elements of it because sz1-k elements can never contribute in calculating kth smallest.

CODE Shown Below

// Complexity    O(log(n)+log(m))

#include<bits/stdc++.h>
using namespace std;
#define f(i,x,y) for(int i = (x);i < (y);++i)
#define F(i,x,y) for(int i = (x);i > (y);--i)
int max(int a,int b){return (a > b?a:b);}
int min(int a,int b){return (a < b?a:b);}
int mod(int a){return (a > 0?a:((-1)*(a)));}
#define INF 1000000




int func(int *arr1,int *arr2,int sz1,int sz2,int k)

{

if((k <= (sz1+sz2))&&(k > 0))

{
int s = 1,e,i,j;
if(k > sz1)e = sz1+1;
else e = k;
while((e-s)>1)
{
  i = (e+s)/2;
  j = ((k-1)-(i-1)); 
  j++;
  if(j > (sz2+1)){s = i;}
  else if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
  else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j];
  else if(arr1[i] < arr2[j-1]){s = i;}
  else if(arr1[i] > arr2[j]){e = i;}
  else {;}
}
i = e,j = ((k-1)-(i-1));j++;
if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j];
else
{
  i = s,j = ((k-1)-(i-1));j++;
  if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
  else return arr2[j];
}

  }

 else

{
cout << "Data Invalid" << endl;
return -INF;

}

}





int main()

{
int n,m,k;
cin >> n >> m >> k;
int arr1[n+2];
int arr2[m+2];
f(i,1,n+1)
cin >> arr1[i];
f(i,1,m+1)
cin >> arr2[i];
arr1[0] = -INF;
arr2[0] = -INF;
  arr1[n+1] = +INF;  
arr2[m+1] = +INF; 
int val = func(arr1,arr2,n,m,k);
if(val != -INF)cout << val << endl;   
return 0;

}

For Solution of complexity (log(n)*log(m))

Just i missed using advantage of the fact that for each i the j can be found using constraint {(i-1)+(j-1)=(k-1)} So for each i i was further applying binary search on second array to find j such that arr2[j] <= arr1[i].So this solution can be optimized further

Penang answered 2/3, 2017 at 6:4 Comment(0)
L
1
#include <bits/stdc++.h>
using namespace std;

int findKthElement(int a[],int start1,int end1,int b[],int start2,int end2,int k){

    if(start1 >= end1)return b[start2+k-1];
    if(start2 >= end2)return a[start1+k-1];
    if(k==1)return min(a[start1],b[start2]);
    int aMax = INT_MAX;
    int bMax = INT_MAX;
    if(start1+k/2-1 < end1) aMax = a[start1 + k/2 - 1];
    if(start2+k/2-1 < end2) bMax = b[start2 + k/2 - 1];

    if(aMax > bMax){
        return findKthElement(a,start1,end1,b,start2+k/2,end2,k-k/2);
    }
    else{
        return findKthElement(a,start1 + k/2,end1,b,start2,end2,k-k/2);
    }
}

int main(void){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m,k;
        cout<<"Enter the size of 1st Array"<<endl;
        cin>>n;
        int arr[n];
        cout<<"Enter the Element of 1st Array"<<endl;
        for(int i = 0;i<n;i++){
            cin>>arr[i];
        }
        cout<<"Enter the size of 2nd Array"<<endl;
        cin>>m;
        int arr1[m];
        cout<<"Enter the Element of 2nd Array"<<endl;
        for(int i = 0;i<m;i++){
            cin>>arr1[i];
        }
        cout<<"Enter The Value of K";
        cin>>k;
        sort(arr,arr+n);
        sort(arr1,arr1+m);
        cout<<findKthElement(arr,0,n,arr1,0,m,k)<<endl;
    }

    return 0;
}

Time Complexcity is O(log(min(n,m)))

Lilienthal answered 4/1, 2018 at 11:24 Comment(0)
C
0

Below C# code to Find the k-th Smallest Element in the Union of Two Sorted Arrays. Time Complexity : O(logk)

        public static int findKthSmallestElement1(int[] A, int startA, int endA, int[] B, int startB, int endB, int k)
        {
            int n = endA - startA;
            int m = endB - startB;

            if (n <= 0)
                return B[startB + k - 1];
            if (m <= 0)
                return A[startA + k - 1];
            if (k == 1)
                return A[startA] < B[startB] ? A[startA] : B[startB];

            int midA = (startA + endA) / 2;
            int midB = (startB + endB) / 2;

            if (A[midA] <= B[midB])
            {
                if (n / 2 + m / 2 + 1 >= k)
                    return findKthSmallestElement1(A, startA, endA, B, startB, midB, k);
                else
                    return findKthSmallestElement1(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1);
            }
            else
            {
                if (n / 2 + m / 2 + 1 >= k)
                    return findKthSmallestElement1(A, startA, midA, B, startB, endB, k);
                else
                    return findKthSmallestElement1(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1);

            }
        }
Cuckooflower answered 11/8, 2014 at 22:18 Comment(3)
there is no bug, i have tested my code before i posted to SO – Cuckooflower
Thanks sammy333, I have updated the code. now its working one – Cuckooflower
(Do not compute midA from endA if k < n. Check for short arrays, starting with return B[startB + k - 1];.) – Pralltriller
N
-1

Check this code.

import math
def findkthsmallest():

    A=[1,5,10,22,30,35,75,125,150,175,200]
    B=[15,16,20,22,25,30,100,155,160,170]
    lM=0
    lN=0
    hM=len(A)-1
    hN=len(B)-1
    k=17

    while True:
        if k==1:
            return min(A[lM],B[lN])


        cM=hM-lM+1
        cN=hN-lN+1
        tmp = cM/float(cM+cN)
        iM=int(math.ceil(tmp*k))
        iN=k-iM
        iM=lM+iM-1
        iN=lN+iN-1
        if A[iM] >= B[iN]:
            if iN == hN or A[iM] < B[iN+1]:
                return A[iM]
            else:
                k = k - (iN-lN+1)
                lN=iN+1
                hM=iM-1
        if B[iN] >= A[iM]:
            if iM == hM or B[iN] < A[iM+1]:
                return B[iN]
            else:
                k = k - (iM-lM+1)
                lM=iM+1
                hN=iN-1
        if hM < lM:
            return B[lN+k-1]
        if hN < lN:
            return A[lM+k-1]

if __name__ == '__main__':
    print findkthsmallest();
Ningpo answered 21/2, 2012 at 6:31 Comment(1)
Provide explanation – Bingen

© 2022 - 2024 — McMap. All rights reserved.