Java Program to Find Second Largest Number in An Array

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).

But time complexity of this solution is O(nlogn).

4. More Optimized Solution

  • Initialize two variables, highest and secondHighest, with the minimum possible values.
  • Iterate through the array:
    • If the current element is greater than highest:
      • Assign secondHighest the value of highest.
      • Assign highest the value of the current element.
    • Else if the current element is greater than secondHighest and not equal to highest:
      • Assign secondHighest the value of the current element.
Here is java program to find second largest number in array:
When you run above program, you will get below output:

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:

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)

Was this post helpful?

Comments

  1. 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}

  2. If we change else id condition code works fine all cases,
    else if (array[i] > secondHighest && array[i] != highest){
    secondHighest = array[i];
    }

Leave a Reply

Your email address will not be published. Required fields are marked *