Find second largest element in an array using recursion

Question

As the title says, is there any efficient way to find the second largest element in an array using recursion?

• nano_nano: show us your code and we tell you if it is efficient
• Henry: Do you have to use recursion? It's rather easy to do without.
• sr01853: Efficiency and recursion are two different directions.
• Reinstate Monica -- notmaynard: Assuming it's unsorted, the simplest way would be to run through the array once, find the largest element, then run through again to find the largest element less than the largest. You could use recursion; it would recurse twice.
• Luchian Grigore: @iamnotmaynard why pass twice if you can pass once?

Answer 1

partition based Selection algorithm is recursive by nature, and it lets you select the k'th element in the array, so using it - you can actually find the answer for any k, including k = n-1 (your case).

This is done in O(n) on average with fairly low constants.

Answer 2

If nothing is known about the array, you can't do better than O(n), whether it's recursive or iterative.

Just pass throught the array recursively, while passing the two largest elements and replacing them if you find larger values.

find_largest(array_begin, largest, secondLargest)
 if (array_begin = NULL)
 return secondLargest
 if (array_begin.value > largest)
 secondLargest = largest
 largest = array_begin.value
 return find_largest(array_begin+1, largest, secondLargest)

largest and secondLargest can initially be set to the minimum you expect to find in the array.

You're right, sorting (at least full sorting) is overkill.

• Neel: How can I set the minimum if nothing about the array is known? Do you mean the first elem?
• Luchian Grigore: @Neel no additional info I mean - i.e. if you know that the array is sorted, you can do it in O(1).

Answer 3

Something in O(n) like this:

int findSecondLargest(int[] arr, int index, int largest, int secondLargest) {
 if(index == arr.length) {
 return secondLargest;
 }
 int element = arr[index];
 if(element > secondLargest) {
 if(element > largest) {
 return findSecondLargest(arr, index + 1, element, largest);
 } else {
 return findSecondLargest(arr, index + 1, largest, element);
 }
 }
 return findSecondLargest(arr, index + 1, largest, secondLargest);
}

Answer 4

 public void recurs(int[] data, int ind, int max1, int max2){
 if(ind<data.length){
 if(data[ind]>max1){
 int temp = max1;
 max1 = data[ind];
 max2 = temp;
 } else if(data[ind]>max2){
 max2 = data[ind];
 }
 recurs(data, ind+1, max1, max2);
 } else {
 return max2;
 }
 return -1;
 }

to call it : recurs(dataX, 0, Integer.MIN_VALUE, Integer.MIN_VALUE);

Answer 5

Instinctively, you can scan the array and do comparison on every value twice. Anyway, you need O(n) to solve the problem. It's fast enough.

Try to avoid recursive when it is not necessary because it is not free.

Answer 6

If you do it by recursion then at most you have to do 3(n)/2-2 comparisons but for a better solution, think this problem as a binary tree with n numbers of nodes. Then there will be n-1 comparison for finding largest and log(n)-1 comparison for second largest. But some argue that it needs n + log(n) comparison.

Answer 7

function findTwoLargestNumber(n,startIndex,largestNumber,secondLargestNumber){ 
 if(startIndex==arrlengths-1){
 return [largestNumber,secondLargestNumber];
 }
 
 if(largestNumber<n[startIndex+1]){
 secondLargestNumber=largestNumber;
 largestNumber=n[startIndex+1];
 }
 return findTwoLargestNumber(n,startIndex+1 ,largestNumber,secondLargestNumber) 
}

• Community: As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.