CareerCup

it can be done in log(n) time using binary search.
Do binary search in both arrays simultaneously, starting with lo1 = lo2 = 0 and hi1=hi2 = n;
At each step, chuck out a portion of each array.

public static int findNthRankElement(int[] a1, int[] a2, int n){
		// double binary search
		int lo1 = 0, lo2 = 0, hi1 = n, hi2 = n; 
		while (lo1 < hi1 && lo2 < hi2){
			int mid1 = lo1 + (hi1 - lo1)/2;
			int mid2 = lo2 + (hi2 - lo2)/2;
			
			if (a1[mid1] < a2[mid2]) {
				lo1 = mid1+1;
				hi2 = mid2-1;
			} else if (a1[mid1] > a2[mid2]) {
				hi1 = mid1-1;
				lo2 = mid2+1;
			} else {
				return a1[mid1];
			}
			
			//System.out.println(lo1 + " " + hi1 + " - " + lo2 + " " + hi2);
		}
		return (lo1 >= 0 && lo1 < a1.length) ? a1[lo1] :
			   (hi1 >= 0 && hi1 < a1.length) ? a1[hi1] :
			   (lo2 >= 0 && lo2 < a2.length) ? a2[lo2] :
				   a2[hi2] ;
	}

The funky return statement is because i couldn't be bother to figure out which one to return (btw this function return the actual element rather than it's rank)

Doing binary search.
Complexity: O(log N), where N is the size of array data

int getNth(int a[], int size_a,
           int b[], int size_b,
           int k) {
    
    if(size_a + size_b < k || k <= 0) {
        throw "Not found";
    }
    
    int left_a = 0;
    int right_a = (k < size_a) ? k : size_a;
    
    do {
	// pivots go from 0, 1...N 
	// 0 - dont include any element from that array
	// 1 - first element of the array
	// Hence, you will notice that all array references are left shifted by 1

        int pivot_a = left_a + (right_a - left_a) / 2;
        int pivot_b = k - pivot_a;
        
	// Second array is smaller than "k"
        if(pivot_b > size_b) {
            left_a = (left_a == size_b) ? size_b + 1 : size_b;
            continue;
        }
        
        if(pivot_a == 0 && left_a == right_a) {
            return b[k-1];
        }
        
        if(pivot_b == 0) {
            return a[k-1];
        }
        
	// We have found the expected element when:
	// element pointed by a pivot is less than or equal to all elements of the other array
	// Example with k = 5
	// 1,3,5,7,9
 	// 2,4,6,8,10
	// when pivot_a = 3 and pivot_b = 2
	// (a[pivot_a-1]=5) is less than (b[pivot_b]=6)
	// and 
	// (b[pivot_b-1]=2) is less than (a[pivot_a]=5)

        if(pivot_b == size_b || a[pivot_a-1] <= b[pivot_b]) {
            if(pivot_a == size_a || b[pivot_b-1] <= a[pivot_a]) {
                return (a[pivot_a-1] > b[pivot_b-1]) ? a[pivot_a-1] : b[pivot_b-1];
            }
            else {
                left_a = pivot_a + 1;
            }
        }
        else {
            right_a = pivot_a;
        }
    }
    while(1);
}

What does it mean by nth rank element? Does it mean nth largest/smallest element? Thanks.

Simplest method is to use merge() from mergeSort to end up with the combined sorted array, then selection-rank algorithm utilizing partition() from quickSort.
Merge: O(m+n)
Partition: O(lg(m+n)) avg, O(m+n) worst
Overall worst case: O(m+n)

There is also the observation that given some value v1 in array a, the rank of v1 in the combined array is the rank of v1 in array a + the rank of the largest value v2 in array b that is <= v1. Using this, you can recursively chop away regions of both arrays. However the hard part is finding the rank of v2, which itself is O(lgm) avg and O(m) worst case.
Using this technique, the avg case becomes O(lgnlgm), and worst O(mn). It is questionable whether the possible performance increase is worth the complexity and possible much worse performance.

Here is the method which i think will work here.

A, B are input arrays
FindRank(A, i1,j1, B, i2, j2, N)	
	if i1=j1 then
		q = Apply BS in B[i2..j2] for key A[j1], we use nearest value which is less then A[j1] to find this
		return B[i2 + |N-(q-i2+2)|] as response
	else if i2=j2 then
		q = Apply BS in A[i1..j1] for key B[j2], we use nearest value which is less then B[j2] to find this
		return A[i1 + |N-(q-i1+2)|] as response
	else
		q =  (j1+i1)/2
		r = Apply BS in B[i2..j2] for key A[q], we use nearest value which is less then A[q] to find this
		if N > (r-i2 + q-i1)
			call FindRank(A, q,j1, B, r, j2, N - (r-i2 + q-i1))
		else if N < (r-i2 + q-i1)
			call FindRank(A, i1,q, B, i2, r, N)
		else if N = (r-i2 + q-i1)
			return r or q based upon whether A[q] is big or B[r] is big
		end
	end
end

Complexity
Time : O(Log(n)*Log(n))
Space : O(1)

A simpler but O(N) complexity algorithm can be found using two pointer i, j strting from 0, and moving the samller value pointer until i+j < n.

how about this? Isn't this simple? Am I missing something?

private static int FindNth(int[] arr1, int[] arr2, int n)
        {
            int i = 0, j = 0, c = 2, target = 0;

            while (c < n)
            {
                if (arr1[i] < arr2[j])
                {
                    i++;
                    target = i;
                }
                else
                {
                    j++;
                    target = j;
                }
                
                c++;
            }
            return arr2[target];
        }

I can only think of a O(n) solution, where n is the rank.

Perform the merge method (as in the merge sort) to move one cursor on each sorted array. When both cursors have moved n times, you found the n-ranked element.

set a pointer i to first array A and j to second array B.
setup a counter to 0

in a loop--
compare A[i] and B[j]

if(A[i] = B[j])
increment counter. if(counter == n) then result = A[i] or B[j]. else increment i and j

if(A[i] < B[j])
increment counter. if(counter == n) then result = A[i]. else increment i

if(B[j] < A[i])
increment counter. if(counter == n) then result = B[j]. else increment j.
--

This will take care of assigning same rank to integers that are equal.
There are some more conditions to take care of

1. i > A size
compare subsequent integers in B and dont increment counter if they are equal. Once you find unequal subsequent integers, increment counter and check if the counter is n. in which case the first integer (smalled one) of the two being compared is the answer.
(same goes with j > B size, which ever runs out first)

2. you ran out of both A and B and counter is still not n, in which case there is no answer

space O(1)
time O(n)


what if the arrays are sorted in desc order or one is ascending the other is descending? the only difference in such cases will be if you are incrementing or decrementing i / j. In any case, i and j need to point to the smallest integer before starting comparisons.

// v1 and v2 are sorted vectors.
// value in nelem is valid only if return value is true
bool FindNthElement(vector<int>& v1, vector<int>& v2, int& nelem, int rank)
{
  bool ret = false;
  int n1 = v1.size(), n2 = v2.size();
  int size = n1+n2;
  int i=0,j=0,k=0, count = 0, temp;
  
  if( (rank <= size) && (rank>0) )
  {
    while( (k<size) && (count!=rank ) ) 
    {  
      if( (i<n1) && (j<n2) )
      {  
        if( v1.at(i) <= v2.at(j) )
        {  
          temp = v1.at(i); i++;
        }   
        else
        {  
          temp = v2.at(j); j++;
        }   
      }   
      else if(i<n1)
      {  
        temp = v1.at(i); i++;
      }   
      else
      {  
        temp = v2.at(j); j++;
      }   
      nelem = temp; count++;
      if( count == rank )
      {   
        ret = true;
      }   
      k++;
    }   
  }

  return ret;
}

Please let me know if you my code gives a wrong result. :)