Write a Java Program to find the second-highest number in an array.

The optimal approach is to traverse the array only once while maintaining the largest and second-largest values found so far.

For each element: 1. If the current number is greater than the largest number, update the second-largest value with the previous largest value and assign the current number as the largest. 2. If the current number is smaller than the largest number but greater than the second-largest number, update the second-largest value.

This approach avoids sorting the array and provides better performance for large datasets.

Java Solution:

public class SecondHighestNumber {

    public static int findSecondHighest(int[] numbers) {

        if (numbers == null || numbers.length < 2) {
            throw new IllegalArgumentException(
                    "Array must contain at least two elements."
            );
        }

        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;

        for (int number : numbers) {

            if (number > largest) {
                secondLargest = largest;
                largest = number;
            } else if (number > secondLargest && number != largest) {
                secondLargest = number;
            }
        }

        if (secondLargest == Integer.MIN_VALUE) {
            throw new IllegalArgumentException(
                    "Second highest number does not exist."
            );
        }

        return secondLargest;
    }

    public static void main(String[] args) {

        int[] numbers = {12, 35, 1, 10, 34, 1};

        int secondHighest = findSecondHighest(numbers);

        System.out.println("Second Highest Number: " + secondHighest);
    }
}

Output: Second Highest Number: 34

Time Complexity: O(n), where n is the number of elements in the array because the array is traversed only once.

Space Complexity: O(1), since only two additional variables are used regardless of the input size.

Key Interview Points: • The single-pass approach is more efficient than sorting the array, which requires O(n log n) time. • The solution correctly handles duplicate maximum values. • Always consider edge cases such as arrays with fewer than two elements or arrays containing identical values. • A common follow-up question is to find the third-largest or kth-largest element in an array.