Finding the Second Largest Element in an Array
An introduction to one of the most frequently asked foundational interview questions: finding the second largest value in an array.
A Classic Interview Problem
"Find the second largest element in an array."
This problem seems trivial at first glance, which is exactly why interviewers love it. It is the perfect filter to test a candidate's understanding of edge cases, time complexity, and optimization.
The Problem Breakdown
You are given an array of integers. Your goal is to return the value that is strictly smaller than the maximum value, but larger than all other values. For example:
- Input:
[10, 5, 20, 8] - Output:
10
The Hidden Complexities
While finding the absolute maximum is easy (just keep track of the highest number seen so far), finding the second highest requires managing state carefully. You have to ask yourself:
- What if the array has duplicates? (e.g.,
[10, 10, 5]) - What if the array has negative numbers? (e.g.,
[-10, -20, -5]) - What if the array has less than two elements?
Why Interviewers Ask This
This question evaluates your progression of thought. An interviewer expects you to:
- Suggest the brute-force sorting method (O(N log N)).
- Improve it to a two-pass linear method (O(2N)).
- Optimize it into a final one-pass method (O(N)).
The Takeaway
Do not dismiss basic array problems. Mastering the logic required to track multiple variables (like max and second_max) simultaneously is the foundation for solving complex dynamic programming and array traversal questions later on.
It tests basic array traversal, state management (tracking multiple variables), and handling of edge cases like duplicates and negative numbers.
Interviewers expect a final, optimal solution that runs in O(N) linear time, iterating through the array only once.
Yes. In an array like [10, 10, 5], the largest is 10, and the second largest is 5. Duplicates of the maximum do not count as the second largest.
You can mention them, but interviewers will immediately ask you to implement the logic manually without using built-in sorting or max functions.
If the array has fewer than 2 elements, or all elements are identical, the function should return a designated error value like -1 or throw an exception.