# Find kth largest element in the union of two sorted array

Problem statement: Find $kth$ largest element in the union of two sorted array.

My introduction of the algorithm I spent a few hours to review two algorithms, Leetcode 4:Median of Two Sorted Arrays and Leetcode 215:Kth Largest Element in an Array together since median is a special case of kth element problem, and also read the article to talk about the kth largest element in the union of two sorted array, 3 solutions: 1:The trivial way, $O(m+n)$; 2: A better way, O(k); 3: The best solution, but non-trivial, O(lg m + lg n).

So, I decided to practice the algorithm "Find kth largest element in the union of two sorted array" (similar to Leetcode 4 and 215, but with some difference.), using binary search non-trivial one, C# Source code. Please help me to review the code.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace KthLargestElementTwoSortedArrays_OptimalSolution
{
/*
* Problem statement:
* Find kth largest element in the union of two sorted array.
*
* Introduction:
*
* Review Leetcode 4 and Leetcode 215 two algorithm, and then, read the  article:
* http://articles.leetcode.com/find-k-th-smallest-element-in-union-of
*
*
*
* Introduction of algorithms for the solutions:
* There are a few of solutions to solve the problem, one is to merge two sorted array and then
* find the kth largest element, the solution will take O(m + n) time, where m and n are two arrays's
* length respectively.
*
* But, we do not stop here. Try to beat the solution in time complexity, the following solution
* use binary search, and then use recursive solution to solve a small subproblem.
*
* We do not need to sort first k element in the array, and then find kth element. As long as
* we know that less than k/2 elements (denoted as m) are smaller than kth element in two sorted
* array, then we can solve a small subproblem - find (k - m)th largest element in two sorted
*
*
*/
class KthLargestElement
{
static void Main(string[] args)
{
RunSampleTestcase1();
}

/*
* 5th largest element from a union of two sorted arrays, integers from 1 to 10.
*/
public static void RunSampleTestcase1()
{
int[] array1 = new int[] { 1, 3, 5, 7, 9 };
int[] array2 = new int[] { 2, 4, 6, 8, 10 };

Debug.Assert( FindKthLargestElement(array1, array2, 5) == 5);
}

public static double FindKthLargestElement(int[] array1, int[] array2, int k)
{
return FindKthLargestElement_BinarySearch(array1, array1.Length, array2, array2.Length, k);
}

/*
*
* Using binary search to find kth largest element from the union of two sorted array
* in time complexity O(lg(n + m))
*
* Naive solution is to merge two sorted array, and then find kth largest element.
* Time complexity is O(n + m), n, m are the length of two arrays respectively.
*
* Current solution is to use binary search to expedite the search.
*
* Function spec:
*
* Find kth largest element from two sorted arrays,
* @array1 - sorted array ascending order
* @array2 - soretd array ascending order
*
* Always try to remove k/2 elements one time
*
* Recursive function: subproblem is a smaller problem.
*/
private static double FindKthLargestElement_BinarySearch(
int[] array1,
int   length1,
int[] array2,
int   length2,
int   k)
{
//always assume that length1 is equal or smaller than length2
if (length1 > length2)
return FindKthLargestElement_BinarySearch(array2, length2, array1, length1, k);

if (length1 == 0)
return array2[k - 1];

if (k == 1)
return Math.Min(array1, array2);

//divide k into two parts
int half_k         = Math.Min(k / 2, length1);
int rest_kElements = k - half_k;

if (array1[half_k - 1] == array2[rest_kElements - 1])
return array1[half_k - 1];

if (array1[half_k - 1] < array2[rest_kElements - 1])
{
// kth largest element definitely not in the range of array1[i], i is in [0, middleOfSearch_1 - 1]
int[] newArray1 = ArraySplice(array1, half_k);
return FindKthLargestElement_BinarySearch(newArray1, length1 - half_k, array2, length2, k - half_k);
}
else
{
int[] newArray2 = ArraySplice(array2, rest_kElements);
return FindKthLargestElement_BinarySearch(array1, length1, newArray2, length2 - rest_kElements, k - rest_kElements);
}
}

/*
* Remove first n items from the array
*
* similar to JavaScript array's API: splice
*    https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/splice
*
* syntax
* array.splice(start, deleteCount, item1, item2, ...)
*
*/
public static int[] ArraySplice(int[] array, int deleteCount)
{
int length = array.Length;

if (deleteCount <= length)
{
int[] result = new int[length - deleteCount];
for (int i = 0; i < length - deleteCount; i++)
result[i] = array[deleteCount + i];

return result;
}

return new int[] { };
}
}
}

• Pretty minor but not pass length to FindKthLargestElement_BinarySearch Jan 8, 2017 at 19:47
• @Paparazzi, I like your advice. Can you explain it with more detail, you suggest that it is better to set a class member as length variable? Jan 8, 2017 at 19:55
• Just get the length directly from the array Jan 8, 2017 at 19:57
• Just so you know, your solution appears to be $O(\log k * (n+m))$. The reason is that ArraySplice() makes a copy of the array, which takes either $O(n)$ or $O(m)$ time. If you would just avoid doing the copy and instead pass a starting index for each array to your function, you would be down to $O(\log k)$ time.
– JS1
Jan 9, 2017 at 18:58
• @JianminChen The new version looks good.
– JS1
Feb 5, 2017 at 2:09

Can't comment yet, so a few clarifications:

1. Isn't your test RunSampleTestcase1() incorrect? The fifth largest value would be 6. You appear to be returning the 5th smallest value. Also evidenced by return Math.Min(array1, array2);. I'd think the k^th largest should be return Math.Max(array1[array1.Length - 1], array2[array2.Length - 1]).

2. Why are you passing length as a parameter to FindKthLargestElement_BinarySearch()? Arrays already have a length parameter. Using that will make the code much easier to follow.

3. Why are you reinventing the wheel with ArraySplice()?

Note: All of these have one big red flag though. That article you linked is referencing arrays; however, it discusses using linked lists in the Big O notation. Those have a lot different properties than arrays in C#.

• @C Smith, you are correct, my code is to work on kth smallest element instead; however, in order to calculate largest element, just calculate (n + m - k) smallest element. Jan 8, 2017 at 20:10
• @C Smith, you are correct that the array's length does not need to be passed as an argument in the function FindKthLargestElement_BinarySearch. Jan 8, 2017 at 20:13
• @C Smith, ArraySplice() function, I did check C# Array class and found that the documentation of the array Splice API is not so clear as JavaScript array does. Jan 8, 2017 at 20:15
• @C Smith, I am not sure your note about the article, reference arrays vs linked list, Big O notation. Can you help me more on this concern? Jan 8, 2017 at 20:16
• @jianmin, the issue with the big o notation is that the author was only considering starting at the beginning of a list, and then working towards the end. This ignores known elements about an array (such as length), which can absolutely speed this up. Additionally, you don't need to do a binary search. In fact, you're probably able to speed this up to O(ln(k)). But I'll leave the proof up to you. As a starting point, consider finding where arr1 and arr2 intersect on the last element. Jan 8, 2017 at 23:08