Finding the Second Largest Element in an Array

Hi all,

Here I'm back with another algorithmic problem. This is a classical interview question asked almost everywhere. As you may know, I recently did a Software Engineering internship at WSO2. While preparing for those interviews, I came across this simple-looking but tricky problem.

Let’s jump into it.

The Problem

You are given an array of integers. Your task is to find the second largest element in the array.

For example,

If we sort this array, we clearly see.

A straightforward Java solution might look like this.

public static int FindSecondLargest(int[] arr) {
    sort(arr);
    return arr[arr.length - 2];
}

But… this is not a good solution.

Why Sorting Is Not the Right Approach

1. Sorting is unnecessary and inefficient

Sorting takes O(n log n) time. But finding the second largest element can be done in O(n). Why waste extra computation?

2. Duplicate elements break our logic

If the largest value appears multiple times, this approach might still return the same largest value instead of the second distinct largest.

The O(n) Linear Scan Approach

We can find the second largest in just O(n) time.

max     = 1
2nd max = 1

sdf

max     = 56
2nd max = 1

max     = 56
2nd max = 4

    public static int findSecondLargest(int[] arr) {

        int max = arr[0];
        int second_max = arr[0];

        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                second_max = max;
                max = arr[i];

            } else if (second_max < arr[i]) {
                second_max = arr[i];
            }
        }

        return second_max;

    }

The Hidden Bug

It seems like the correct algorithm right? We are good to go.

but, Wait!!

What if the array is something like bellow?

max     = 56
2nd max = 56

We assume the first element is maximum and second maximum. (Just for the beginning as we did in previous example.)

max     = 56
2nd max = 56

This still keeps the second maximum value as 56. Then this approach is not going to work for finding the second maximum of the array.

But we can correct the algorithm by a simple tweak. We set the maximum and second maximum values to the lowest possible integer value. We can obtain this by using Integer.MIN_VALUE.

    public static int findSecondLargest(int[] arr) {

        int max = Integer.MIN_VALUE;
        int second_max = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                second_max = max;
                max = arr[i];

            } else if (second_max < arr[i]) {
                second_max = arr[i];
            }
        }

        return second_max;

    }

Now, algorithm should works as expected.