CareerCup

Use the partition algorithm in quicksort till there are 2 elements in the right

A min heap of length 3 will do the job...

en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Sorting the array has complexity O(nlogn).

Here is a O(n) solution:

Maintain a priority queue (PQ) that never grows beyond size 3, and where the order is ascending, i.e. the element in front is the lowest of the 3 elements. Step through the array. Whenever a value is greater than the front of the PQ, remove the front element from the PQ, and put the new value in its right place in the PQ. When finished, the 3rd largest integer will be in front of the PQ.

Complexity:
Scanning the array: O(n)
Replacing an element in the PQ: O(1) (since the size is a constant k=3)
Totally: O(n)

Often a heap is used for PQ, but in this case the PQ is so small that an array will do fine.

Find the largest integer and discard it from the array. Do this twice. Find the largest integer once more and return it. O(n) and simple to describe but not the best constant factor for O(n).

Heapify and Remove Three Elements

int thirdLargest(int[] arr,int k){
	return createMaxHeap(arr,k);
}


 int createMaxHeap(int[] arr,int k){
	Heap h = new Heap(arr.length);	
	for(int i=0;i<arr.length;i++){
		h.insert(arr[i]);
	}
	int max = 0;
	int i = 0;
	while(i < k-1){
		max = h.extractMax();
		i++;
	}
	return max;
}

class Heap{
	
	private int[] heapArray;
	private int currentSize;
	private int maxSize;
	private int FRONT = 1;

	Heap(int maxSize){
		this.maxSize = maxSize;
		this.currentSize = 0;
		this.heapArray = new int[maxSize];
	}
	
	
	
	public boolean insert(int key){
		
		if(currentSize==maxSize)return false;
		heapArray[currentSize] = key;
		tickleUp(currentSize++);
		return false;
		
		
		
	}
	
	
	public int extractMax(){
		if(currentSize==0)
			return Integer.MAX_VALUE;
		
		int root = heapArray[0];
		
		if(currentSize>1){
			heapArray[0] = heapArray[currentSize-1];
			maxHeapify(0);
		}
		currentSize--;
		return root;
	}
	
	
	public void maxHeapify(int i){
		int l = 2*i+1;
		int r = 2*i+2;
		
		int largest = i;
		
		if(l < currentSize && heapArray[i] < heapArray[l] )
		      largest = l;
		
		if(r < currentSize && heapArray[i] < heapArray[r] )
		      largest = r;
		
		if(largest != i){
			int t = heapArray[i];
			heapArray[i] =heapArray[largest];
			heapArray[largest] = t;
			maxHeapify(largest);
		}
		
	}

Sort the Integer array and get the third largest interger

Sort the Integer array and get the third largest integer

do bubble sort for 3 times. o(n) as 3 is constant.

Since the number is 3rd largest, you need to take 3 variables and set the values of max1,max2,max3 from the a[0],a[1] and a[2] elements using basic if-then compares. Now keep traversing the array till you reach the end. Every time you get a number larger than the largest i.e. max1 store it in max1 and ripple the values to max2 and max3.

What V has suggested would also work, but you traverse 3 times, here you traverse only once. The time-complexity of the algo remains the same at O(n).

For the generic kth largest element, you can use the QuickSelect or the median of median algorithm.

I have tried following code with basic if/else.

static void findThirdLargest(int[] array){
int max1,max2,max3;
max1=max2=max3=0;
for(int i=0;i<array.length;i++){
//Single assignment is possible
if(array[i]>max1){
max2=max1;
max3=max2;
max1=array[i];
continue;
}
if(array[i]>max2 && array[i]<max1){
max3=max2;
max2=array[i];
continue;
}
if(array[i]>max3 && array[i]<max2){
max3=array[i];
continue;
}
}
System.out.println(" Max1 -> "+max1+" Max2 -> "+max2+" Max3 -> "+max3);
}

Why can't we just scan the complete array 3 times to find the 3rd largest number??