In this tutorial, we will learn how to find the second largest element in an array using JavaScript.
Given an array of integers, our task is to write an efficient JavaScript program that finds the second largest element in the given array.
For example:
Input: [12, 11, 5, 19, 26, 2, 13]
Output: The second largest element is 19
Input: [12, 11, 12]
Output: The second largest element is 11
Input: [13, 13, 13]
Output: The second largest element doesn't exist
There can be several approaches to solve this problem. However, we will discuss only the most efficient and commonly used ones.
Approach 1:
In this approach, we will traverse the whole array using a for
loop and keep track of the largest and the second largest element at each iteration.
We will use the below algorithm:
- Create two variables
largest
andsecondLargest
and initialize them with the minimum possible value i.e-Infinity
. - Start traversing the array from the very first element:
- Check if the current element is greater than the value stored in the
largest
variable. If yes, copy the value oflargest
intosecondLargest
and update thelargest
to current element i.e. secondLargest = largest and largest = currentElement. - If the current element is greater than the value stored in
secondLargest
and less than thelargest
, update the value of thesecondLargest
to current element.
- Check if the current element is greater than the value stored in the
- If
secondLargest
is not equal to-Infinity
, it means the second largest exists in the array. Print its value.
Below is the implementation of the above algorithm:
// Find second largest element in an array const numbers = [12, 11, 5, 19, 26, 2, 13]; let largest = -Infinity, secondLargest = -Infinity; for(let i=0; i<numbers.length;i++){ if(numbers[i]>largest){ secondLargest = largest; largest = numbers[i]; } else if(numbers[i]<largest && numbers[i]>secondLargest){ secondLargest = numbers[i]; } } if(secondLargest!==-Infinity){ console.log(`Second largest element is ${secondLargest}`); } else{ console.log("Second largest element doesn't exist."); }
Output:
Second largest element is 19
The time complexity of the above program is O(n).
Approach 2 –
The basic idea of this approach is to sort the array in ascending order. This will put the largest element at the end of the array.
But, the second largest element can either be at the second last position(if it is not equal to the last element) or somewhere before the second last element if the array contains duplicates.
For example:
Input: [12, 11, 5, 19, 26, 2, 13]
Sorted: [2, 5, 11, 12, 13, 19, 26]
Output: Second largest element is 19(second last element)
Input: [12, 26, 5, 19, 26, 2, 13]
Sorted: [2, 5, 12, 13, 19, 26, 26]
Output: Second largest element is 19(third last element)
So, after sorting, we have to basically find that element from the end of the array which is not equal to the last element(largest) of the array.
If no such element exists, it means the array does not have the second largest.
Below is the implementation of the above algorithm:
// Find second largest element in an array const numbers = [12, 11, 5, 19, 26, 2, 13]; // Sort the array in ascending order numbers.sort((x,y)=>x-y); let secondLargest = -Infinity; for(let i=numbers.length-2; i>=0;i--){ // If the current element is not equal // to the last(largest) element if(numbers[i]!==numbers[numbers.length-1]){ secondLargest = numbers[i]; break; } } if(secondLargest!==-Infinity){ console.log(`Second largest element is ${secondLargest}`); } else{ console.log("Second largest element doesn't exist."); }
Output:
Second largest element is 19
The time complexity of the above algorithm will be same as the sort()
method’s time complexity which is O(nlogn).
Thanks for reading.