Constraints
Before we look into the different approaches to solve this problem, let's discuss the constraints that our solution should follow :
1. The array should contain at least two elements. If the array has only one element, there is no second largest element.
2. The array may contain duplicate elements. In such cases, we consider the second occurrence of the largest element as the second largest element.
3. The array may contain elements in any order, so we cannot assume that the elements are sorted.
4. The solution should have a time complexity better than O(n^2), where n is the number of elements in the array. This means we should avoid nested loops that compare each element with every other element.
5. The solution should be space-efficient, using only a constant amount of extra space.
Approach 1 (Simple Solution)
The simple solution is to iterate through the array twice. In the first iteration, we find the largest element. In the second iteration, we find the largest element that is smaller than the element found in the first iteration.
Let’s see the step-by-step algorithm:
1. Initialize a variable `largest` to store the index of the largest element and set it to 0.
2. Iterate through the array from index 1 to n-1 and update `largest` if the current element is greater than the element at index `largest`.
3. Initialize another variable `secondLargest` to store the index of the second largest element and set it to -1.
4. Iterate through the array again from index 0 to n-1 and update `secondLargest` if the current element is smaller than the element at index `largest` and greater than the element at index
`secondLargest`.
5. Return the element at index `secondLargest`.
Implementation
C++
#include <iostream>
using namespace std;
int findSecondLargest(int arr[], int n) {
int largest = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[largest])
largest = i;
}
int secondLargest = -1;
for (int i = 0; i < n; i++) {
if (arr[i] != arr[largest]) {
if (secondLargest == -1 || arr[i] > arr[secondLargest])
secondLargest = i;
}
}
if (secondLargest == -1)
return -1; // No second largest element
return arr[secondLargest];
}
int main() {
int arr[] = {10, 5, 8, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int secondLargest = findSecondLargest(arr, n);
if (secondLargest == -1)
cout << "No second largest element" << endl;
else
cout << "Second largest element: " << secondLargest << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Java
public class SecondLargest {
public static int findSecondLargest(int[] arr) {
int n = arr.length;
int largest = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[largest])
largest = i;
}
int secondLargest = -1;
for (int i = 0; i < n; i++) {
if (arr[i] != arr[largest]) {
if (secondLargest == -1 || arr[i] > arr[secondLargest])
secondLargest = i;
}
}
if (secondLargest == -1)
return -1; // No second largest element
return arr[secondLargest];
}
public static void main(String[] args) {
int[] arr = {10, 5, 8, 20, 15};
int secondLargest = findSecondLargest(arr);
if (secondLargest == -1)
System.out.println("No second largest element");
else
System.out.println("Second largest element: " + secondLargest);
}
}
You can also try this code with Online Java Compiler
Python
def findSecondLargest(arr):
n = len(arr)
largest = 0
for i in range(1, n):
if arr[i] > arr[largest]:
largest = i
secondLargest = -1
for i in range(n):
if arr[i] != arr[largest]:
if secondLargest == -1 or arr[i] > arr[secondLargest]:
secondLargest = i
if secondLargest == -1:
return -1 # No second largest element
return arr[secondLargest]
arr = [10, 5, 8, 20, 15]
secondLargest = findSecondLargest(arr)
if secondLargest == -1:
print("No second largest element")
else:
print("Second largest element:", secondLargest)
You can also try this code with Online Python Compiler
Output
Second largest element: 15
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) as we are using only a constant amount of extra space.
Approach 2 (Better Solution)
In the previous approach, we iterate through the array twice, which can be optimized. We can find the second largest element in a single traversal of the array.
Let’s look at the step-by-step algorithm:
1. Initialize two variables, `largest` and `secondLargest`, to store the largest and second largest elements. Set `largest` to the first element (arr[0]) and `secondLargest` to a small value, like INT_MIN.
2. Iterate through the array starting from index 1:
- If the current element is greater than `largest`, update `secondLargest` to `largest` and `largest` to the current element.
- If the current element is greater than `secondLargest` and not equal to `largest`, update `secondLargest` to the current element.
3. Return `secondLargest`.
C++
#include <iostream>
#include <climits>
using namespace std;
int findSecondLargest(int arr[], int n) {
int largest = arr[0];
int secondLargest = INT_MIN;
for (int i = 1; i < n; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
}
else if (arr[i] > secondLargest && arr[i] != largest) {
secondLargest = arr[i];
}
}
if (secondLargest == INT_MIN)
return -1; // No second largest element
return secondLargest;
}
int main() {
int arr[] = {10, 5, 8, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int secondLargest = findSecondLargest(arr, n);
if (secondLargest == -1)
cout << "No second largest element" << endl;
else
cout << "Second largest element: " << secondLargest << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Java
public class SecondLargest {
public static int findSecondLargest(int[] arr) {
int n = arr.length;
int largest = arr[0];
int secondLargest = Integer.MIN_VALUE;
for (int i = 1; i < n; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
} else if (arr[i] > secondLargest && arr[i] != largest) {
secondLargest = arr[i];
}
}
if (secondLargest == Integer.MIN_VALUE)
return -1; // No second largest element
return secondLargest;
}
public static void main(String[] args) {
int[] arr = {10, 5, 8, 20, 15};
int secondLargest = findSecondLargest(arr);
if (secondLargest == -1)
System.out.println("No second largest element");
else
System.out.println("Second largest element: " + secondLargest);
}
}
You can also try this code with Online Java Compiler
Python
def findSecondLargest(arr):
n = len(arr)
largest = arr[0]
secondLargest = float('-inf')
for i in range(1, n):
if arr[i] > largest:
secondLargest = largest
largest = arr[i]
elif arr[i] > secondLargest and arr[i] != largest:
secondLargest = arr[i]
if secondLargest == float('-inf'):
return -1 # No second largest element
return secondLargest
arr = [10, 5, 8, 20, 15]
secondLargest = findSecondLargest(arr)
if secondLargest == -1:
print("No second largest element")
else:
print("Second largest element:", secondLargest)
You can also try this code with Online Python Compiler
Output
Second largest element: 15
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) as we are using only a constant amount of extra space.
Note: This approach is more efficient than the previous one as it finds the second largest element in a single traversal of the array.
Approach 3 (Efficient Solution)
The previous approach works well, but we can further optimize it by reducing the number of comparisons. Instead of updating `secondLargest` every time we find an element greater than it, we can update it only when necessary.
Let’s see the optimized algorithm:
1. Initialize two variables, `largest` and `secondLargest`, to the first two elements of the array.
2. If the first element is greater than the second element, swap them.
3. Iterate through the array starting from index 2:
- If the current element is greater than `largest`, update `secondLargest` to `largest` and `largest` to the current element.
- If the current element is greater than `secondLargest` and not equal to `largest`, update `secondLargest` to the current element.
4. Return `secondLargest`.
C++
#include <iostream>
using namespace std;
int findSecondLargest(int arr[], int n) {
if (n < 2)
return -1; // No second largest element
int largest = arr[0];
int secondLargest = arr[1];
if (largest < secondLargest)
swap(largest, secondLargest);
for (int i = 2; i < n; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
}
else if (arr[i] > secondLargest && arr[i] != largest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
int main() {
int arr[] = {10, 5, 8, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int secondLargest = findSecondLargest(arr, n);
if (secondLargest == -1)
cout << "No second largest element" << endl;
else
cout << "Second largest element: " << secondLargest << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Java
public class SecondLargest {
public static int findSecondLargest(int[] arr) {
int n = arr.length;
if (n < 2)
return -1; // No second largest element
int largest = arr[0];
int secondLargest = arr[1];
if (largest < secondLargest)
swap(arr, 0, 1);
for (int i = 2; i < n; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
} else if (arr[i] > secondLargest && arr[i] != largest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {10, 5, 8, 20, 15};
int secondLargest = findSecondLargest(arr);
if (secondLargest == -1)
System.out.println("No second largest element");
else
System.out.println("Second largest element: " + secondLargest);
}
}
You can also try this code with Online Java Compiler
Python
def findSecondLargest(arr):
n = len(arr)
if n < 2:
return -1 # No second largest element
largest = arr[0]
secondLargest = arr[1]
if largest < secondLargest:
largest, secondLargest = secondLargest, largest
for i in range(2, n):
if arr[i] > largest:
secondLargest = largest
largest = arr[i]
elif arr[i] > secondLargest and arr[i] != largest:
secondLargest = arr[i]
return secondLargest
arr = [10, 5, 8, 20, 15]
secondLargest = findSecondLargest(arr)
if secondLargest == -1:
print("No second largest element")
else:
print("Second largest element:", secondLargest)
You can also try this code with Online Python Compiler
Output
Second largest element: 15
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) as we are using only a constant amount of extra space.
Note: This approach is the most efficient among the three as it minimizes the number of comparisons and finds the second largest element in a single traversal of the array.
Frequently Asked Questions
What if the array contains duplicate elements?
If the array contains duplicate elements, we consider the second occurrence of the largest element as the second largest element. For example, in the array [5, 2, 8, 8, 1], the second largest element would be 8.
Can we solve this problem using sorting?
Yes, we can solve this problem by sorting the array in descending order and returning the second element. However, sorting the array would take O(n log n) time complexity, which is less efficient compared to the linear time complexity of the efficient approach discussed above.
What if the array has less than two elements?
If the array has less than two elements, there is no second largest element. In such cases, we can return a special value, like -1, to indicate that there is no second largest element in the array.
Conclusion
In this article, we learned how to find the second largest element in an array efficiently. We discussed three different approaches. We started from a simple solution and progressed to an efficient solution. The efficient approach finds the second largest element in a single traversal of the array, which minimizes the number of comparisons.
You can also check out our other blogs on Code360.
19+ registered 
