Leeetcode 215: Find kth largest element in two sorted array - https://leetcode.com/problems/kth-largest-element-in-an-array/

Leetcode215_kthLargestElementInTwoSortedArrays

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode215_KthLargestElementTwoSortedArrays
{
    /*
     * Leetcode 215: Find kth largest elment in two sorted arrays 
     * 
     * 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 array instead. 
     * 
     * As long as k/2 > 1, we are ready to go for the solution. 
     * 
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            RunSampleTestcase(); 
        }

        /*
         * kth largest element from two sorted arrays {1,3,5,7,9}, array {2, 4, 6, 8, 10}
         * 
         */
        public static void RunSampleTestcase()
        {
            int[] array1 = new int[] { 1, 3, 5, 7, 9 };
            int[] array2 = new int[] { 2, 4, 6, 8, 10 };

            double result = FindKthLargestElementFromTwoSortedArray(array1, array2, 5); 
        }

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

        /*
         *
         * Using binary search to find medium of two sorted array in time complexity O(lg(n + m))
         *
         * There are a lot of discussion of medium of two sorted array using binary search, 
         * certain conditions may apply. I will document it in detail later. 
         *    
         * 
         * 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[0], array2[0]);

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

            if (array1[p1 - 1] == array2[p2 - 1])
                return array1[p1 - 1];

            // array1 first p1 -1 elements are definitely in the first k elements,
            // ready to remove. 
            if (array1[p1 - 1] < array2[p2 - 1])
            {
                int[] newArray1 = ArraySplice(array1, p1);
                return FindKthLargestElement_BinarySearch(newArray1, length1 - p1, array2, length2, k - p1);
            }
            else 
            {
                int[] newArray2 = ArraySplice(array2, p2);
                return FindKthLargestElement_BinarySearch(array1, length1, newArray2, length2 - p2, k - p2);
            }            
        }

        /*
         * 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[]{};
        }
    }
}