Algorithm to find the kth largest element in unsorted list

[Mansukhdeep Thind]

Here is what I could write.

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
import java.util.TreeSet;

public class KthGreatestNumberInUnsortedList {

	public static void main(String[] args){
		List<Integer> myList= new ArrayList<Integer>();
		myList.add(6);
		myList.add(42);
		myList.add(8);
		myList.add(1);
		myList.add(27);
		myList.add(39);
		myList.add(12);


		// Get the value of K from the user
		System.out.println("Enter the rank k :");
		Scanner scanner = new Scanner(System.in);
		int k = scanner.nextInt();


		KthGreatestNumberInUnsortedList greatestNumber = new KthGreatestNumberInUnsortedList();




		List<Integer> list = greatestNumber.topKElementsInList(myList, k);
		List<Integer> list2 = greatestNumber.smallestNumberFromList(myList);
		System.out.println("Top " + k + "elements are :");
		for(Integer i: list){
			System.out.println(i);
		}

	}



	/**
	 * 
	 * @param myList - Unordered list of integers 
	 * @return - list of size 1 which will be the greatest number
	 */
	public List<Integer> greatestNumberFromList(List<Integer> myList){

		// We have to repeat this exercise until we get a list of size=1
		while(myList.size()>1){

			// generate a random number based on the size of the list which will represent the position
			//of the arbitrary element in the list
			int randomElementIndex = new Random().nextInt(myList.size());

			// find the arbitrary element
			int randomElement = myList.get(randomElementIndex);

			// temporary list to store the subset containing the n greatest integers
			List<Integer> greaterNumbersList= new ArrayList<Integer>();

			// iterate through the list and partition 
			// the elements
			for(int i=0;i<myList.size();i++){
				if(myList.get(i)>randomElement){
					greaterNumbersList.add(myList.get(i));
				}

			}			

			if(greaterNumbersList.size()==0){
				greaterNumbersList.add(randomElement);
			}

			//reset the reference myList to point to the temporary list
			myList = greaterNumbersList;

			// till the size of this temporary list is more than 1, we recursively call
			// this method from within itself supplying it the temporary list of that pass
			if(myList.size()>1){
				greatestNumberFromList(myList);				
			}
			// when size becomes 1, we have the greatest element with us
			// so we break out of the loop and return the final list
			else{
				break;
			}
		}
		return myList;



	}



	public List<Integer> topKElementsInList (List<Integer> myList, int k){



		List<Integer> topKElements = new ArrayList<Integer>();
		List<Integer> remainingElements = new ArrayList<Integer>();

		// pick k elements at random
		// and store it in temporary list
		for(int i=0; i<k;i++){
			topKElements.add(myList.get(i));
		}


		// store the rest of elements in
		// another temporary list

		for(int i=k; i<myList.size();i++){
			remainingElements.add(myList.get(i));
		}


		Integer [] topKArray =  topKElements.toArray(new Integer[k]);

		Integer [] remainingArray =  remainingElements.toArray(new Integer[myList.size()-k]);

		for(int i=0;i<topKArray.length;i++){
			List<Integer> smallestInTopKArray = smallestNumberFromList(Arrays.asList(topKArray));
			int smallestElement = smallestInTopKArray.get(0);
			int indexOfSmallestElementInTopKArray = Arrays.asList(topKArray).indexOf(smallestElement);
			for(int j=0;j<remainingArray.length;j++){
				if(remainingArray[j]>smallestElement){
					int temp = topKArray[indexOfSmallestElementInTopKArray];
					topKArray[indexOfSmallestElementInTopKArray]=remainingArray[j];
					remainingArray[j]=temp;
					break;
				}
			}

		}

		myList = Arrays.asList(topKArray);

		return myList;

	}

	/**
	 * 
	 * @param myList - Unordered list of integers 
	 * @return - list of size 1 which will be the greatest number
	 */
	public List<Integer> smallestNumberFromList(List<Integer> myList){

		// We have to repeat this exercise until we get a list of size=1
		while(myList.size()>1){

			// generate a random number based on the size of the list which will represent the position
			//of the arbitrary element in the list
			int randomElementIndex = new Random().nextInt(myList.size());

			// find the arbitrary element
			int randomElement = myList.get(randomElementIndex);

			// temporary list to store the subset containing the n greatest integers
			List<Integer> smallerNumbersList= new ArrayList<Integer>();

			// iterate through the list and partition 
			// the elements
			for(int i=0;i<myList.size();i++){
				if(myList.get(i)<randomElement){
					smallerNumbersList.add(myList.get(i));
				}

			}			

			if(smallerNumbersList.size()==0){
				smallerNumbersList.add(randomElement);
			}

			//reset the reference myList to point to the temporary list
			myList = smallerNumbersList;

			// till the size of this temporary list is more than 1, we recursively call
			// this method from within itself supplying it the temporary list of that pass
			if(myList.size()>1){
				smallestNumberFromList(myList);				
			}
			// when size becomes 1, we have the greatest element with us
			// so we break out of the loop and return the final list
			else{
				break;
			}
		}
		return myList;



	}
}

It has a bug. It is producing incorrect output for k=2. For k=1,3,4,5,6 , it is working fine.

[Winston Gutkowski]

Mansukhdeep Thind wrote:Here is what I could write.

Rather than prolong this too much, here's my solution. See if you follow it:

private static final <T extends Comparable<? super T>> int indexSmallest(
      List<T> values, int end)
{
   T smallest = values.get(0);
   int index = 0;
   for (int i = 1; i < end; i++) {
      T value = values.get(i);
      if (value.compareTo(smallest) < 0) {
         smallest = value;
         index = i;
      }
   }
   return index;
}

public static final <T extends Comparable<? super T>> int kthLargest(
      List<T> values, int k)
{
   int s = indexSmallest(values, k);
   T smallest = values.get(s);
   for (int i = k; i < values.size(); i++) {
      T current = values.get(i);
      if (current.compareTo(smallest)) > 0) {
         values.set(s, current);
         values.set(i, smallest); // not strictly necessary
         s = indexSmallest(values, k);
         smallest = values.get(s);
      }
   }
   return smallest;
}

it probably needs a check or two to make it bulletproof; but hopefully you get the general idea.

Winston

PS: So I lied; 30 lines, not 20.

[Mansukhdeep Thind]

I nailed it Winston. Here is my code:

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class KthGreatestNumberInUnsortedList {

	public static void main(String[] args){
		List<Integer> myList= new ArrayList<Integer>();
		myList.add(6);
		myList.add(42);
		myList.add(8);
		myList.add(100);
		myList.add(27);
		myList.add(39);
		myList.add(12);
		myList.add(270);
		myList.add(390);
		myList.add(12);


		// Get the value of K from the user
		System.out.println("Enter the rank k :");
		Scanner scanner = new Scanner(System.in);
		int k = scanner.nextInt();


		KthGreatestNumberInUnsortedList greatestNumber = new KthGreatestNumberInUnsortedList();




		List<Integer> list = greatestNumber.topKElementsInList(myList, k);
		List<Integer> list2 = greatestNumber.smallestNumberFromList(list);
		System.out.println(k + "largest element is:");
		for(Integer i: list2){
			System.out.println(i);
		}
		
		
		

	}



	/**
	 * 
	 * @param myList - Unordered list of integers 
	 * @return - list of size 1 which will be the greatest number
	 */
	public List<Integer> greatestNumberFromList(List<Integer> myList){

		// We have to repeat this exercise until we get a list of size=1
		while(myList.size()>1){

			// generate a random number based on the size of the list which will represent the position
			//of the arbitrary element in the list
			int randomElementIndex = new Random().nextInt(myList.size());

			// find the arbitrary element
			int randomElement = myList.get(randomElementIndex);

			// temporary list to store the subset containing the n greatest integers
			List<Integer> greaterNumbersList= new ArrayList<Integer>();

			// iterate through the list and partition 
			// the elements
			for(int i=0;i<myList.size();i++){
				if(myList.get(i)>randomElement){
					greaterNumbersList.add(myList.get(i));
				}

			}			

			if(greaterNumbersList.size()==0){
				greaterNumbersList.add(randomElement);
			}

			//reset the reference myList to point to the temporary list
			myList = greaterNumbersList;

			// till the size of this temporary list is more than 1, we recursively call
			// this method from within itself supplying it the temporary list of that pass
			if(myList.size()>1){
				greatestNumberFromList(myList);				
			}
			// when size becomes 1, we have the greatest element with us
			// so we break out of the loop and return the final list
			else{
				break;
			}
		}
		return myList;



	}



	public List<Integer> topKElementsInList (List<Integer> myList, int k){



		List<Integer> topKElements = new ArrayList<Integer>();
		List<Integer> remainingElements = new ArrayList<Integer>();

		// pick k elements at random
		// and store it in temporary list
		for(int i=0; i<k;i++){
			topKElements.add(myList.get(i));
		}


		// store the rest of elements in
		// another temporary list

		for(int i=k; i<myList.size();i++){
			remainingElements.add(myList.get(i));
		}


		Integer [] topKArray =  topKElements.toArray(new Integer[k]);

		Integer [] remainingArray =  remainingElements.toArray(new Integer[myList.size()-k]);

		for(int i=0;i<remainingArray.length;i++){

			for(int j=0;j<topKArray.length;j++){
				List<Integer> smallestInTopKArray = smallestNumberFromList(Arrays.asList(topKArray));
				int smallestElement = smallestInTopKArray.get(0);
				int indexOfSmallestElementInTopKArray = Arrays.asList(topKArray).indexOf(smallestElement);
				if(remainingArray[i]>smallestElement){
					int temp = topKArray[indexOfSmallestElementInTopKArray];
					topKArray[indexOfSmallestElementInTopKArray]=remainingArray[i];
					remainingArray[i]=temp;
					break;
				}
			}

		}
		myList = Arrays.asList(topKArray);

		return myList;

	}

	/**
	 * 
	 * @param myList - Unordered list of integers 
	 * @return - list of size 1 which will be the greatest number
	 */
	public List<Integer> smallestNumberFromList(List<Integer> myList){

		// We have to repeat this exercise until we get a list of size=1
		while(myList.size()>1){

			// generate a random number based on the size of the list which will represent the position
			//of the arbitrary element in the list
			int randomElementIndex = new Random().nextInt(myList.size());

			// find the arbitrary element
			int randomElement = myList.get(randomElementIndex);

			// temporary list to store the subset containing the n greatest integers
			List<Integer> smallerNumbersList= new ArrayList<Integer>();

			// iterate through the list and partition 
			// the elements
			for(int i=0;i<myList.size();i++){
				if(myList.get(i)<randomElement){
					smallerNumbersList.add(myList.get(i));
				}

			}			

			if(smallerNumbersList.size()==0){
				smallerNumbersList.add(randomElement);
			}

			//reset the reference myList to point to the temporary list
			myList = smallerNumbersList;

			// till the size of this temporary list is more than 1, we recursively call
			// this method from within itself supplying it the temporary list of that pass
			if(myList.size()>1){
				smallestNumberFromList(myList);				
			}
			// when size becomes 1, we have the greatest element with us
			// so we break out of the loop and return the final list
			else{
				break;
			}
		}
		return myList;



	}
}

I shall mark this as resolved now. Thanks all you guys.