In this article, we are going to learn how can we find the second-largest element in an array. If the array length is 1 there will be no second-largest element so the array must have more than 1 element.
Examples:
Input: arr[] = {12, 35, 1, 10, 34, 1}
Output: The second largest element is 34.
Explanation: The largest element of the array is 35 and the second largest element is 34
Input: arr[] = {10, 5, 10}
Output: The second largest element is 5. Explanation: The largest element of the array is 10
and the second largest element is 5
Input: arr[] = {10, 10, 10}
Output: The second largest does not exist.
Explanation: Largest element of the array is 10 there is no second largest element
There are a few approaches using which we can find the second largest element in an array:
- Using sorting
- Using Set
- Using iteration
Using Sorting
Sort the array in ascending order and iterate through the sorted array from the end to find the first element different from the largest element, which is considered the second largest. If no such element is found, it indicates that there is no second-largest element.
Example:
Javascript
function findSecondLargest(arr) { let first, second; // There should be at least two elements if (arr.length < 2) { return "Invalid Input"; } // Sort the array in ascending order arr.sort(); // Start from the second last element as // the largest element is at last for (let i = arr.length - 2; i >= 0; i--) { // If the element is not equal to the // largest element if (arr[i] !== arr[arr.length - 1]) { return "The second largest element is " + arr[i]; } } return "There is no second largest element"; } // Driver program to test the function const arr = [12, 35, 10, 35, 10, 34, 1]; // Output: The second largest element is 34 console.log(findSecondLargest(arr)); |
The second largest element is 34
Time Complexity: O(n log n).
Auxiliary space: O(1).
Using Set
Create a Set to store unique elements from the input array, ensuring that duplicates are eliminated. Check if there are at least two unique elements in the Set. If not, it returns a message indicating that no second largest element exists.
Finally, it convert the Set back to an array, sort it in ascending order, and return the second-last element as the second largest element.
Example:
Javascript
function findSecondLargestUsingSet(arr) { // Create a Set to store unique elements const uniqueElements = new Set(arr); // Check if there are at least two unique elements if (uniqueElements.size < 2) { return "No second largest element exists"; } // Convert the Set back to an array and sort it const sortedUnique = Array.from(uniqueElements) .sort((a, b) => a - b); // Return the second-to-last element return "The second largest element is " + sortedUnique[sortedUnique.length - 2]; } // Example usage: const numbers = [12, 35, 35, 2, 10, 10, 34, 12]; const number = [10, 10, 10]; // Output: The second largest element is 34 console.log(findSecondLargestUsingSet(numbers)); console.log(findSecondLargestUsingSet(number)); |
The second largest element is 34 No second largest element exists
Time Complexity: O(n log n).
Auxiliary space: O(n) for set data structure.
Using Iteration
- Initialize two variables, firstMax and secondMax, to negative infinity to ensure they are initially smaller than any possible array element.
- Iterate through the input array, arr, and compare each element with firstMax. If an element is greater than firstMax, update secondMax to firstMax and firstMax to the current element.
- Also, check that the current element is not equal to firstMax to handle cases with duplicate elements.
- If secondMax remains as negative infinity after the iteration, it means there is no distinct second largest element.
- Else, return the value of secondMax as the second largest element found in the array.
Example:
Javascript
function findSecondLargestUsingIteration(arr) { let firstMax = -Infinity; let secondMax = -Infinity; for (let num of arr) { if (num > firstMax) { secondMax = firstMax; firstMax = num; } else if (num > secondMax && num !== firstMax) { secondMax = num; } } if (secondMax === -Infinity) { return "No second largest element exists"; } return "The second largest element is " + secondMax; } // Example usage: const numbers = [12, 35 ,35 , 2, 10, 10, 34, 12]; const number = [10, 10 , 10]; // Output: The second largest element is 34 console.log(findSecondLargestUsingIteration(numbers)); console.log(findSecondLargestUsingIteration(number)); |
The second largest element is 34 No second largest element exists
Time Complexity: O(n).
Auxiliary space: O(1).
