Second Largest Element in an Array
We will write a program to find the second largest element in an array
Srivastava Bodakunti
0
54
Given an array of size n, we need to find the index of the second largest element in the array.
IP: arr[] = {10, 5, 8, 20}
OP: 0 // index of 10
IP: arr[] = {20, 10, 20, 8, 12}
OP: 4 // index of 12
IP: arr[] = {10, 10, 10}
OP: -1 // No second largestNaive Approach
- Find the index of largest element
- Traverse the array again to find the second largest where the value is not equal to largest element
int getLargest(int[] arr) {
int maxIdx = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > arr[maxIdx]) {
maxIdx = i;
}
}
return maxIdx;
}
int secondLargest(int[] arr) {
int largest = getLargest(arr);
int secondLargest = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != arr[largest]) {
if (secondLargest == -1) {
secondLargest = i;
} else if (arr[i] > arr[secondLargest]) {
secondLargest = i;
}
}
}
return secondLargest;
}Time Complexity is O(n), as we are traversing the array twice.
Efficient Approach
We will maintain largest and second largest element index in one traversal, let's see how.
array elements => a[0], a[1], a[2],...a[i-1], a[i]
a[i] > a[largest]: secondLargest = largest, largest = i
a[i] == a[largest]: ignore
a[i] < a[largest]
-> secondLargest == -1: secondLargest = i
-> a[i] <= a[secondLargest] = ignore
-> a[i] > a[secondLargest]: secondLargest = iint secondLargest(int[] arr) {
int secondLargest = -1, largest = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = i;
} else if (arr[i] != arr[largest]) {
if (secondLargest == -1 || arr[i] > arr[secondLargest]) {
secondLargest = i;
}
}
}
return secondLargest;
}Time Complexity: Θ(n), Space Complexity: Θ(1)
