Table of Contents
If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
1. Overview
In this post, we will see how to find the second largest number in an array. This is a one of common interview questions on array data structure.
2. Introduction to Problem Statement
Given an unsorted array, we need to find the second largest element in the array in o(n) time complexity.
For example:
int[] arr1={7,5,6,1,4,2};
Second largest element in the array : 6
3. Sort and Return Second Largest Element
Most Straight forward solution is to sort the array and iterate over the array backwards fron second last element to find the element which is not equal to last element(largest element).
|
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 |
import java.util.Arrays; public class SecondLargestUsingSorting { public static int findSecondLargest(int[] array) { if (array==null || array.length < 2) { return -1; } Arrays.sort(array); for (int i = array.length - 2; i >= 0; i--) { if (array[i] != array[array.length - 1]) { return array[i]; } } return -1; } public static void main(String[] args) { int[] arr = {45, 53, 22, 89, 77, 98, 94}; int result = findSecondLargest(arr); System.out.println("The second largest number is: " + result); } } |
But time complexity of this solution is O(nlogn).
4. More Optimized Solution
- Initialize two variables,
highestandsecondHighest, with the minimum possible values. - Iterate through the array:
- If the current element is greater than
highest:- Assign
secondHighestthe value ofhighest. - Assign
highestthe value of the current element.
- Assign
- Else if the current element is greater than
secondHighestand not equal tohighest:- Assign
secondHighestthe value of the current element.
- Assign
- If the current element is greater than
|
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 |
public class FindSecondLargestMain { public static void main(String args[]) { int[] arr1={7,5,6,1,4,2}; int secondHighest=findSecondLargestNumberInTheArray(arr1); System.out.println("Second largest element in the array : "+ secondHighest); } public static int findSecondLargestNumberInTheArray(int array[]) { // Initialize these to the smallest value possible int highest = Integer.MIN_VALUE; int secondHighest = Integer.MIN_VALUE; // Loop over the array for (int i = 0; i < array.length; i++) { // If current element is greater than highest if (array[i] > highest) { // assign second highest element to highest element secondHighest = highest; // highest element to current element highest = array[i]; } else if (array[i] > secondHighest && array[i]!=highest) // Just replace the second highest secondHighest = array[i]; } // After exiting the loop, secondHighest now represents the second // largest value in the array return secondHighest; } } |
|
1 2 3 |
Second largest element in the array : 6 |
Time complexity: o(n) as array is traversed only once.
Space complexity: o(1) as no extra space is used.
5. Handling Edge Cases
There are two edge cases which we didn’t handle in the program:
- Array has less than two elements: If the array has only one element or is empty, the program will return Integer.MIN_VALUE. This might not be expected output. Let’s return -1 in this scenario.
- Array with All Elements Being the Same: In the case where all elements are identical, the program again returns Integer.MIN_VALUE. Let’s return -1 in this scenario as well.
Let’s handle these scenarios in our program:
|
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 39 40 41 42 43 44 45 |
package org.arpit.java2blog.generic; public class FindSecondLargestMain { public static void main(String args[]) { int[] arr1={7,5,6,1,4,2}; int secondHighest=findSecondLargestNumberInTheArray(arr1); System.out.println("Second largest element in the array : "+ secondHighest); } public static int findSecondLargestNumberInTheArray(int array[]) { // Initialize these to the smallest value possible int highest = Integer.MIN_VALUE; int secondHighest = Integer.MIN_VALUE; if(array==null || array.length < 2) { return -1; } // Loop over the array for (int i = 0; i < array.length; i++) { // If current element is greater than highest if (array[i] > highest) { // assign second highest element to highest element secondHighest = highest; // highest element to current element highest = array[i]; } else if (array[i] > secondHighest && array[i]!=highest) // Just replace the second highest secondHighest = array[i]; } // All the elements are same if(secondHighest == Integer.MIN_VALUE) return -1; // After exiting the loop, secondHighest now represents the second // largest value in the array return secondHighest; } } |
6. Conclusion
In this article, we discussed about how to find second largest elements in the array.
Sorting and returning second last element works fine, but time complexity is o(nlogn). Second method is more optimized solution as array is only traversed once and have time complexity of o(n)
I love your blog. Thanks a ton to you. One of the best website to get ready for interviews.
Hi, this code will fail if an array contains duplicate which is also happened to be largest element.
Example: arr[] = {7, 8, 8, 1, 4, 2}
Missed the edge case!! Thank you for bringing it up. Fixed it.
If we change else id condition code works fine all cases,
else if (array[i] > secondHighest && array[i] != highest){
secondHighest = array[i];
}