If Alice comes can Ben be far behind Now our beloved Bob Bit

If Alice comes, can Ben be far behind? Now, our beloved Bob Bit fiddler has an times n 2-D array on his hands which gives the altitudes of all points in Durham county (let\'s assume Durham is square). But, Durham is not quite a volcano! So, the altitudes form an arbitrary matrix of numbers. Bob would have ideally liked to find the highest point in Durham, but since he does not have the nice property that Alice had, he settles for an easier target: find a locally highest point, i.e., an entry in the n times n 2-D array that is as large as both its horizontal neighbors and both its vertical neighbors. (Bob hopes that this will at least be a hillock if not a mountain!) Formally, M is an n times n array, then M[i, j] is a locally highest point if M[i, j] greaterthanorequalto max(M[i - 1, j], M[i + 1, j], M[i, j - 1], M[i, j + 1]). Note that an entry on the boarder of the grid (which will only have 2 or 3 valid vertical/horizontal neighbors) just needs to be as large as its valid neighbors in order to be considered a locally highest point. Can you help Bob find such an entry in O(n) time? (An O(n log n) solution will get partial credit.)

Solution

include <algorithm>

#include <iostream>

enum { Cm = 2 };

void findHighest(int A[][Cm], int n, int m) {

if (m <= 0) return;

for (int i = 0; i < n; i++) {

    int max = *std::max_element(A[i], A[i] + m);

    std::cout << max << \" \";

}

}

int main() {

int A[2][2] = {{1, 2}, {3, 4}};

findHighest(A, 2, 2);

}

prints 2 4.

void findMax(double x[][COLS])

{

    int max=x[0][0];

        int i,j;

     

    for (i=0; i<ROWS; i++)

        for (j=0; j<COLS; j++)

        {  

            if(x[i][j]> max)

            max= x[i][j];

             

            

        }

}

The time complexity will be O (n*m) where n the number of arrays which is the 1st dimension and m the max size of each internal array ie, the 2nd dimension.

Best case - finding the max element as the first (O(1)), worst case - it is the last element checked (O(n)).

The tricky part is the average case.
To find the average case - we need the expected number of iterations!

Since you can stop after you find the maximum, we can split the problem into two parts:

This totals in O(n) average time solution.