Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find a Peak Element II

MEDIUMProblemSolveExternal Links

Description

You are given a 0-indexed m x n matrix mat where no two adjacent cells are equal. Your task is to find any peak element and return its position as [i, j].

A cell mat[i][j] is considered a peak element if it is strictly greater than all of its adjacent neighbors — that is, the cells directly to its left, right, top, and bottom.

You may assume the entire matrix is surrounded by an imaginary outer border where every cell has the value -1. This means cells along the edges and corners have fewer neighbors to compare against, making it easier for them to qualify as peaks.

Key points:

  • A peak is a local maximum, not necessarily the global maximum of the entire matrix.
  • Multiple peaks may exist; returning any one of them is acceptable.
  • The algorithm must run in O(m log n) or O(n log m) time.
3x3 matrix with peak element 30 highlighted, showing all four neighbors are smaller
3x3 matrix with peak element 30 highlighted, showing all four neighbors are smaller

Examples

Example 1

Input: mat = [[1, 4], [3, 2]]

Output: [0, 1]

Explanation: The element mat[0][1] = 4 is a peak because:

  • Left neighbor: mat[0][0] = 1 < 4 ✓
  • Right neighbor: border (-1 < 4) ✓
  • Top neighbor: border (-1 < 4) ✓
  • Bottom neighbor: mat[1][1] = 2 < 4 ✓

Note: [1, 0] (value 3) is also a valid answer since 3 is also a peak.

Example 2

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

Output: [1, 1]

Explanation: The element mat[1][1] = 30 is a peak because all four neighbors are smaller: top=20, bottom=16, left=21, right=14. Alternatively, [2, 2] (value 32) is also valid — its right and bottom neighbors are borders (-1), and its left neighbor is 16 and top neighbor is 14, both smaller than 32.

Example 3

Input: mat = [[5]]

Output: [0, 0]

Explanation: The single element 5 has no neighbors (all four sides are borders with value -1). Since 5 > -1 in every direction, it is trivially a peak.

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 ≤ m, n ≤ 500
  • 1 ≤ mat[i][j] ≤ 10^5
  • No two adjacent cells are equal.

Editorial

Brute Force

Intuition

The most straightforward way to find a peak element is to check every single cell in the matrix. For each cell, we compare it to its four neighbors (top, bottom, left, right). If a neighbor is outside the matrix boundary, we treat it as -1, which is guaranteed to be less than any cell value (since values start at 1).

The moment we find a cell that is greater than all its valid neighbors, we have found a peak and can return its position immediately.

This approach is like walking through every room in a building and checking if the floor of that room is higher than all adjacent rooms. As soon as you find one, you stop.

Step-by-Step Explanation

Let's trace through mat = [[10, 20, 15], [21, 30, 14], [7, 16, 32]]:

Step 1: Check cell (0,0) = 10

  • Top: border (-1) → 10 > -1 ✓
  • Bottom: 21 → 10 > 21? ✗
  • Not a peak, move on.

Step 2: Check cell (0,1) = 20

  • Top: border (-1) → 20 > -1 ✓
  • Bottom: 30 → 20 > 30? ✗
  • Not a peak, move on.

Step 3: Check cell (0,2) = 15

  • Top: border (-1) → 15 > -1 ✓
  • Bottom: 14 → 15 > 14 ✓
  • Left: 20 → 15 > 20? ✗
  • Not a peak, move on.

Step 4: Check cell (1,0) = 21

  • Top: 10 → 21 > 10 ✓
  • Bottom: 7 → 21 > 7 ✓
  • Left: border (-1) → 21 > -1 ✓
  • Right: 30 → 21 > 30? ✗
  • Not a peak, move on.

Step 5: Check cell (1,1) = 30

  • Top: 20 → 30 > 20 ✓
  • Bottom: 16 → 30 > 16 ✓
  • Left: 21 → 30 > 21 ✓
  • Right: 14 → 30 > 14 ✓
  • Peak found! Return [1, 1].

Brute Force — Checking Every Cell for Peak — Scan every cell row by row. For each cell, compare against all four neighbors. Stop at the first cell that is strictly greater than all its neighbors.

Algorithm

  1. Iterate through every cell (i, j) in the matrix row by row.
  2. For each cell, retrieve the value mat[i][j].
  3. Compare it against all valid neighbors:
    • Top: mat[i-1][j] if i > 0, otherwise treat as -1.
    • Bottom: mat[i+1][j] if i < m-1, otherwise treat as -1.
    • Left: mat[i][j-1] if j > 0, otherwise treat as -1.
    • Right: mat[i][j+1] if j < n-1, otherwise treat as -1.
  4. If the cell value is strictly greater than all valid neighbors, return [i, j].
  5. If no peak is found after scanning the entire matrix (impossible given problem guarantees), return [-1, -1].

Code

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int curr = mat[i][j];
                bool isPeak = true;
                
                // Check top
                if (i > 0 && mat[i - 1][j] >= curr) isPeak = false;
                // Check bottom
                if (i + 1 < m && mat[i + 1][j] >= curr) isPeak = false;
                // Check left
                if (j > 0 && mat[i][j - 1] >= curr) isPeak = false;
                // Check right
                if (j + 1 < n && mat[i][j + 1] >= curr) isPeak = false;
                
                if (isPeak) return {i, j};
            }
        }
        return {-1, -1}; // unreachable given constraints
    }
};
class Solution:
    def findPeakGrid(self, mat: list[list[int]]) -> list[int]:
        m, n = len(mat), len(mat[0])
        
        for i in range(m):
            for j in range(n):
                curr = mat[i][j]
                is_peak = True
                
                # Check top
                if i > 0 and mat[i - 1][j] >= curr:
                    is_peak = False
                # Check bottom
                if i + 1 < m and mat[i + 1][j] >= curr:
                    is_peak = False
                # Check left
                if j > 0 and mat[i][j - 1] >= curr:
                    is_peak = False
                # Check right
                if j + 1 < n and mat[i][j + 1] >= curr:
                    is_peak = False
                
                if is_peak:
                    return [i, j]
        
        return [-1, -1]  # unreachable given constraints
class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int curr = mat[i][j];
                boolean isPeak = true;
                
                // Check top
                if (i > 0 && mat[i - 1][j] >= curr) isPeak = false;
                // Check bottom
                if (i + 1 < m && mat[i + 1][j] >= curr) isPeak = false;
                // Check left
                if (j > 0 && mat[i][j - 1] >= curr) isPeak = false;
                // Check right
                if (j + 1 < n && mat[i][j + 1] >= curr) isPeak = false;
                
                if (isPeak) return new int[]{i, j};
            }
        }
        return new int[]{-1, -1}; // unreachable given constraints
    }
}

Complexity Analysis

Time Complexity: O(m × n)

In the worst case, we visit every cell in the matrix before finding a peak. For each cell, we compare it against at most 4 neighbors, which is O(1) per cell. With m rows and n columns, the total number of cells is m × n, giving us O(m × n).

Space Complexity: O(1)

We only use a constant number of variables (i, j, curr, isPeak) regardless of the matrix size.

Why This Approach Is Not Efficient

The brute force approach checks every cell in the matrix, giving O(m × n) time complexity. With constraints allowing m, n up to 500, this means up to 250,000 cells — which is manageable, but the problem explicitly requires an O(m log n) or O(n log m) solution.

More importantly, the brute force wastes work. When we examine a cell and find it is not a peak (because a neighbor is larger), we simply move to the next cell without using that information. The key insight we're ignoring is: if a neighbor is larger than the current cell, then a peak must exist in the direction of that larger neighbor (because values can't increase forever due to the boundary). This directional information lets us eliminate entire rows or columns of cells at once, rather than checking them one by one.

Can we use this "move toward the larger value" idea more systematically? Binary search gives us a framework for eliminating half the search space at each step.

Optimal Approach - Binary Search on Rows

Intuition

The crucial insight comes from thinking about the 1D version first. In a 1D array, to find a peak element in O(log n), we pick the middle element and compare it with its neighbor. If the neighbor is larger, we move toward it — a peak is guaranteed to exist in that direction because values eventually hit the boundary (which is -1).

Now extend this to 2D. The trick is: binary search on the rows, and within each row, find the maximum element.

Here's why this works:

  1. Pick the middle row mid.
  2. Find the maximum element in that row, say at column j. Call it mat[mid][j].
  3. This element is already the largest in its row, so it's automatically greater than its left and right neighbors — we don't need to check those.
  4. Now we only need to check the top and bottom neighbors.
  5. Compare mat[mid][j] with mat[mid + 1][j] (the element directly below):
    • If mat[mid][j] > mat[mid + 1][j]: The peak could be in the current row or above. Why? Because mat[mid][j] already beats left, right, and below. If it also beats the top neighbor, it's a peak. If not, the element above is larger, so moving up leads toward larger values — and eventually the top boundary (-1) guarantees a peak exists in rows [0...mid]. Set right = mid.
    • If mat[mid][j] < mat[mid + 1][j]: The element below is larger, so moving down leads toward larger values. A peak must exist in rows [mid+1...m-1]. Set left = mid + 1.
  6. When left == right, we've narrowed down to one row. The maximum element in that row is guaranteed to be a peak.

This is like climbing a mountain by always walking toward higher ground — you're guaranteed to reach a summit because the boundary is at sea level.

Step-by-Step Explanation

Let's trace through mat = [[1, 4, 3, 2], [9, 5, 6, 7], [8, 10, 11, 12]] (3 rows × 4 columns):

Step 1: Initialize binary search boundaries.

  • left = 0, right = 2 (first and last row indices).

Step 2: Calculate mid row.

  • mid = (0 + 2) / 2 = 1.

Step 3: Find maximum element in row 1.

  • Row 1 = [9, 5, 6, 7]. Maximum is 9 at column 0.
  • maxCol = 0, mat[1][0] = 9.

Step 4: Compare with element below.

  • mat[mid + 1][maxCol] = mat[2][0] = 8.
  • Is 9 > 8? Yes! → Peak must be in rows [0...1]. Set right = 1.

Step 5: Calculate new mid row.

  • left = 0, right = 1. mid = (0 + 1) / 2 = 0.

Step 6: Find maximum element in row 0.

  • Row 0 = [1, 4, 3, 2]. Maximum is 4 at column 1.
  • maxCol = 1, mat[0][1] = 4.

Step 7: Compare with element below.

  • mat[mid + 1][maxCol] = mat[1][1] = 5.
  • Is 4 > 5? No → Peak must be in rows [1...1]. Set left = 1.

Step 8: Loop ends: left = right = 1.

  • Find maximum in row 1 = [9, 5, 6, 7]. Maximum is 9 at column 0.
  • Return [1, 0].

Verification: Is mat[1][0] = 9 a peak?

  • Left: border (-1) → 9 > -1 ✓
  • Right: mat[1][1] = 5 → 9 > 5 ✓
  • Top: mat[0][0] = 1 → 9 > 1 ✓
  • Bottom: mat[2][0] = 8 → 9 > 8 ✓
  • Yes, 9 is a valid peak! ✓

Binary Search on Rows — Finding a Peak — Watch how binary search picks the middle row, finds its max element, then eliminates half the rows by comparing with the element below. The search space shrinks logarithmically until one row remains.

Algorithm

  1. Set left = 0 and right = m - 1 (the first and last row indices).
  2. While left < right:
    a. Compute mid = (left + right) / 2.
    b. Scan row mid to find the column maxCol where the maximum element resides.
    c. Compare mat[mid][maxCol] with mat[mid + 1][maxCol]:
    • If mat[mid][maxCol] > mat[mid + 1][maxCol]: set right = mid (peak is in upper half including mid).
    • Else: set left = mid + 1 (peak is in lower half excluding mid).
  3. When left == right, find the maximum element in row left at column maxCol.
  4. Return [left, maxCol].

Code

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int left = 0, right = mat.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // Find column of max element in row mid
            int maxCol = 0;
            for (int j = 1; j < mat[mid].size(); j++) {
                if (mat[mid][j] > mat[mid][maxCol]) {
                    maxCol = j;
                }
            }
            
            // Compare with element below
            if (mat[mid][maxCol] > mat[mid + 1][maxCol]) {
                right = mid; // peak in upper half
            } else {
                left = mid + 1; // peak in lower half
            }
        }
        
        // Find max element in the final row
        int maxCol = 0;
        for (int j = 1; j < mat[left].size(); j++) {
            if (mat[left][j] > mat[left][maxCol]) {
                maxCol = j;
            }
        }
        
        return {left, maxCol};
    }
};
class Solution:
    def findPeakGrid(self, mat: list[list[int]]) -> list[int]:
        left, right = 0, len(mat) - 1
        
        while left < right:
            mid = (left + right) // 2
            
            # Find column of max element in row mid
            max_col = 0
            for j in range(1, len(mat[mid])):
                if mat[mid][j] > mat[mid][max_col]:
                    max_col = j
            
            # Compare with element below
            if mat[mid][max_col] > mat[mid + 1][max_col]:
                right = mid  # peak in upper half
            else:
                left = mid + 1  # peak in lower half
        
        # Find max element in the final row
        max_col = 0
        for j in range(1, len(mat[left])):
            if mat[left][j] > mat[left][max_col]:
                max_col = j
        
        return [left, max_col]
class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int left = 0, right = mat.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // Find column of max element in row mid
            int maxCol = 0;
            for (int j = 1; j < mat[mid].length; j++) {
                if (mat[mid][j] > mat[mid][maxCol]) {
                    maxCol = j;
                }
            }
            
            // Compare with element below
            if (mat[mid][maxCol] > mat[mid + 1][maxCol]) {
                right = mid; // peak in upper half
            } else {
                left = mid + 1; // peak in lower half
            }
        }
        
        // Find max element in the final row
        int maxCol = 0;
        for (int j = 1; j < mat[left].length; j++) {
            if (mat[left][j] > mat[left][maxCol]) {
                maxCol = j;
            }
        }
        
        return new int[]{left, maxCol};
    }
}

Complexity Analysis

Time Complexity: O(n × log m)

The binary search runs for O(log m) iterations, where m is the number of rows. In each iteration, we scan an entire row of n elements to find the maximum, costing O(n). Total: O(n × log m).

This satisfies the problem's requirement of O(m log n) or O(n log m). For a 500 × 500 matrix, this means roughly 500 × log₂(500) ≈ 500 × 9 ≈ 4,500 operations, compared to 250,000 for brute force.

Space Complexity: O(1)

We only use a constant number of variables (left, right, mid, maxCol) regardless of the matrix size. No extra data structures are needed.