In this tutorial, I am going to discuss the easiest way to find second largest number in array.
Given an array of integers. The array is unsorted. Write a java code to find second highest number in an array.
For example –
Input – arr[] = { 1, 9, 5, 2, 8, -1, 3, 55}
Output: 9
In this example, we have given an unsorted array of integers. The second largest number in this array is 9.
This problem is itself not very tough. But how do you approach this kind of problems tells lot about your problem solving ability.
For solving any kind of problems time and space complexity is an important factor. Try to solve this problem in a minimum time complexity.
In this tutorial, I am going to discuss multiple approaches and their time complexities to solve this problem.
Before checking the solution think how do you approach this problem. Which approach you prefer and why?
How to Find Second Largest Element in Array?
The easiest way to solve this problem is to sort an array. After sorting an array, the number present at n-2 index is the second highest number in an array.
Insertion Sort Program in Java
For sorting either we can write our own custom sort method using sorting algorithms or we can use java inbuilt sort method.
The time complexity of sorting an array is O(nlogn).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import java.util.Arrays; public class SecondHighest { public static void main(String[] args) { //unsorted array int num[] = {1, 9, 5, 2, 8, -1, 3, 55}; //Length of an array int n = num.length; //Sort the array Arrays.sort(num); /** * After sorting * Second highest number is at n-2 position */ System.out.println("Second Highest Number: "+num[n-2]); } } |
NOTE: If the element of an array is repeated then this approach won’t work.
To understand this concept, let’s take an example.
int num[] = {1, 9, 5, 55, 8, -1, 3, 55};
So what will be the second highest number if we use above method (sort and pick the element present at n-2 index). The element is 55 which is wrong.
The best approach is to traverse an array once to find second highest number. Let’s implement this approach.
Find Second Largest Number in Array without Sorting – Java Code
The idea here is to traverse an array once. Declare two variables highest and secondHighest. Initially, Assign them with Integer minimum possible value.
In each iteration, Compare the value present at current index with highest and secondHighest variable. If current value is greater than the highest then assign highest value in second highest and current value in highest variable.
The time complexity of this approach is O(n).
|
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 37 38 |
//Find second largest number in array without sorting public class SecondHighest { public static void main(String[] args) { // unsorted array int num[] = { 1, 9, 5, 55, 8, -1, 3, 55 }; // Length of an array int n = num.length; // Initialize highest and second highest with minimum integer value int highest = Integer.MIN_VALUE; int secondHighest = Integer.MIN_VALUE; //Traverse an array for (int i = 0; i < n; i++) { // If greater than highest if (num[i] > highest) { // Assign highest value into secondhigest secondHighest = highest; // Set new highest highest = num[i]; } // If number is less than highest and greater than secondHighest if (num[i] < highest && num[i] > secondHighest) { // Set second highest secondHighest = num[i]; } } System.out.println("Second highest " + secondHighest); } } |
Find Second Max in an Array : Video Tutorial
In this video tutorial, I have explained how we can find second highest number without sorting an array.
Find second largest number in an array – video tutorial
Java program to find the first non-repeated character in a string
Find pair of elements in an array whose sum is equal to a given number
I have discussed two approaches to solve this problem. If you know some other better way to solve this problem then you can discuss with us through your comments.
