3
\$\begingroup\$

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;
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 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. 
     *        
     * 
     */
     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[0], array2[0]);

            //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[] { };
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Pretty minor but not pass length to FindKthLargestElement_BinarySearch \$\endgroup\$ – paparazzo Jan 8 '17 at 19:47
  • \$\begingroup\$ @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? \$\endgroup\$ – Jianmin Chen Jan 8 '17 at 19:55
  • 1
    \$\begingroup\$ Just get the length directly from the array \$\endgroup\$ – paparazzo Jan 8 '17 at 19:57
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JS1 Jan 9 '17 at 18:58
  • 1
    \$\begingroup\$ @JianminChen The new version looks good. \$\endgroup\$ – JS1 Feb 5 '17 at 2:09
1
\$\begingroup\$

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[0], array2[0]);. 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#.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Jianmin Chen Jan 8 '17 at 20:10
  • \$\begingroup\$ @C Smith, you are correct that the array's length does not need to be passed as an argument in the function FindKthLargestElement_BinarySearch. \$\endgroup\$ – Jianmin Chen Jan 8 '17 at 20:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Jianmin Chen Jan 8 '17 at 20:15
  • \$\begingroup\$ @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? \$\endgroup\$ – Jianmin Chen Jan 8 '17 at 20:16
  • \$\begingroup\$ @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. \$\endgroup\$ – C Smith Jan 8 '17 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.