You are given an array of numbers (integers) and the task is to find second largest number in array.
Takeaways
The most efficient approach to find second largest number in array uses only one loop.
Find Second Largest Element in an Array
Refer to the Example and Explanationsections for more details about how to find second largest number in array and the Approach section to understand the explanation of how to find second largest number in array.
Example
Let us look at some of the examples provided to find second largest element in array.
Example 1: Given input array is {12, 35, 1, 10, 34, 1} Output: The second largest element in array is 34.
Example 2: Given input array is {10, 5, 10} Output: The second largest element in array is 5.
Example 3: Given input array is {10, 10, 10} Output: N/A. (No second largest element is present in the given array, so we cannot find second largest number in array.)
Example Explanation
Before getting into the explanation of how to find second largest element in array, let us first get a brief introduction about the arrays.
An array is a linear collection of values stored at contiguous memory locations. Array stores homogeneous values(similar data type values).
Some of the important points to keep in mind regarding arrays are as follows:
- The arrays occupy continuous (contiguous) space in the memory.
- The indexing of the array starts with 0 and goes on to (length of array – 1).
- Arrays are of fixed length, i.e. after the creation of an array, we cannot change the size of the array.
- The access of elements is very fast in arrays. We can easily access any element using the index of the array.
Example: The array os 56, 50, 34, 24, 12 will look like:
To learn more about the arrays, refer to the article – Arrays in Data Structure.
Note: A list is used to store one or more objects or data elements. Lists are used in python and java mostly. We can say that lists are similar to arrays.
Constraints
- The first input is the number of elements present in the array i.e. n.
- The second input is the sequential set of elements of the array.
In some problems, you may find the number of test cases represented by t. So, we only need to call the reverse function t-times.
The problem is to find second largest element in array.
Approach 1 (Simple Solution)
Let us learn the simple or brute force approach to find second largest element in array. One of the most simple solutions can be sorting the array in ascending order and then finding the second element which is not equal to the largest element from the sorted array. So, in this way, we can find second largest element in array.
Pseudo code can be:
1. Sort the array in ascending order.
2. Find the second element which is not equal to the largest element from the sorted array.
C++ :
#include <bits/stdc++.h>
using namespace std;
int findSecondLargest(int a[], int n)
{
/*
First, sort the array and find the first_largest element present in the array (at the last position).
*/
sort(a, a + n);
/*
Now for the second_largest element, we need to start from second last element as the largest element is at last.
*/
int second_largest = 0;
for (int i = n - 2; i >= 0; i--)
{
/*
If the last and second last element are equal then check the previous one else return the second last element.
*/
if (a[i] != a[n - 1])
{
second_largest = a[i];
break;
}
}
return second_largest;
}
int main()
{
int a[] = {12, 35, 1, 10, 34, 1};
int n = sizeof(a) / sizeof(a[0]);
int answer = findSecondLargest(a, n);
cout << "The second largest element in the array is: " << answer;
return 0;
}
Java:
import java.util.*;
public class FindSecondLargest {
static int findSecondLargest(int a[], int n) {
/*
First, sort the array and find the first_largest element present in the array (at the last position).
*/
Arrays.sort(a);
/*
Now for the second_largest element, we need to start from second last element as the largest element is at last.
*/
int second_largest = 0;
for (int i = n - 2; i >= 0; i--)
{
/*
If the last and second last element are equal then check the previous one else return the second last element.
*/
if (a[i] != a[n - 1])
{
second_largest = a[i];
break;
}
}
return second_largest;
}
public static void main(String[] args) {
int a[] = { 12, 35, 1, 10, 34, 1 };
int n = a.length;
int answer = findSecondLargest(a, n);
System.out.println("The second largest element in the array is: " + answer);
}
}
JavaScript:
function findSecondLargest(a, n) {
/*
First, sort the array and find the first_largest element present in the array (at the last position).
*/
a.sort();
/*
Now for the second_largest element, we need to start from second last element as the largest element is at last.
*/
let second_largest = 0;
/*
If the last and second last element are equal then check the previous one else return the second last element.
*/
for (let i = n - 2; i >= 0; i--) {
if (a[i] != a[n - 1]) {
second_largest = a[i];
break;
}
}
return second_largest;
}
const a = [12, 35, 1, 10, 34, 1];
let n = a.length;
let answer = findSecondLargest(a, n);
console.log("The second largest element in the array is: " + answer);
Python:
def find_second_largest(a, n):
"""
First, sort the array and find the first_largest element present in the array (at the last position).
"""
a.sort()
"""
Now for the second_largest element, we need to start from second last element as the largest element is at last.
"""
second_largest = 0
for i in range(n-2, -1, -1):
"""
If the last and second last element are equal then check the previous one else return the second last element.
"""
if a[i] != a[n - 1]:
second_largest = a[i]
break
return second_largest
if __name__ == '__main__':
a = [12, 35, 1, 10, 34, 1]
n = len(a)
answer = find_second_largest(a, n)
print("The second largest element in the array is: ", answer)
Output:
The second largest element in the array is: 34
Complexity Analysis
In this simple approach to find second largest element in array, we are first sorting the array which takes O(log n) time. Apart from that, we are not using any extra space rather than one variable namely second_largest to store and return the answer.
Time Complexity
The time complexity of this above approach to find second largest number in array is O(n log(n)), where n is the number of elements present in the array.
Space Complexity
The space complexity of the above approach is O(1).
Approach 2 (Better Solution)
Let us learn a better yet simple approach to find second largest element in array. One of the most basic or simple solutions can be running two loops. The first loop will find the first largest element in the array (let’s say first_largest is the largest element present in the array). After that, the second loop will find the largest element present in the array which is smaller than first_largest. So, in this way, we can find second largest element in array.
Pseudo code can be:
1. Find the largest element in the array and store its value (let's say first_largest).
2. Find the largest element in the array which is smaller than first_largest and return the value found.
C++:
#include <bits/stdc++.h>
using namespace std;
int findSecondLargest(int a[], int n)
{
/*
Let us assume that initially, the largest element (first_largest) present in the array is INT_MIN.
*/
int first_largest = INT_MIN;
/*
The first loop will find the first_largest element present in the array.
*/
for (int i = 0; i < n; i++)
{
/*
Update the value of first_largest if the current element is larger than the first_largest value till now.
*/
if (first_largest < a[i])
{
first_largest = a[i];
}
}
/*
Now find the largest element present in the array which is smaller than the first_largest.
Initially, the second element present in the array is INT_MIN.
*/
int second_largest = INT_MIN;
for (int i = 0; i < n; i++)
{
if (a[i] > second_largest and a[i] < first_largest)
{
second_largest = a[i];
}
}
return second_largest;
}
int main()
{
int a[] = {12, 35, 1, 10, 34, 1};
int n = sizeof(a) / sizeof(a[0]);
int answer = findSecondLargest(a, n);
cout << "The second largest element in the array is: " << answer;
return 0;
}
Java:
public class FindSecondLargest {
static int findSecondLargest(int a[], int n) {
/*
Let us assume that initially, the largest element (first_largest) present in the array is Integer.MIN_VALUE.
*/
int first_largest = Integer.MIN_VALUE;
/*
The first loop will find the first_largest element present in the array.
*/
for (int i = 0; i < n; i++)
{
/*
Update the value of first_largest if the current element is larger than the first_largest value till now.
*/
if (first_largest < a[i])
{
first_largest = a[i];
}
}
/*
Now find the largest element present in the array which is smaller than the first_largest.
Initially, the second element present in the array is Integer.MIN_VALUE.
*/
int second_largest = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
if (a[i] > second_largest && a[i] < first_largest)
{
second_largest = a[i];
}
}
return second_largest;
}
public static void main(String[] args) {
int a[] = { 12, 35, 1, 10, 34, 1 };
int n = a.length;
int answer = findSecondLargest(a, n);
System.out.println("The second largest element in the array is: " + answer);
}
}
JavaScript:
function findSecondLargest(a, n) {
/*
Let us assume that initially, the largest element (first_largest) present in the array is Number.MIN_SAFE_INTEGER.
*/
let first_largest = Number.MIN_SAFE_INTEGER;
/*
The first loop will find the first_largest element present in the array.
*/
for (let i = 0; i < n; i++) {
/*
Update the value of first_largest if the current element is larger than the first_largest value till now.
*/
if (first_largest < a[i]) {
first_largest = a[i];
}
}
/*
Now find the largest element present in the array which is smaller than the first_largest.
Initially, the second element present in the array is Number.MIN_SAFE_INTEGER.
*/
let second_largest = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
if (a[i] > second_largest && a[i] < first_largest) {
second_largest = a[i];
}
}
return second_largest;
}
const a = [12, 35, 1, 10, 34, 1];
let n = a.length;
let answer = findSecondLargest(a, n);
console.log("The second largest element in the array is: " + answer);
Python:
def find_second_largest(a, n):
"""
Let us assume that initially, the largest element (first_largest) present in the array(list in case of python) is (-999999).
"""
first_largest = -999999
"""
The first loop will find the first_largest element present in the array.
"""
for i in range(n):
"""
Update the value of first_largest if the current element is larger than the first_largest value till now.
"""
if first_largest < a[i]:
first_largest = a[i]
"""
Now find the largest element present in the array which is smaller than the first_largest.
Initially let the second element present in the array be -999999.
"""
second_largest = -999999
for i in range(n):
if a[i] > second_largest and a[i] < first_largest:
second_largest = a[i]
return second_largest
if __name__ == '__main__':
a = [12, 35, 1, 10, 34, 1]
n = len(a)
answer = find_second_largest(a, n)
print("The second largest element in the array is: ", answer)
Output:
The second largest element in the array is: 34
Complexity Analysis
In this better yet simple approach to find second largest element in array, we are using two loops but one after the other (not a nested loop). Here, we are traversing the array twice. Apart from that, we are not using any extra space rather than two variables namely first_largest and second_largest.
Time Complexity
The time complexity of the above approach to find second largest number in array is O(n), where n is the number of elements present in the array.
Space Complexity
The space complexity of the above approach is O(1).
Approach 3 (Efficient Solution)
Let us now discuss an efficient approach to find second largest element in array. In this approach, we need two variables namely first_largest and second_largest. As the name suggests, the second_largest variable will ultimately store the index of the second largest element.
Initially, set the value of the first_largest variable with 0 and the second_largest variable with the value -1. Now, we will need only one traversal (one loop) to get our answer. In each iteration, we need to check if the current element in the array (i.e. a[i]) is greater than the element at the first_largest index (a[first_largest]) or not. If it is greater, then we need to update the values of second_largest and first_largest. Update the value of second_largest with the value present in first_largest (i.e. second_largest = first_largest) and update the value of first_largest with the index value of the current element (i.e. first_largest = i). (Refer to the pseudo-code and code for better clarity). On the other hand, if the value of the current element is in between first_largest and second_largest, then update second_largest to store the index value of the current element (i.e. second_largest = i). Once the loop is completed, return the element present at the second_largest as result. So, in this way, we can find second largest element in array.
Pseudo code can be:
1. Initialize the first_largest variable with 0 and the second_largest variable with the value -1
2. Start traversing the array and in each iteration check:
i) If the current element in array i.e. a[i] is greater
than the element at the index - first_largest or not. If it is greater then update:
second_largest = first_largest
first_largest = i
ii) If the value of current element is in between first_largest and second_largest, then update :
second_largest = i
3. Return the value stored at the second_largest index as the answer.
C++:
#include <bits/stdc++.h>
using namespace std;
int findSecondLargest(int a[], int n)
{
/*
Initialize the variable first_largest with the value 0 and second_largest with the value -1.
*/
int first_largest = 0;
int second_largest = -1;
/*
Now update the values of first_largest and second_largest in each iteration as per the approach.
*/
for (int i = 0; i < n; i++)
{
if (a[i] > a[first_largest])
{
second_largest = first_largest;
first_largest = i;
}
else if (a[i] < a[first_largest])
{
if (second_largest == -1 || a[second_largest] < a[i])
second_largest = i;
}
}
return a[second_largest];
}
int main()
{
int a[] = {12, 35, 1, 10, 34, 1};
int n = sizeof(a) / sizeof(a[0]);
int answer = findSecondLargest(a, n);
cout << "The second largest element in the array is: " << answer;
return 0;
}
Java:
public class FindSecondLargest {
static int findSecondLargest(int a[], int n) {
/*
Initialize the variable first_largest with the value 0 and second_largest with the value -1.
*/
int first_largest = 0;
int second_largest = -1;
/*
Now update the values of first_largest and second_largest in each iteration as per the approach.
*/
for (int i = 0; i < n; i++) {
if (a[i] > a[first_largest]) {
second_largest = first_largest;
first_largest = i;
} else if (a[i] < a[first_largest]) {
if (second_largest == -1 || a[second_largest] < a[i])
second_largest = i;
}
}
return a[second_largest];
}
public static void main(String[] args) {
int a[] = { 12, 35, 1, 10, 34, 1 };
int n = a.length;
int answer = findSecondLargest(a, n);
System.out.println("The second largest element in the array is: " + answer);
}
}
JavaScript:
function findSecondLargest(a, n) {
/*
Initialize the variable first_largest with the value 0 and second_largest with the value -1.
*/
let first_largest = 0;
let second_largest = -1;
/*
Now update the values of first_largest and second_largest in each iteration as per the approach.
*/
for (let i = 0; i < n; i++) {
if (a[i] > a[first_largest]) {
second_largest = first_largest;
first_largest = i;
} else if (a[i] < a[first_largest]) {
if (second_largest == -1 || a[second_largest] < a[i]) second_largest = i;
}
}
return a[second_largest];
}
const a = [12, 35, 1, 10, 34, 1];
let n = a.length;
let answer = findSecondLargest(a, n);
console.log("The second largest element in the array is: " + answer);
Python:
def find_second_largest(a, n):
"""
Initialize the variable first_largest with the value 0 and second_largest with the value -1.
"""
first_largest = 0
second_largest = -1
"""
Now update the values of first_largest and second_largest in each iteration as per the approach.
"""
for i in range(n):
if a[i] > a[first_largest]:
second_largest = first_largest
first_largest = i
elif a[i] < a[first_largest]:
if second_largest == -1 or a[second_largest] < a[i]:
second_largest = i
return a[second_largest]
if __name__ == '__main__':
a = [12, 35, 1, 10, 34, 1]
n = len(a)
answer = find_second_largest(a, n)
print("The second largest element in the array is: ", answer)
Output:
The second largest element in the array is: 34
Complexity Analysis
In this effective approach to find second largest element in array, we are traversing the array only once. Apart from that, we are not using any extra space rather than two variables namely first_largest and second_largest.
Time Complexity
The time complexity of the above approach to find second largest number in array is O(n), where n is the number of elements present in the array.
Space Complexity
The space complexity of the above approach is O(1).
Conclusion
- An array is a linear collection of values stored at contiguous memory locations. Array stores homogeneous values(similar data type values).
- The brute force approach to find second largest element in array can be sorting the array and then finding the second element which is not equal to the largest element from the sorted array.
- The time complexity of the brute approach is O(n log(n)), where n is the number of elements present in the array. The space complexity is O(1).
- The simple approach to find second largest element in array can be running two loops. The first loop will find the first largest element in the array. After that, the second loop will find the largest element present in the array which is smaller than first_largest.
- The time complexity of the simple approach is O(n), where n is the number of elements present in the array. The space complexity is O(1).
- The efficient approach to find second largest number in array uses only one loop. The two variables first_largest and second_largest will keep on updating their values in each iteration and the result will be finally stored in the second_largest variable.
- The time complexity of the efficient approach is also O(n), where n is the number of elements present in the array. The space complexity is O(1).
