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

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

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;
    }
}

When you run above program, you will get below output:

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:

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)