Kth Largets element in an sorted array.

Hi All,

For today the problem statement is this :

Find the Kth largest element in a sorted array.

Solutions:

Lets for the sake of simplicity  consider the array is in descending order.Futher duplicates are possible.

Below is one of the possible solutions :

Go through each element in the sorted , copy each non-repeated element to a different array. At the end Kth largest element is copy[k-1] element.

int []sortedArray={10,9,9,8,6,5,5,3,3,2,1};

       

        int k=3;

        /*                 logic

         *

         * 1. Copy each different integer to a new array.

         * 2. Now the Kth largest element would be

         *         a) a[k-1] if in descending order

         *         b) a[length-k-1]

         *

         *

         * */

       

        int []copy=new int[sortedArray.length];

        /* the problem with this approach is we dnt know how many duplicates are there*/

        int j=1;

        copy[0]=sortedArray[0];

       

        for(int i=1;i<sortedArray.length;i++){

            if(sortedArray[i]!=sortedArray[i-1]){

                copy[j++]=sortedArray[i];

            }

        }

       

        for(int i:copy){

            System.out.println(i);

        }

       

        /* now the Kth largest element is copy[K-1]*/

       

       

        System.out.println(k+"th largest element is :"+copy[k-1]);

       

Now lets discuss the implications of this scheme.

We have used an auxiliary array named copy[] . As we dont know before hand how many different non-repeated element exists in the array we need to create the copy with that of the size of the original array.

Lets say the size of the original array is 1 million ... its too bad approach . It needs O(N) augmented space (apart from space for the original array).

We will also see time complexity for the above algorithm . Meanwhile I found the follwing links interesting

http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

The point to be noted there in the notes is that we see how scalable our algorithm with the input size !!.Which algorithm runs faster is secondary and requires more details  .

Now we analyze our code:

for(int i=1;i<sortedArray.length;i++){

            if(sortedArray[i]!=sortedArray[i-1]){

                copy[j++]=sortedArray[i];

            }

        }

lets say  the bit of code   if(sortedArray[i]!=sortedArray[i-1]){

                copy[j++]=sortedArray[i];

            }

takes a constant time K . That is it is O(1).

So the time complexity is O(N*1) =O(N). In all the cases.

Clearly from the analysis of space and time complexity this approach is not sufficient.

Now lets look for some other way.

In the following code we maintain a counter to count the no of different values that we have read so far in the array. The point here is we would like to see the Kth value i.e counter=K.

 */
        int []sortedArray={10,9,9,8,6,5,5,3,3,2,1};
       
        int k=3;
       
        int count=1;
       
        for(int i=1;i<sortedArray.length;i++){
           
            if(sortedArray[i]!=sortedArray[i-1]){
                count++;
               
            }
           
            if(count= =k){
                System.out.println(sortedArray[i]);
                break;
            }
               
           
           
           
        }

the beauty of the above code is evident . We dont need any auxiliary memory . The space complexity is O(N) for the original array only.

Now coming to the time complexity the worst case time complexity remains the same , assuming all preliminary operations take constant time, which is O(N). However the best case and worst case scenarios are promising than the previous approach.

Still we are not satisfied with the worst case performance as it is O(N) . We need more good approaches.

To be continued in next post .

Request  : Kindly give your valuable suggestions and comments on the content. Feel free to debate about the content.