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;
    }
};