7
\$\begingroup\$

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(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 \$(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);
        }
    }       
  }
}
\$\endgroup\$
4
\$\begingroup\$

Your code looks really good, but there are some things I'm not necessarily a fan of:

private static double FindKthSmallestElement_BinarySearch(
   int[] array1,
   int   start1, 
   int   length1,
   int[] array2,
   int   start2, 
   int   length2,
   int   k)

This reminds me of the C/C++ days and when I did DirectX programming. Every single method had the parameters listed out like this because we didn't have the powerful Intellisense then, and it was easy to lay them out in headers like this to allow us to reference easily. But it's 2017, and this is C#, we don't need to lay things out like this, it should be a red flag that we're doing something wrong.

And what may be that 'wrong' thing? We're not encapsulating our data. The fact that we have three variables with a suffix of 1 or 2 tells us that we could encapsulate those and save ourselves several parameters, since they're co-dependent.

public class SearchArray
{
    public int[] Array { get; set; }
    public int Start { get; set; }
    public int Length { get; set; }
}

The interesting thing here is we may get an increase in performance by making this array mutable, but at least it shortens our method prototype:

public static double FindKthSmallestElement_BinarySearch(SearchArray array1, SearchArray array2, int k)

The rest of it looks great. I won't comment on the algorithm, because I'm not an algorithms person, and it looks like it does what it wants.

What I'm even more interested in is the fact that you wrote this algorithm so clearly that it's easy to follow and read. Personally, I think more people should take that page out of this playbook and write code for clarity first, then deal with whatever issues may arise.

\$\endgroup\$
1
\$\begingroup\$

I have to write some code review and make some corrections on the above C# code.

Testing using Leetcode 4 online judge

It is Sunday Dec. 17, 2017, 10 months after I posted the question, I had a mock interview and then peer asked me to solve the algorithm Leetcode 4: median of two sorted array. So I shared my solution using the above code, but the peer sent an email to tell me that the code has bugs.

I spent over 60 minutes to fix all the bugs using the code to solve Leetcode 4 algorithm. Here is the C# code to pass the Leetcode 4 online judge.

There are several bugs in my original code.

Missing one value

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);
}

The statement to calculate nthSmallest should be the following:

int nthSmallest = length1 + length2 - k + 1; 

Base Case

Function FindKthSmallestElement_BinarySearch's two arguments start1 and start2 should apply to multiple statements.

Here are details:

if (k == 1)
{
    return Math.Min(array1[0], array2[0]); 
}

Instead the statement should be

return Math.Min(array1[start1], array2[start2]);

Four more places

The start1 and start2 variable should be applied to the index value of the array in another four places. The comments are added starting from "bug fix", the variable's declaration of firstNode1, firstNode2, newStart variables.

The following is the C# code without a bug based on Leetcode 4 online judge:

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[start2 + k - 1];
    }

    if (k == 1)
    {
        return Math.Min(array1[start1], array2[start2]); // bug fix: start1 and start2 instead of 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; // bug fix: add start1
    int firstNode2 = start2 + rest_kElements - 1; // bug fix: add start2

    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 = start1 + half_k;  // bug fix: missing start1 value
        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 = start2 + rest_kElements;  // bug fix: missing start2
        int newLength = length2 - rest_kElements;
        int searchNew = k - rest_kElements;

        return FindKthSmallestElement_BinarySearch(
            array1,
            start1,
            length1,
            array2,
            newStart,
            newLength,
            searchNew);
    }
}    
\$\endgroup\$

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.