# Second Largest Element in an Array

## We will write a program to find the second largest element in an array 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 largest``````

Naive 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, a, a,...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 = i``````
``````int 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)