Let’s discuss a problem to find the second largest number in an array.
Given an unsorted array of integers, write a code to find the second largest number in an array.
For example –
Input – arr[] = { 4, 1, 5, 2, 8, 0, 3, 55}
Output – 8
The second max element in this array is 8.
Before checking the solution, let’s think for a moment, how do you approach this problem? There are multiple ways to solve this problem. Which approach you prefer and why? At the end of this tutorial, I have shared the link to the video tutorial.
In this tutorial, I am going to cover following topics –
- How to find the second largest number in an array using sorting.
- C program to find the second largest number in an array.
- C++ program to find the second largest number in an array.
Find the Second Largest Number in an Array using Sorting
The simple approach is to sort an array using sorting algorithm. After sorting an array element at n-2 index will be the second largest number.
For sorting an array, we can use following sorting algorithms.
ii) Insertion Sort
iii) Bubble Sort
iv) Merge Sort
v) Quick Sort
Selection sort, Insertion sort, and bubble sort are not suitable for large datasets as their time complexity is O(n2). We can use Merge Sort or Quick Sort for large data sets. The time complexity of merge sort and quick sort is O(nlogn).
NOTE – If the element of an array is repeated then this approach won’t work. Then the best approach is to traverse an array to find the second highest element.
Find Second Highest Number in an Array using Single Loop
The best approach is to visit each element of an array to find the second highest number in array with duplicates. The time complexity of this approach is O(n).
Algorithm :
i) Declare two variables max and second max and initialize them with integer minimum possible value.
ii) Traverse an array and compare each element of an array with the value assigned to max variable. If current element is greater than the value assigned at max variable. Then do two things –
a) In second max variable, assign the value present at max variable.
b) In max variable, assign the current index value.
iii) We have to do one more comparison that if current index value is less than max and greater than the value assigned at second max. Then, assign current index value at second max variable.
After complete iteration print the second max element of an array.
C Program to Find the Second Largest Number in an Array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> int secondLargest(int arr[], int len) { //Initialize int max = INT_MIN; int second_max = INT_MIN; for(int i = 0; i < len; i++) { if(arr[i] > max) { second_max = max; max = arr[i]; } if(max > arr[i] && arr[i] > second_max) { second_max=arr[i]; } } return second_max; } int main(void) { int arr[] = {70, 4, 8, 10, 14, 9, 7, 6, 5, 3, 2}; int len = 11; printf("Second highest element is %d\n",secondLargest(arr,len)); return 0; } |
C++ Program to Find the Second Largest Number in an Array
We have written a c code to find the second maximum number in an unsorted array. Let’s write a c++ code to find the second highest number in an array.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> using namespace std; int main() { int n, i; cout << "Enter number of elements in an array \n"; cin >> n; int arr[n]; cout << "Enter values in an array \n"; //Input array elements for (i = 0; i < n; i++) { cin >> arr[i]; } //Assign min value to max and second_max int max = INT_MIN; int second_max = INT_MIN; //Traverse an array to find second max for (i = 0; i < n; i++) { if(arr[i] > max) { second_max = max; max = arr[i]; } if(arr[i] < max && arr[i] > second_max) { second_max = arr[i]; } } cout << "Second highest number in an unsorted array is " << second_max; return 0; } |
Find second smallest number in an array
Video Tutorial Link
C, C++ program to find second largest number in an array
Find second largest number in an array
Conclusion
There are multiple ways by which you can solve this problem efficiently. I have explained two approaches. If you want to share any other approach to solve this problem efficiently then let us know through your comment.
