Given an array of integers and the task is to write a program that efficiently finds the second-largest element present in the array.
Example:
Input: arr[] = {13, 14, 15, 16, 17, 18}
Output: The second largest element is 17.
Explanation: The largest element of the array
is 35 and the second largest element is 17
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
Simple Solution:
Approach: The idea is to sort the array in descending order and then return the second element which is not equal to the largest element from the sorted array.
PHP
<?phpfunction bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // traverse the array from 0 to // n-i-1. Swap if the element // found is greater than the // next element if ($arr[$j] <$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $swapped = True; } } // IF no two elements were swapped // by inner loop, then break if ($swapped == False) break; }} // Driver code to test above$arr = array(64, 34, 25, 12, 22, 11, 90);$len = sizeof($arr);bubbleSort($arr);if($arr[0] == $arr[1]) { echo "No element";}else { echo "Second Largest element is ".$arr[1];} ?> |
Second Largest element is 64
Complexity Analysis:
Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space: O(1)Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.
Sorting In Place: Yes
Stable: Yes
Another Approach: Find the second largest element in a single traversal.
Below is the complete algorithm for doing this:
1) Initialize the first as 0 (i.e, index of arr[0] element)
2) Start traversing the array from array[1],
a) If the current element in array say arr[i] is greater
than first. Then update first and second as,
second = first
first = arr[i]
b) If the current element is in between first and second,
then update second to store the value of current variable as
second = arr[i]
3) Return the value stored in second.
PHP
<?php // PHP program to find second largest// element in an array// Function to print the// second largest elementsfunction print2largest($arr, $arr_size) { // There should be atleast // two elements if ($arr_size < 2) { echo(" Invalid Input "); return; } $first = $second = PHP_INT_MIN; for ($i = 0; $i < $arr_size ; $i++) { // If current element is // smaller than first // then update both // first and second if ($arr[$i] > $first) { $second = $first; $first = $arr[$i]; } // If arr[i] is in // between first and // second then update // second else if ($arr[$i] > $second && $arr[$i] != $first) $second = $arr[$i]; } if ($second == PHP_INT_MIN) echo("There is no second largest element\n"); else echo("The second largest element is " . $second . "\n");}// Driver Code$arr = array(12, 35, 1, 10, 34, 1);$n = sizeof($arr);print2largest($arr, $n);?> |
Output:
The second largest element is 34
Another Approach: Sort the array in descending order using the PHP rsort() method and then return the second element from the sorted array. Here, we have declared a returnSecondHighest() method that accepts an array. By implementing the rsort() method in PHP that will sort the array in descending order. Now, store the second-highest element of the sorted array by using the 1st index of the array in a variable. Here, we declare the user-defined array of numbers & call the returnSecondHighest() method and print the second-highest element of the array.
PHP Code:
PHP
<?php function returnSecondHighest(array $myarray){ // Sort the array in descending order rsort($myarray); // Save the element from the second last position of sorted array $secondHighest = $myarray[1]; // Return second highest number return $secondHighest; } // Driver code to test above $arr = array(64, 34, 25, 12, 22, 11, 90); // Call the function and print output echo "Second highest number : ".returnSecondHighest($arr);?> |
Output: The time complexity of this program is O(nlogn) as the PHP rsort() method takes O(nlogn) where n is the number of elements in the array parameter.
Second highest number : 64
