CareerCup

why not using min heap of size 3

parse the array, when ever the element in the array is greater than the root of min heap, replace the root with new element and run min heapify on root

at the end, root will contain the third largest number

this can also be modified to find kth largest element where k = 1 to n

order statistics with rank n-3.
can be solved in O(n) time.
However, is it any better than O(3n)? Maintaining a buffer to hold three elements sounds better because we don't have to participate and call recursively which is pretty expensive by itself.

order statistics

you can use quick sort for this.. just modify the method of quicksort
just check when ever the partition method return n(here it is 3 for ur question) return that value..simple... because partition place that value into its original location...

find max1 max2 max3 among the first 3 elements.

then start from fourth element till end.
there will be some cases and comparisons will be more
but complexity will be O(n)

1 build the max heap if we're allowed to change the array
2 swap the root with the last element of the heap and decrement the heap size
3 rep 2 twice and the root is the 3rd largest element

{{
int[] myArr = {6, 7, 8, 9, 10, 1,2,3,4,5};
HashSet<Integer> mySet = new HashSet<Integer>();

for(int i : myArr)
{
mySet.add(i);
}

int size = mySet.size();
int breaker = size - 3;
for(int i : mySet)
{
if(i == breaker)
System.out.println(i);
}
}}

Use QuickSelect, modification of quicksort. I have written algorithm to find kth smallest number, you can modify it to find 3rd largest number.

seesharpconcepts.blogspot.in/2012/05/linear-solution-finding-kth-smallest.html

This algo may look like nonlinear but in practical it works in O(n).

This is my approach. I believe Complexity is O(n). Correct me if I'm wrong.

public class ThirdLargestEle {

	static int thirdLargEle(int[] nums) throws Exception {
		if(nums.length < 3) {
			throw new Exception("This array is too small to obtain the 3rd LargestElement");
		}
		int[] topThree = new int[3];
		topThree[0] = nums[0];
		topThree[1] = nums[1];
		topThree[2] = nums[2];

		for(int i = 3 ; i < nums.length ; i++) {
			int min = Math.min(Math.min(topThree[0],topThree[1]), topThree[2]);
			if(nums[i] > min ) {
				if(topThree[0] == min) {
					topThree[0] = nums[i];
				} else if(topThree[1] == min) {
					topThree[1] = nums[i];
				} else if(topThree[2] == min) {
					topThree[2] = nums[i];
				}
			}
		}
		return Math.min(Math.min(topThree[0],topThree[1]), topThree[2]);
	}
	public static void main(String[] args) throws Exception {
		int[] a = {100,100,3};
		System.out.println(thirdLargEle(a));
	}
}

below is my code [implemented order statistics] which has linear (0(n)) complexity

public class RandomizedSelect {

public static void main(String[] args) {
int[] A = {7,4,11,3,19,25,21,20,43,1,12,2,9};
// for 3rd largest one
System.out.println(randomizedSelect(A,0,A.length-1,A.length -1-3));

}

public static int randomizedSelect(int[] A, int p, int r, int i){
if(p == r)
return A[p];
int q = randomizedPartition(A,p,r);
int k = q - p + 1;
if(i == k)
return A[q];
else if(i < k)
return randomizedSelect(A,p,q-1,i);
else
return randomizedSelect(A, q+1, r, i-k);


}

public static int randomizedPartition(int[] input, int left, int right){
int randPivot = left + (int)Math.random()*((right-left)+1);
swap(input, right,randPivot);
return partition(input,left,right);
}

public static int partition(int[] input, int left, int right){
int pivot = input[right];
int i = left -1;

for(int j =left ; j < right; j++){
if(input[j] <= pivot){
i++;
swap(input,i,j);
}
}

swap(input,i+1,right);
return i+1;
}

public static void swap(int[] input,int p, int q){
int tmp = input[p];
input[p] = input[q];
input[q] = tmp;
}

what about tournament tree. it's kind of like merge sort, but we dont need to actually sort, just select the largest. first round we will cut half of the players. 2nd round 1/4....
the last run, say nth run, will have to compare the largest two. so the result should be in n - 1 run and there we have 4 element to compare. so its n complexity.

using buffer but one loop

private void thirdhighest() {
		// how to find the Third largest Element in an array of integers..? 
		//I suggested a logic using a buffer that can hold three elements..
		//But it is of O(3n) complexity..Can someone give a better algorithm
		
		
		int [] arr = new int []{11,1,10,9,8,7,6,5,4,2,3};
		
		int[] temp = new int[3];
		
		temp[0]=arr[0];
		temp[1]=arr[1];
		temp[2]=arr[2];
		
		
			
		
		
		for (int i = 3; i < arr.length; i++) {
			
			
			if(temp[0]>temp[1]){
				int a = temp[0];
				temp[0]=temp[1];
				temp[1]=a;
			}
			
			if(temp[1]>temp[2]){
				int a = temp[2];
				temp[2]=temp[1];
				temp[1]=a;
			}
			
			if(temp[0]>temp[1]){
				int a = temp[0];
				temp[0]=temp[1];
				temp[1]=a;
			}
				
			
			if(temp[0]<arr[i])
				temp[0]=arr[i];
			
		}
		
		System.out.println("temp[0]="+temp[0]+"=temp[1]="+temp[1]+"=temp[2]="+temp[2]);
System.out.println("third highest:::"+temp[0]);
		
	}

Order statistic will take nlogn to build the tree, Even modified quick sort that does recursive partition takes nlogn.
I dont think any thing better than 3buffer for this problem is possible.