There is an integer matrix which has the following features:

• The numbers in adjacent positions are different.
• The matrix has n rows and m columns.
• For all i < m, A[0][i] < A[1][i] & & A[n - 2][i] > A[n - 1][i] .
• For all j < n, A[j][0] < A[j][1] & & A[j][m - 2] > A[j][m - 1] .

We define a position P is a peek if:

A[j][i] 
>
 A[j+1][i] 
&
&
 A[j][i] 
>
 A[j-1][i] 
&
&
 A[j][i] 
>
 A[j][i+1] 
&
&
 A[j][i] 
>
 A[j][i-1]

Find a peak element in this matrix. Return the index of the peak.

Notice

The matrix may contains multiple peeks, find any of them.

Have you met this question in a real interview?

Yes

Example

Given a matrix:

[
  [1 ,2 ,3 ,6 ,5],
  [16,41,23,22,6],
  [15,17,24,21,7],
  [14,18,19,20,10],
  [13,14,11,10,9]
]

return index of 41 (which is[1,1]) or index of 24 (which is[2,2])

Challenge

Solve it in O(n+m) time.

If you come up with an algorithm that youthought_it is O(n log m) or O(m log n), can you prove it is actually O(_n+m) or propose a similar but O(n+m) algorithm?

class Solution {

public:

/\*\*

 \* @param A: An integer matrix

 \* @return: The index of the peak

 \*/

vector<int> findPeakII\(vector<vector<int> > A\) {

    // write your code here

    if \(A.empty\(\) \|\| A\[0\].empty\(\)\) {

        return {};

    }

    int n = A.size\(\), m = A\[0\].size\(\);

    int l = 1, r = m - 1, t = 1, b = n - 1;

    vector<int> res;

    while \(l <= r && t <= b\) {

        int mid = \(r - l\) / 2 + l;

        int row = findRow\(mid, l, r, t, b, A\);

        if \(A\[row\]\[mid\] < A\[row\]\[mid - 1\]\) {

            r = mid - 1;

        } else if \(A\[row\]\[mid\] < A\[row\]\[mid + 1\]\) {

            l = mid + 1;

        } else {

            res.push\_back\(row\);

            res.push\_back\(mid\);

            break;

        }



        mid = \(b - t\) / 2 + t;

        int col = findCol\(mid, l, r, t, b, A\);

        if \(A\[mid\]\[col\] < A\[mid - 1\]\[col\]\) {

            b = mid - 1;

        } else if \(A\[mid\]\[col\] < A\[mid + 1\]\[col\]\) {

            t = mid + 1;

        } else {

            res.push\_back\(mid\);

            res.push\_back\(col\);

        }

    }

    return res;

}



int findRow\(int col, int l, int r, int t, int b, vector<vector<int>>& A\) {

    int row = t;

    for \(int i = t; i <= b; ++i\) {

        if \(A\[i\]\[col\] > A\[row\]\[col\]\) {

            row = i;   

        }

    }

    return row;

}



int findCol\(int row, int l, int r, int t, int b, vector<vector<int>>& A\) {

    int col = l;

    for \(int i = l; i <= r; ++i\) {

        if \(A\[row\]\[i\] > A\[row\]\[col\]\) {

            col = i;

        }

    }

    return col;

}

};