Find a peak element II

Problem Link

Find-a-peak-element-ii

Problem Statement

A peak element in a 2D grid is an element that is strictly greater than its four possible neighbors (up, down, left, right). Given a 2D matrix mat where mat[i][j] != mat[i+1][j] and mat[i][j] != mat[i][j+1] (no two adjacent elements are equal), return any peak element’s position as a 2-element array [row, col].

You must implement an algorithm that runs in O(m log n) or O(n log m) time complexity.

Examples

Example 1:

Input:
mat = [[1,4], [3,2]]
Output: [0,1]
Explanation: mat[0][1] = 4 is a peak because it is greater than its neighbors.

Example 2:

Input:
mat = [[10,20,15], [21,30,14], [7,16,32]]
Output: [1,1] or [2,2]
Explanation: Both mat[1][1]=30 and mat[2][2]=32 are valid peaks.

Constraints

• 1 <= mat.length, mat[i].length <= 500

• All adjacent cells are distinct

Intuition

In a 1D array, a binary search-like strategy can find a peak in O(log n).
To extend this to 2D:

• Fix one column, find the global max in that column.

• Compare that element with its left and right neighbors.

• Use the comparison to decide whether to move left or right — just like binary search.

This way, we reduce the search space in half on each step in terms of columns, giving us a binary search on columns.

Approach (Column-wise Binary Search)

1. Let startCol = 0, endCol = n - 1 (where n is the number of columns).

2. While startCol <= endCol:

   • Find midCol = (startCol + endCol) / 2.

   • For this column, find the row with the maximum value in that column (maxRow).

   • Check the left and right neighbors:

     • If mat[maxRow][midCol] < mat[maxRow][midCol - 1], move left (endCol = midCol - 1)

     • If mat[maxRow][midCol] < mat[maxRow][midCol + 1], move right (startCol = midCol + 1)

     • Else, it's a peak → return [maxRow, midCol]

Java Code

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int startCol = 0, endCol = n - 1;

        while (startCol <= endCol) {
            int midCol = startCol + (endCol - startCol) / 2;

            // Find the max element in the middle column
            int maxRow = 0;
            for (int row = 0; row < m; row++) {
                if (mat[row][midCol] > mat[maxRow][midCol]) {
                    maxRow = row;
                }
            }

            int left = (midCol - 1 >= 0) ? mat[maxRow][midCol - 1] : -1;
            int right = (midCol + 1 < n) ? mat[maxRow][midCol + 1] : -1;

            if (mat[maxRow][midCol] >= left && mat[maxRow][midCol] >= right) {
                return new int[]{maxRow, midCol};
            } else if (left > mat[maxRow][midCol]) {
                endCol = midCol - 1;
            } else {
                startCol = midCol + 1;
            }
        }

        return new int[]{-1, -1}; // Should not reach here as per problem constraints
    }
}

Time and Space Complexity

• Time Complexity: O(m * log n)
  For each binary search step on columns (log n steps), we scan all m rows to find the max in that column.

• Space Complexity: O(1)
  We use only a constant number of variables.

Dry Run

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

1. Columns: startCol = 0, endCol = 2, midCol = 1

2. Find max in col 1:

   • col[1] = [20, 30, 16] → max = 30 at row 1

3. Check left = 21 (col 0), right = 14 (col 2)

4. 30 > left and right → return [1, 1]

Conclusion

This problem is a classic example of optimizing 2D matrix search using binary search over rows or columns. The key idea is to narrow the search space by comparing only relevant neighbors, making the algorithm efficient even for large matrices.

If you see a matrix where each row and column is not necessarily sorted but you're asked to find a peak, this column-wise binary search pattern is a powerful tool to apply.