Problem Description

The "Find a Peak Element II" problem asks you to locate a peak element in a 2D matrix mat of size m x n. A peak element is defined as an element that is strictly greater than its four direct neighbors: up, down, left, and right (if those neighbors exist).

You are to return the [row, col] coordinates of any such peak element. You are guaranteed that at least one peak exists. The matrix is not cyclic, so neighbors outside the matrix do not exist.

• Input: 2D integer array mat (size m x n)
• Output: An array [row, col] indicating the position of a peak
• Neighbors are only the four cardinal directions (no diagonals)
• Return any peak position; multiple peaks may exist

Thought Process

The naive approach to this problem is to check every element in the matrix and see if it is greater than all of its neighbors. While this works, it is inefficient for large matrices, since it requires examining every cell.

To improve, we can draw inspiration from the 1D peak finding problem, which can be solved in O(log n) time using binary search. The challenge is extending this idea to two dimensions. Since we only need one peak, we can use a divide-and-conquer approach: at each step, focus on a row or column, locate the maximum in that line, and decide which region to search next based on neighbor comparisons.

This process is similar to how you’d search for a local maximum by always moving toward the highest neighbor. By repeatedly narrowing the search space, we avoid examining every element, making the solution efficient even for large matrices.

Solution Approach

We use a binary search on columns (or rows) to efficiently find a peak:

1. Initialize search bounds: Set left = 0 and right = n - 1 (where n is the number of columns).
2. While left ≤ right:
   • Pick the middle column mid = (left + right) // 2.
   • Find the row max_row with the largest value in column mid.
   • Compare mat[max_row][mid] with its left and right neighbors (if they exist):
   • If mat[max_row][mid] is less than its left neighbor, move search to the left half (right = mid - 1).
   • If mat[max_row][mid] is less than its right neighbor, move search to the right half (left = mid + 1).
   • Otherwise, mat[max_row][mid] is a peak; return [max_row, mid].
3. End: The process continues until a peak is found.

Why does this work? At each step, we move toward a neighbor that is higher, guaranteeing that we do not miss a peak (since at matrix boundaries, the process will stop). We always reduce the search space, ensuring efficiency.

Design choices:

• Binary search on columns is chosen because the number of columns is often large, and finding the max in a column is fast (O(m)).
• We only compare with left and right because, by picking the maximum in the column, we already have the largest value vertically in that column.

Example Walkthrough

Sample Input:

    mat = [
      [10, 20, 15],
      [21, 30, 14],
      [ 7, 16, 32]
    ]
    

1. Step 1: Number of columns n = 3. Start with left = 0, right = 2.
2. Step 2: mid = 1 (middle column). Find max in column 1:
   • Column 1: [20, 30, 16] → max is 30 at row 1.
3. Step 3: Compare mat[1][1] = 30 with left neighbor (21) and right neighbor (14):
   • 30 > 21 (left)
   • 30 > 14 (right)

   30 is greater than both neighbors, so [1, 1] is a peak!

If 30 was not greater than one of its neighbors, we would shift our search to that side and repeat the process.

Time and Space Complexity

Brute-force approach:

• Check every element and compare with up to 4 neighbors.
• Time Complexity: O(mn)
• Space Complexity: O(1)

• At each step, find the max in a column (O(m)), and binary search over columns (log n steps).
• Time Complexity: O(m log n)
• Space Complexity: O(1) (no extra space needed)

The binary search approach is much faster for large matrices, especially when the number of columns is large.

Summary

To solve "Find a Peak Element II", we use a binary search over columns, always moving in the direction of a higher neighbor. By finding the maximum in each column and comparing with adjacent columns, we efficiently narrow down the search to find any peak. This approach is inspired by the 1D peak-finding algorithm and leverages the guarantee that a peak always exists. The result is an elegant, efficient solution that avoids unnecessary work and demonstrates the power of divide-and-conquer in two dimensions.

Code Implementation

class Solution:
    def findPeakGrid(self, mat):
        m, n = len(mat), len(mat[0])
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            # Find the row with the max element in column mid
            max_row = 0
            for i in range(m):
                if mat[i][mid] > mat[max_row][mid]:
                    max_row = i
            # Compare with left and right neighbors
            left_is_bigger = mid - 1 >= 0 and mat[max_row][mid - 1] > mat[max_row][mid]
            right_is_bigger = mid + 1 < n and mat[max_row][mid + 1] > mat[max_row][mid]
            if not left_is_bigger and not right_is_bigger:
                return [max_row, mid]
            elif left_is_bigger:
                right = mid - 1
            else:
                left = mid + 1

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int max_row = 0;
            for (int i = 0; i < m; ++i) {
                if (mat[i][mid] > mat[max_row][mid])
                    max_row = i;
            }
            bool left_is_bigger = mid - 1 >= 0 && mat[max_row][mid - 1] > mat[max_row][mid];
            bool right_is_bigger = mid + 1 < n && mat[max_row][mid + 1] > mat[max_row][mid];
            if (!left_is_bigger && !right_is_bigger)
                return {max_row, mid};
            else if (left_is_bigger)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return {-1, -1}; // Should not reach here
    }
};

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int maxRow = 0;
            for (int i = 0; i < m; i++) {
                if (mat[i][mid] > mat[maxRow][mid]) {
                    maxRow = i;
                }
            }
            boolean leftIsBigger = mid - 1 >= 0 && mat[maxRow][mid - 1] > mat[maxRow][mid];
            boolean rightIsBigger = mid + 1 < n && mat[maxRow][mid + 1] > mat[maxRow][mid];
            if (!leftIsBigger && !rightIsBigger) {
                return new int[]{maxRow, mid};
            } else if (leftIsBigger) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{-1, -1}; // Should not reach here
    }
}

var findPeakGrid = function(mat) {
    const m = mat.length, n = mat[0].length;
    let left = 0, right = n - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let maxRow = 0;
        for (let i = 0; i < m; i++) {
            if (mat[i][mid] > mat[maxRow][mid]) {
                maxRow = i;
            }
        }
        const leftIsBigger = mid - 1 >= 0 && mat[maxRow][mid - 1] > mat[maxRow][mid];
        const rightIsBigger = mid + 1 < n && mat[maxRow][mid + 1] > mat[maxRow][mid];
        if (!leftIsBigger && !rightIsBigger) {
            return [maxRow, mid];
        } else if (leftIsBigger) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return [-1, -1]; // Should not reach here
};