# Finding the second largest element in a range

In recent days, there’s been a question coming up on twitter: how do you find the second largest element in an array (container)? People are providing different answers. As usual, there are multiple solutions to this problem and they depend on the actual requirements: could this operation have side effect (change the original range) or should it be left untouched? In this post, I will discuss several solutions in C++ to this problem.

Before going forward, I want to add some more requirements:

• if the range is empty, the function must not return any value
• if the range has only one element, the function must return this element
• if all the range elements have the same value, the function must return this value

You could argue whether these make sense or not but I will start with these premises.

## Scenario 1: the range must not be modified

Let’s first assume that the range must not be modified by this operation. I would guess that this should be the requirement in most cases when you need to find the second largest element. As someone put it on Twitter:

There are two possible solutions for this: a user-defined search and using `std::max_element`. Let’s see them both.

### User-defined search function

We can write and explicit iteration of the range and compare elements to find the 2nd largest. The algorithm is as follows:

• define two variables to store the 1st and 2nd largest values and initialize them with the first two elements of the range
• iterate the range until the end doing the following:
• if the current element is greater than the largest, then assign 2nd largest to the value of 1st largest, and the 1st largest to the current element
• otherwise, if the current element is greater than the 2nd largest then assign its value to the 2nd largest

This can be implemented as follows using a function template that takes iterators to the first and last elements of a range:

```template <typename Iter>
Iter find_2nd_largest_1(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;

auto max1 = begin++;
auto max2 = begin++;
if (*max1 < *max2) std::swap(max1, max2);

for (auto it = begin; it != end; ++it)
{
if (*it > *max1)
{
max2 = max1;
max1 = it;
}
else if (*it > *max2 && *it < *max1)
{
max2 = it;
}
}

return max2;
}```

Notice that the first two checks are meant to ensure the first two requirements defined in the beginning are properly handled.

### Using std::max_element

A second alternative is to use the `std::max_element` general purpose algorithm. However, we need to use this twice:

• the first call would find the largest element in the range
• the second call would require a comparer to help find the largest element that is smaller than the element found with the first call

Of course, this means there are two passes through the range and this implies a degraded performance as the number of elements increases. But will see about this later. The following is a possible implementation:

```template <typename Iter>
Iter find_2nd_largest_2(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;

auto m = std::max_element(begin, end);

auto m2 = std::max_element(
begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m && e1 < e2; });

return m2;
}```

## Scenario 2: the range can be modified

Assuming you can modify the original range there are additional solutions to the problem using partial sorting algorithms from the standard library.

(As a side note, I’d like to hear some use cases where modifying the range is OK, but that’s a side issue for now.)

### Using std::nth_element

The std::nth_element function is a partial sorting algorithm that rearranges elements in a range. It takes two iterators that define the range (begin and last) and a pivot (the nth element) and sorts the range such that:

• the element pointed by the pivot is changed with the element that would occur in that position if the range was sorted
• all the elements before the pivot are changed so they are less or equal to the elements after the new pivot (nth element)

We can partially sort the range using the 2nd element as the pivot, and using operator `>` instead of the default operator `<` for comparison (in other words we would sort descending, not ascending).

Here is the implementation:

```template <typename Iter>
Iter find_2nd_largest_3(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;

std::nth_element(begin, begin + 1, end, std::greater<>());

return begin + 1;
}```

This is even less code than with `std::max_element` although remember, the range is modified.

### Using std::partial_sort

The std::partial_sort function is a general purpose algorithm that rearranges elements in a range based on a pivot so that the `pivot - first` smallest elements come first followed by the other elements in an specified order.

Again, the default behavior is to sort using operator `<` so we need to change this and sort using operator `>`. We only need to sort the largest two elements of the range, so the pivot would be `begin + 2`. Here is how the implementation would look:

```template <typename Iter>
Iter find_2nd_largest_4(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;

std::partial_sort(begin, begin + 2, end, std::greater<>());

return begin + 1;
}```

This is very similar to the previous implementation. The question is, which is faster? But before answering that, let’s see if they actually do the right thing.

## Testing the implementations

To put these implementations to test, we can write the following simple tests to ensure they always return the expected value:

```void basic_tests()
{
std::vector<std::pair<std::optional<int>, std::vector<int>>> data = {
{{}, { }},
{1, { 1}},
{1, { 1, 2}},
{1, { 2, 1}},
{2, { 2, 3, 1}},
{2, { 3, 2, 1}},
{1, { 1, 1, 1 }},
{1, { 1, 2, 1 }},
{1, { 1, 2, 2 }},
{4, { 1, 2, 3, 4, 5 }},
{5, { 1, 2, 3, 4, 5, 6 }},
{4, { 5, 4, 3, 2, 1 }},
{5, { 6, 5, 4, 3, 2, 1 }},
{8, { 4, 2, 1, 5, 8, 6, 9, 3, 7 }},
};

std::cout << std::format("{:<10} {:<10} {:<10} {:<10} {:<10}\n",
"expected", "manual", "max", "nthelem", "partsort");

for (auto const & [e, v] : data)
{
auto m1 = find_2nd_largest_1(v.begin(), v.end());
auto m2 = find_2nd_largest_2(v.begin(), v.end());
auto v3 = v;
auto m3 = find_2nd_largest_3(v3.begin(), v3.end());
auto v4 = v;
auto m4 = find_2nd_largest_4(v4.begin(), v4.end());

std::cout << std::format("{:<10} {:<10} {:<10} {:<10} {:<10}\n",
(bool)e ? std::to_string(e.value()) : "N/A",
m1 != v.end() ? std::to_string(*m1) : "N/A",
m2 != v.end() ? std::to_string(*m2) : "N/A",
m3 != v3.end() ? std::to_string(*m3) : "N/A",
m4 != v4.end() ? std::to_string(*m4) : "N/A");
}
}```

If we run this, we get the following output:

```expected   manual     max        nthelem    partsort
N/A        N/A        N/A        N/A        N/A
1          1          1          1          1
1          1          1          1          1
1          1          2 [!]      1          1
2          2          2          2          2
2          2          3 [!]      2          2
1          1          1          1          1
1          1          1          1          1
1          1          1          2 [!]      2 [!]
4          4          4          4          4
5          5          5          5          5
4          4          5          4          4
5          5          6 [!]      5          5
8          8          8          8          8```

An exclamation mark here indicates the result is not what was expected.

Let’s first look at `std::max_element`. It got the wrong results for the following test cases:

```{ 2, 1}
{ 3, 2, 1}
{ 6, 5, 4, 3, 2, 1 }```

We can notice here that the maximum element is always the first. There is a bug on this line:

`auto m2 = std::max_element(begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m&& e1 < e2; });`

It starts with the first element and compares it against each of the rest and the maximum but it will never find something larger. We need to modify this: when the largest is the first, then continue from the second element:

```template <typename Iter>
Iter find_2nd_largest_2(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;

auto m = std::max_element(begin, end);

auto m2 = std::max_element(
m == begin ? begin + 1 : begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m&& e1 < e2; });

return m2;
}```

With this change, `find_2nd_largest_2` always returns the expected value.

The second problem is related to `std::nth_element` and `std::partial_sort`. They both fail for the range `{ 1, 2, 2 }`. We can see here that the maximum element appears multiple times. There was an implicit assumption that this would not appear more than once. If that’s not true, then these two solutions do not work.

## Comparing performance

The last but not least thing to check is how do they perform against each other. For this, I have written another simple test.

```void benchmark()
{
std::cout << std::format("{:>10} {:>10} {:>10} {:>10} {:>10}\n",
"size", "manual", "max", "nthelem", "partsort");

std::vector<size_t> sizes{ 1000, 10000, 100000, 1000000, 10000000 };
for (auto size : sizes)
{
std::vector<int> data;
generate(data, size);

auto d3 = data;
auto d4 = data;

auto m1 = find_2nd_largest_1(data.begin(), data.end());

auto m2 = find_2nd_largest_2(data.begin(), data.end());

auto m3 = find_2nd_largest_3(d3.begin(), d3.end());

auto m4 = find_2nd_largest_4(d4.begin(), d4.end());

if (*m1 == *m2 || *m1 == *m3 || *m1 == *m4) // this is just to ensure calls are not remove because of optimizations
{
std::cout << std::format(
"{:>10} {:>10} {:>10} {:>10} {:>10}\n",
size,
std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(),
std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count(),
std::chrono::duration_cast<std::chrono::microseconds>(t4 - t3).count(),
std::chrono::duration_cast<std::chrono::microseconds>(t5 - t4).count()
);
}
}
}```

Run with optimizations enabled (a release build) I get the following numbers (of course, these vary slightly with each run):

```      size     manual        max    nthelem   partsort
1000          1          3         11          1
10000         11         28        112          6
100000        104        293       1306        107
1000000       4044       8083      10364       4020
10000000      25980      34281      66386       5834```

There are several thing to notice here:

• the implementation using two calls to `std::max_element` is always less performant than the manual search (about twice as much time to find the 2nd largest)
• the implementation using the `std::nth_element` is the least performant of them all
• the implementation using `std::partial_sort` is comparable to the manual search and several times faster when there are 10 million elements in the range

The reason `std::partial_sort` is much faster than `std::nth_element` is that it does much fewer swaps. This is demonstrated in a cppcon talk by Marshall Clow: Down the Rabbit Hole: An Exploration of Stack Overflow Questions.

## Conclusions

Problems usually have multiple solutions and finding the 2nd largest element in a range is no different. In my opinion, modifying the range is rarely an option, so, usually, you’d have to chose between the first two implementations. The manual search is faster but if you only have a small number of elements using `std::max_element` twice should not represent a performance problem.

This site uses Akismet to reduce spam. Learn how your comment data is processed.