Best method to find the extrema points of a 2D array in C++?

Question

I'm looking for a method to find the maximum and minimum values of a 2D integer array in C++. I'm aware of the std::max_element() and std::min_element(), but they only seem to work for one dimensional arrays.

The 2D array could be declared and initialized by:

int temp[5][5];

for(int x = 0; x < 5; x++)
{
    for(int y = 0; y < 5; y++)
    {
        temp[x][y] = some_random_number;
    }
}

A simple method could be to do something like:

int min = high_number;
int max = low_number;

for(int x = 0; x < 5; x++)
{
    for(int y = 0; y < 5; y++)
    {
        if(temp[x][y] < min)
        {
            min = temp[x][y];
        }
        if(temp[x][y] > max)
        {
            max = temp[x][y];
        }
    }
}

But this doesn't seem very optimized. Is anyone able to give some advice or propose a better idea?

Answer 1

You can still use std::min_element and std::max_element like this:

int arr[2][2] = {{434, 43}, {9826, 2}};
auto pair = std::minmax_element(&arr[0][0], &arr[0][0] + 4);

Live demo

where 4 is the total number of elements.

Notice that for readability the above solution uses operator& to get the address to the beginning of the array, but std::addressof is recommended because operator& could be overloaded.

If you want you can also declare helper functions for the equivalent bidimensional array begin and end functions:

template<typename T, std::size_t N, std::size_t M>
auto bi_begin(T (&arr)[N][M]) {
    return std::addressof(arr[0][0]);
}

template<typename T, std::size_t N, std::size_t M>
auto bi_end(T (&arr)[N][M]) {
    return bi_begin(arr) + N * M;
}

Live demo

I've intentionally avoided the names begin and end because it could generate infinite discussions here.

---

Overall, I would recommend defining a matrix type which is implemented as a std::array of M * N elements, and then provide proper begin and end member functions, which can then be used with any standard algorithm.

Answer 2

If there are no other constraints on the contents of your array/matrix, you cannot do better than looking at each element. That means that your solution is actually an optimal solution in terms of asymptotic running time.

I would also argue that it is good in terms of readability, but some might find this easier to read (since it's shorter):

for(int x = 0; x < 5; x++)
{
   for(int y = 0; y < 5; y++)
   {
      min = std::min(temp[x][y], min);
      max = std::max(temp[x][y], max);
   }
}