How to find second largest number in array

We can find the second largest item in a Java array using two different approaches:

1. Using sorting: We can sort the array and return the second-to-last element. Sorting with Arrays.sort() has a time complexity of O(n log n).
2. Without sorting: We can find the second largest element in O(n) time by traversing the array only once.

Below is the explanation and code for the approach without sorting:

Approach without sorting:

In this approach, we initialize the array and call the getSecondLargestValue() method by passing the array.

Inside the getSecondLargestValue() method:

• We define two variables: max and secondMax.
• While looping through the array:
  • If the current element is greater than max, we update secondMax to max and then update max to the current element.
  • Otherwise, if the current element is less than max but greater than secondMax, we update secondMax to the current element.

This ensures that after the loop, secondMax holds the second largest value in the array.

public class SecondLargestExample {

public static void main(String[] args) {
    int[] arr = {1, 9, 11, 13, 5};

    int secondMaxNoSort = getSecondLargestWithoutSorting(arr);
    System.out.println("Second largest (without sorting): " + secondMaxNoSort);
}

public static int getSecondLargestWithoutSorting(int[] arr) {
    if (arr.length < 2) {
        throw new IllegalArgumentException("Array must have at least two elements.");
    }

    int max = Integer.MIN_VALUE;
    int secondMax = Integer.MIN_VALUE;

    for (int num : arr) {
        if (num > max) {
            secondMax = max;
            max = num;
        } else if (num > secondMax && num < max) {
            secondMax = num;
        }
    }

    if (secondMax == Integer.MIN_VALUE) {
        throw new IllegalArgumentException("No second largest element found (all elements might be equal).");
    }

    return secondMax;
}

}

Approach with sorting:

In this approach, we use the built-in Arrays.sort() method to sort the array in ascending order. Once the array is sorted, the largest element will be at the last index (arr[length - 1]) and the second largest element will be at the second-to-last index (arr[length - 2]).

We also handle cases where all elements are equal by checking for a distinct second largest value. This method has a time complexity of O(n log n) due to the sorting operation.

import java.util.Arrays;

public class SecondMax {

public static void main(String[] args) {
int[] arr = {1, 9, 11, 13, 5};

// Approach 1: Using sorting
int secondMaxSorted = getSecondLargestSorted(arr);
System.out.println(“Second largest (using sorting): ” + secondMaxSorted);

}

public static int getSecondLargestSorted(int[] arr) {
if (arr.length < 2) {
throw new IllegalArgumentException(“Array must have at least two elements.”);
}

int[] sortedArr = arr.clone(); // Clone to avoid modifying original array
Arrays.sort(sortedArr);

// Start from the second-to-last element and move backwards to find distinct value
int max = sortedArr[sortedArr.length – 1];
for (int i = sortedArr.length – 2; i >= 0; i–) {
if (sortedArr[i] < max) {
return sortedArr[i];
}
}

throw new IllegalArgumentException(“No second largest element found (all elements might be equal).”);
}

}