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
- 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?
- 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
We start by assuming the first element is both the max and the second max. Then we scan through the array.
When we hit 56, it’s greater than our current max (1). So we shift the old max down to second_max and update max.
max = 56
2nd max = 1
When we hit 4, it’s not greater than max but it is greater than second_max. So we update second_max.
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 assumed the first element is both the maximum and second maximum — just like we did in the previous example. But here, the first element is 56, and when we scan through the rest of the array, nothing beats 56. So second_max never gets updated.
max = 56
2nd max = 56
This still keeps the second maximum value as 56. So our algorithm returns 56 as the second largest — which is wrong. It’s the same as the largest!
The issue is in our initialization. By setting both max and second_max to arr[0], we’re assuming the first element is a good starting point. But when the largest element happens to be at the beginning, second_max never gets a chance to update properly.
The fix is simple — we initialize both values to the lowest possible integer value 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 the algorithm works as expected. With Integer.MIN_VALUE as the starting point, every real element in the array is guaranteed to be greater, so both max and second_max will be properly assigned during the scan.
Time and Space Complexity
Let’s break it down:
- Time complexity: O(n) — we scan through the array exactly once. No sorting, no nested loops. Just a single pass.
- Space complexity: O(1) — we only use two extra variables regardless of the input size.
Compare that to the sorting approach which takes O(n log n) time and potentially O(n) extra space depending on the sorting algorithm. For a problem this simple, that’s overkill.
Edge Cases to Consider
Before you call it a day, think about these:
- Array with all identical elements — if every element is the same, what should the second largest be? This depends on the problem definition. If they want distinct values, you might need to return -1 or throw an exception.
- Array with only one element — there is no second largest. Handle this before the loop.
- Array with negative numbers — our
Integer.MIN_VALUEapproach handles this correctly since it’s smaller than any valid integer.
A production-ready version might look like this:
public static int findSecondLargest(int[] arr) {
if (arr.length < 2) {
throw new IllegalArgumentException("Array must have at least 2 elements");
}
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] && arr[i] != max) {
second_max = arr[i];
}
}
if (second_max == Integer.MIN_VALUE) {
throw new IllegalArgumentException("No second largest element found");
}
return second_max;
}
Notice the arr[i] != max check in the else-if condition — this ensures we skip duplicates of the maximum value and find the true second distinct largest.
Wrapping Up
This is one of those problems that looks dead simple until you start thinking about edge cases. The key takeaway here is — don’t reach for sorting when a linear scan will do. O(n) vs O(n log n) might not matter for small arrays, but in interviews, the interviewer wants to see that you can think about efficiency.
Also, always test with edge cases. Duplicates, single elements, negative numbers — these are the traps interviewers love to set. If you handle them cleanly, you’re already ahead of most candidates.
Happy coding!
