How to Find the Second Largest Number in an Array
Finding the second largest number in an array is a common Data Structures and Algorithms (DSA) problem.
It looks simple, but it tests several important programming concepts:
Array traversal
Comparison logic
Handling duplicate values
Edge cases
Time complexity
Space complexity
Writing an efficient one-pass algorithm
For example, given:
[10, 5, 8, 20, 15]
the largest number is:
20
and the second largest number is:
15
In this article, we will learn different ways to solve this problem and understand why the one-pass approach is usually the best solution.
Problem Statement
Given an array of integers, find the second largest distinct element.
Example
Input:
[10, 5, 8, 20, 15]
Output:
15
Another example:
[3, 7, 2, 9, 5]
Output:
7
What Does "Second Largest" Mean?
It is important to clarify that we usually mean the second largest distinct value.
Consider:
[10, 20, 20, 5]
The largest value is:
20
The second largest distinct value is:
10
It is not 20 again.
Therefore:
Largest = 20
Second Largest = 10
This distinction is important when designing the algorithm.
Approach 1: Sort the Array
The easiest approach is to sort the array.
For:
[10, 5, 8, 20, 15]
after sorting:
[5, 8, 10, 15, 20]
The second largest element is:
15
However, there is an important problem.
Sorting the entire array is unnecessary if we only need the second largest value.
Python Solution Using Sorting
def second_largest(arr):
unique_values = list(set(arr))
if len(unique_values) < 2:
return None
unique_values.sort()
return unique_values[-2]
numbers = [10, 5, 8, 20, 15]
print(second_largest(numbers))
Output:
15
The set() removes duplicates before sorting.
Complexity of the Sorting Approach
Suppose the array contains n elements.
Sorting requires:
O(n log n)
time in typical comparison-based sorting.
The set() operation requires approximately:
O(n)
average time.
Therefore, the overall complexity is dominated by sorting:
Time Complexity: O(n log n)
Additional space:
Space Complexity: O(n)
because of the set and resulting list.
Although this approach is easy to understand, we can do better.
Approach 2: Find the Largest First
Another approach is to make two passes.
First, find the largest element.
Then find the largest element that is smaller than the maximum.
For example:
[10, 5, 8, 20, 15]
First pass:
Largest = 20
Second pass:
Find largest value < 20
Result:
15
Python Two-Pass Solution
def second_largest(arr):
if len(arr) < 2:
return None
largest = max(arr)
second = None
for number in arr:
if number < largest:
if second is None or number > second:
second = number
return second
numbers = [10, 5, 8, 20, 15]
print(second_largest(numbers))
Output:
15
This approach runs in:
O(n)
time because the array is traversed a constant number of times.
Approach 3: One-Pass Optimal Solution
We can solve the problem in a single traversal.
We maintain two variables:
largest
second_largest
As we move through the array, we update them.
For example:
Array:
[10, 5, 8, 20, 15]
Start:
largest = -∞
second_largest = -∞
Process 10:
largest = 10
second_largest = -∞
Process 5:
largest = 10
second_largest = 5
Process 8:
largest = 10
second_largest = 8
Process 20:
largest = 20
second_largest = 10
Process 15:
largest = 20
second_largest = 15
Final result:
15
Python One-Pass Solution
def second_largest(arr):
if len(arr) < 2:
return None
largest = float("-inf")
second_largest = float("-inf")
for number in arr:
if number > largest:
second_largest = largest
largest = number
elif (
number > second_largest
and number != largest
):
second_largest = number
if second_largest == float("-inf"):
return None
return second_largest
numbers = [10, 5, 8, 20, 15]
print(second_largest(numbers))
Output:
15
Understanding the Logic
The most important part is:
if number > largest:
second_largest = largest
largest = number
Suppose:
largest = 20
second_largest = 15
and we encounter:
25
The new largest is 25.
The previous largest, 20, becomes the second largest.
Therefore:
Before:
largest = 20
second_largest = 15
After:
largest = 25
second_largest = 20
Why Do We Need the elif Condition?
Consider:
[10, 20, 15]
When we find 20:
largest = 20
second_largest = 10
When we find 15:
15 < 20
so it cannot become the largest.
But:
15 > 10
Therefore:
second_largest = 15
This is handled by:
elif (
number > second_largest
and number != largest
):
second_largest = number
Handling Duplicate Values
Consider:
[10, 20, 20, 5]
When the first 20 appears:
largest = 20
second_largest = 10
When the second 20 appears:
number == largest
Therefore, it should not replace the second largest value.
The condition:
number != largest
prevents duplicate maximum values from being treated as the second largest.
The result is:
10
Example With Negative Numbers
The algorithm also works with negative values.
Consider:
[-10, -5, -20, -3]
The largest value is:
-3
The second largest is:
-5
Test:
numbers = [-10, -5, -20, -3]
print(
second_largest(numbers)
)
Output:
-5
Using:
float("-inf")
allows the algorithm to work correctly with negative numbers.
Example With All Equal Values
Consider:
[5, 5, 5, 5]
There is no second largest distinct value.
Therefore:
Output:
None
The function handles this case using:
if second_largest == float("-inf"):
return None
Example With Only One Element
Input:
[10]
There is no second largest element.
The function returns:
None
because:
if len(arr) < 2:
return None
Example With Two Elements
Input:
[10, 20]
The largest is:
20
The second largest is:
10
Output:
10
Complete Python Program
Here is a complete version that accepts user input.
def second_largest(arr):
if len(arr) < 2:
return None
largest = float("-inf")
second_largest = float("-inf")
for number in arr:
if number > largest:
second_largest = largest
largest = number
elif (
number > second_largest
and number != largest
):
second_largest = number
if second_largest == float("-inf"):
return None
return second_largest
numbers = list(
map(
int,
input(
"Enter numbers separated by spaces: "
).split()
)
)
result = second_largest(numbers)
if result is None:
print(
"There is no second largest "
"distinct element."
)
else:
print(
"Second largest:",
result
)
Example:
Enter numbers separated by spaces: 10 5 8 20 15
Output:
Second largest: 15
Java Solution
The same one-pass algorithm can be implemented in Java.
public class Main {
public static Integer secondLargest(int[] arr) {
if (arr.length < 2) {
return null;
}
int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
boolean foundSecond = false;
for (int number : arr) {
if (number > largest) {
if (largest != Integer.MIN_VALUE) {
secondLargest = largest;
foundSecond = true;
}
largest = number;
} else if (
number > secondLargest
&& number != largest
) {
secondLargest = number;
foundSecond = true;
}
}
return foundSecond
? secondLargest
: null;
}
public static void main(String[] args) {
int[] numbers = {
10, 5, 8, 20, 15
};
Integer result =
secondLargest(numbers);
System.out.println(
"Second largest: " + result
);
}
}
Output:
Second largest: 15
C++ Solution
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
bool secondLargest(
const vector<int>& arr,
int& result
) {
if (arr.size() < 2) {
return false;
}
int largest =
numeric_limits<int>::min();
int secondLargest =
numeric_limits<int>::min();
bool foundSecond = false;
for (int number : arr) {
if (number > largest) {
if (
largest !=
numeric_limits<int>::min()
) {
secondLargest = largest;
foundSecond = true;
}
largest = number;
} else if (
number > secondLargest &&
number != largest
) {
secondLargest = number;
foundSecond = true;
}
}
if (!foundSecond) {
return false;
}
result = secondLargest;
return true;
}
int main() {
vector<int> numbers = {
10, 5, 8, 20, 15
};
int result;
if (secondLargest(numbers, result)) {
cout
<< "Second largest: "
<< result
<< endl;
} else {
cout
<< "No second largest element."
<< endl;
}
return 0;
}
Output:
Second largest: 15
JavaScript Solution
function secondLargest(arr) {
if (arr.length < 2) {
return null;
}
let largest = -Infinity;
let secondLargest = -Infinity;
for (const number of arr) {
if (number > largest) {
secondLargest = largest;
largest = number;
} else if (
number > secondLargest &&
number !== largest
) {
secondLargest = number;
}
}
if (secondLargest === -Infinity) {
return null;
}
return secondLargest;
}
const numbers = [
10, 5, 8, 20, 15
];
console.log(
secondLargest(numbers)
);
Output:
15
Complexity Analysis
Let's compare the three approaches.
ApproachTime ComplexitySpace ComplexitySortingO(n log n)O(n)Two PassesO(n)O(1)One PassO(n)O(1)
The one-pass approach is usually the preferred solution because it:
Traverses the array only once
Uses constant extra space
Handles duplicates
Works with negative numbers
Does not modify the original array
Therefore:
Time Complexity: O(n)
Space Complexity: O(1)
Common Interview Mistakes
Mistake 1: Sorting unnecessarily
Using:
arr.sort()
works, but it solves a more expensive problem than necessary.
If you only need the second largest element, there is no need to completely sort the array.
Mistake 2: Ignoring duplicates
For:
[10, 20, 20, 5]
the answer should normally be:
10
not:
20
when the problem asks for the second largest distinct element.
Mistake 3: Incorrect initialization
Using:
largest = 0
can fail for an array containing only negative numbers.
For example:
[-10, -5, -20]
Therefore, use:
largest = float("-inf")
or another initialization strategy appropriate to the language.
Mistake 4: Forgetting edge cases
Always consider:
[]
[10]
[10, 10]
[5, 5, 5]
[-10, -5, -20]
[10, 20]
A good DSA solution should define what happens when there is no second distinct value.
Interview Explanation
If asked this question in an interview, you can explain it like this:
We need to find the second largest distinct element without sorting the array. I will maintain two variables:
largestandsecondLargest. While traversing the array, if the current number is greater thanlargest, the previous largest becomes the second largest. Otherwise, if the current number is between the largest and second largest and is not equal to the largest, I updatesecondLargest. This allows us to solve the problem in one pass with O(n) time and O(1) extra space.
DSA Pattern to Remember
This problem teaches an important pattern:
Maintain Top Two Values
The same idea can be extended to other problems.
For example:
Find the largest
Find the second largest
Find the third largest
Find top K elements
Find minimum and maximum
Track best and second-best scores
For two values:
largest
second_largest
For three:
largest
second_largest
third_largest
For larger K, more efficient data structures such as heaps are often appropriate.
Final Summary
Finding the second largest number is a simple but important DSA problem.
The straightforward approach is to sort the array:
O(n log n)
A better approach is to traverse the array and maintain:
largest
second_largest
The optimal one-pass solution is:
def second_largest(arr):
largest = float("-inf")
second_largest = float("-inf")
for number in arr:
if number > largest:
second_largest = largest
largest = number
elif (
number > second_largest
and number != largest
):
second_largest = number
return (
None
if second_largest == float("-inf")
else second_largest
)
The key takeaway is:
One Pass
↓
Track Largest
↓
Track Second Largest
↓
Ignore Duplicates
↓
O(n) Time
↓
O(1) Space
This problem is a good introduction to array traversal, optimization, edge-case handling, and maintaining running values, which are fundamental techniques used throughout DSA.