Find kth Smallest Element in Two Sorted Arrays

O(m+n) Solution:
merge the two arrays using O(m+n) time and space, and then pick kth element from merged array.

O(k) Solution:
using two pointers and a counter, move forward the smaller value one until they are equal or hit k, when they are equal, move both of them forward and count it as 2. This is a solution always came up to me.

O(lgn+lgm) Solution:
I could not figure it out, I could understand many of the explainations but still could not easily to understand the code developed for it. Until I found explain from here:

This is the one finally makes me easily understand how it works.

When you calculate out the position of median, this is also a function to help find the median efficiently form two sorted arrays.

Ideas:
1. try to find half of k from both arrays.
2. compare the k/2th elements, discard the part that is higher than the bigger element in corresponding array, discard the part that is lower than the smaller element in the corresponding array.
3. after step 2, we know the elements smaller than smaller elements are part of the i or j elements within the k smallest elements
4. recursively check the rest of elements for k-i or k-j th smallest element.

First version:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

int findKthSmallestElement(int a[], int b[], int k) { if (a.length > b.length) return findKthSmallestElement(b, a, k);// this is for next condition // check. /* * Now case when size of smaller array is 0 i.e there is no element in * one array */ if (a.length == 0 && b.length > 0) return b[k - 1]; // due to zero based index /* case where K ==1 that means we have hit limit */ if (k == 1) return Math.min(a[0], b[0]); /* Now the divide and conquer part */ //i and j means length and not index int i = Math.min(k / 2,a.length);// Math.min(sizeA, k/2) ; int j = Math.min(k -i,b.length);// Math.min(sizeB, k/2) ; int[] aTmp, bTmp; if (a[i - 1] > b[j - 1]) { // let's use non-smart way the first aTmp = new int[i]; System.arraycopy(a, 0, aTmp, 0, i); bTmp = new int[b.length - j]; System.arraycopy(b, j, bTmp, 0, b.length - j); // Now we need to find only K-j th element since we have found out // the lowest j return findKthSmallestElement(aTmp, bTmp, k - j); } else { aTmp = new int[a.length - i]; System.arraycopy(a, i, aTmp, 0, a.length - i); bTmp = new int[j]; System.arraycopy(b, 0, bTmp, 0, j); // Now we need to find only K-i th element since we have found out // the lowest i return findKthSmallestElement(aTmp, bTmp, k - i); } }

Easy to understand, but not space wise.

Second Version:
In-place algorithm based on first version

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

static int findKthSmallestElementInPlace(int a[], int b[], int aStart,int aEnd,int bStart, int bEnd,int k) { /* * to maintain uniformity, we will assume that size_a is smaller than * size_b else we will swap array in call :) */ int aLength =aEnd-aStart+1; int bLength = bEnd-bStart+1; if ( aLength > bLength) return findKthSmallestElementInPlace(b, a, bStart,bEnd,aStart,aEnd, k);// this is for next condition // check. /* * Now case when size of smaller array is 0 i.e there is no element in * one array */ if ((aLength == 0 )&& bLength > 0) return b[bStart+k - 1]; // due to zero based index /* case where K ==1 that means we have hit limit */ if (k == 1) return Math.min(a[aStart], b[bStart]); /* Now the divide and conquer part */ int i = Math.min(k/2,a.length);// represents how many steps to advance based on start int j = k -i;// Math.min(sizeB, k/2) ; if (a[aStart+i-1 ] > b[bStart+j-1 ]) { // Now we need to find only K-j th element since we have found out // the lowest j int aS = aStart,aE = aStart+i-1;// including the bigger element int bS = bStart+j,bE = bEnd;//not including smaller element return findKthSmallestElementInPlace(a, b, aS, aE, bS, bE, k-j); } else { // Now we need to find only K-i th element since we have found out // the lowest i int aS = aStart+i,aE = aEnd; int bS = bStart,bE = bStart+j-1; return findKthSmallestElementInPlace(a, b, aS, aE, bS, bE, k-i); } }

Related use:
Find median from two sorted arrays.

1 2 3 4 5 6 7 8

static double findMedian(int a[],int b[]){ int len = a.length+b.length; if(len%2==0){ return (double) ((findKthSmallestElement(a, b, len/2)+findKthSmallestElement(a, b, len/2+1))/2.0); } else return (double) findKthSmallestElement(a, b, len/2+1); }

kth smallest Element in unsorted array

Find the kth largest element in an unsorted array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array's length.


Note: this is equivalent to find kth smallest element in unsorted array, just use a.length-k to convert it to kth largest element.





Brute force method:

sort the array and return the asked element.

Better method: quick select
derived from quick sort,but no need to sort the entire array, returns when kth element is figured out.

Basic functions for quick sort/select:

    /**
     * quicksort partition:
     * 1.range is the part of array to deal with(divid and conquer)
     * 2.this method use first element in range as a pivot
     * 3. returned value is index of pivot and pivot is in right position and won't change anymore
     * @param a
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] a, int left, int right) {
        int i = left;
        int j = right + 1;
        while(true) {//a[left] ispivot, someone might use right one, and someone randomly pick on
            while(i < right && a[++i] < a[left]);//move i, until it's a position that's no longer less than pivot
            while(j > left && a[left] < a[--j]);//move j, until it's a position that is no longer greater than pivot
            if(i >= j) {//this is important:only swap when i
                break;
            }//
            swap(a, i, j);//now a[i]>=pivot and a[j] <=pivot, swap them to put them into right range
        }
        swap(a, left, j);//finally put left/pivot to right position
        return j;
    }

    /**
     * basic array two elements swap
     * @param a
     * @param i
     * @param j
     */
    private void swap(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

Find kth smallest:

   /**
     * QuickSelect
     * Use partition algorithm in Quick Sort
     */
    public int findKthSmallest(int[] nums, int k) {
        //k = nums.length - k;
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            final int j = partition(nums, l, r);//j's value is figured out
            if(j < k) {
                l = j + 1;//j and its left are guaranteed to be less or equal to nums[j] 
            } else if (j > k) {
                r = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

Find kth largest element

   /**
     * QuickSelect
     * Use partition algorithm in Quick Sort
     */
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        findKtheSmallest(nums, nums.length-k);
        return nums[k];
    }