Series: Subject: Topic:
Question: 6 of 51

# Linked List Kth largest Element

How to find the kth largest element in a linked list? Can you do this without using extra memory and also without modifying (sorting) the list?
Asked by: vmythilee | Member Since Jul-2010 | Asked on: Aug 31st, 2010

View all questions by vmythilee

sai krishna b

Answered On : Sep 16th, 2010

View all answers by sai krishna b

Consider a pointer pointing to first element and keep comparing with next element,
Which ever is highest put it in next node, keep moving the pointer, final element will be the the highest.

1 User has rated as useful.

djsingh

Answered On : Oct 27th, 2010

Traverse the complete linked list K times first time find the maximum value and subsequent times find the next largest value.

In case the values are duplicate we can increment the loop counter by 1 every time we find a duplicate value of a new found nth max value.

Abhis3k

Answered On : Mar 2nd, 2011

int i,j,k,cnt=0;
input k
while (itr1!=null)
{
while (itr2!=null)
{
if(itr1.info>itr2.info && itr1!=itr2)
{
cnt++;
}
}
if(cnt==N-k)
{
print itr1->info;
break;
}
cnt=0;
}

Sumit Khedkar

Answered On : May 27th, 2011

View all answers by Sumit Khedkar

1. We need to traverse the list K times.

2. Take 3 pointers p1, p2 , p3.Set p1 to it

3. In first iteration find the largest element and set p1 to that element.Set p1 to it

4. In second iteration exclude the node pointed by p1 hance u will get the 2nd largest element. Set p2 to the second largest element.

5. In third iteration make use of pointer p1 exclude the elements which are greater than the element currently pointing by p2.hence u will get the 3rd largest element. Set p1 to it

6. Repeat step 5 and make alternate use of p1 p2 till the final answer.

7. P3 will be needed for comparison and iteration.

Amit Jain

Answered On : Jun 9th, 2011

View all answers by Amit Jain

If the question assumes that the extra memory used should not be a function of x, then one possible solution can be the use of heap to make min-queue. After k elements have been entered , compare the next entry with the minimum of the queue. If its larger, extract-min and insert the new number.

After the whole list is complete, sort the heap to find the maximum.

batman

Answered On : Oct 4th, 2011

Solution 1.
Assuming int & no duplicates & rather small [min,max] interval: Iterate through the list once to find the min&max. Make a binary search on the interval [min, max] to find out the V value for which there are exactly k higher values in the list(complexity log(max-min)*n). Find the Find the maximum value in the queue smaller than V and you have your answer.

You can of course make adjustments for other data types & duplicates & whatever.

Solution 2.
General double numbers
Use n0-n9 to store the number of values that start with 0-9. Find out with what number our Kth value starts, find out the new K for those numbers only. Repeat the procedure for the new numbers(they can still remain in the same list, you will just have to check their start) until you have the entire number in the 'starting with' value.

Complexity (nr of digits in the longest number - including what is after the coma) * n, extra memory 10 variables.