Problem statement:
Find \$kth\$ largest element in the union of two sorted array, assuming that two sorted arrays are in ascending order. The size of two arrays are \$m\$, \$n\$.
My introduction of the algorithm
To solve the kth largest element in the union of two sorted array, there are three solutions; \$1\$: The trivial way, time complexity is \$O(m+n)\$; \$2\$: A better way is with time complexity \$O(k)\$; \$3\$: The best solution, but non-trivial is with the time complexity \$O(lg m + lg n)\$ where \$m\$, \$n\$ are the length of two arrays.
I solved two issues in my last practice. First, make sure that the largest kth element is found instead of the smallest kth element. Secondly, the time complexity is \$O(lg m + lg n)\$, pass the array's position index instead of copying the array costing \$O(m)\$ or \$O(n)\$.
The practice is advised by the comment from JS1 Jan 9 on my last practice. "Just so you know, your solution appears to be \$O(logk∗(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 \$(logk)\$ time."
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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 the
* complexity, 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 array instead.
*
*/
class KthLargestElement
{
static void Main(string[] args)
{
RunSampleTestcase1();
}
/*
* 5th largest element from a union of two sorted arrays, integers
* from 1 to 10. Count from 10, 9, 8, 7, 6, so 6 is the 5th
* largest element
*/
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) == 6);
}
public static double FindKthLargestElement(int[] array1, int[] array2, int k)
{
int length1 = array1.Length;
int length2 = array2.Length;
int nthSmallest = length1 + length2 - k;
return FindKthSmallestElement_BinarySearch(array1, 0, array1.Length, array2, 0, array2.Length, nthSmallest);
}
/*
*
* Using binary search to find kth smallest 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 smallest element from two sorted arrays in ascending order,
* @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 FindKthSmallestElement_BinarySearch(
int[] array1,
int start1,
int length1,
int[] array2,
int start2,
int length2,
int k)
{
//always assume that length1 is equal or smaller than length2
if (length1 > length2)
{
return FindKthSmallestElement_BinarySearch(array2, start2, length2, array1, start1, length1, k);
}
if (length1 == 0)
{
return array2[k - 1];
}
if (k == 1)
{
return Math.Min(array1[0], array2[0]);
}
//divide k into two parts
int half_k = Math.Min( k / 2, length1);
int rest_kElements = k - half_k;
int firstNode1 = start1 + half_k - 1;
int firstNode2 = start2 + rest_kElements - 1;
if (array1[firstNode1] == array2[firstNode2])
{
return array1[firstNode1];
}
if (array1[firstNode1] < array2[firstNode2]) // remove half_k
{
// Go to solve a smaller subproblem, remove first part of the array1
int newStart = half_k;
int newLength = length1 - half_k;
int searchNew = k - half_k;
return FindKthSmallestElement_BinarySearch(
array1,
newStart,
newLength,
array2,
start2,
length2,
searchNew);
}
else // remove rest_kElements
{
// Go to solve a smaller subproblem, remove first part of the array2
int newStart = rest_kElements;
int newLength = length2 - rest_kElements;
int searchNew = k - rest_kElements;
return FindKthSmallestElement_BinarySearch(
array1,
start1,
length1,
array2,
newStart,
newLength,
searchNew);
}
}
}
}
