Find a Peak Element II

MEDIUM

Description

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.

Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].

You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.

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

Example 1:

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Example 2:

Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 10⁵
No two adjacent cells are equal.

Approaches

Checkout 2 different approaches to solve Find a Peak Element II. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves iterating through every cell of the matrix and checking if it's a peak element. A cell is a peak if it is strictly greater than all its four adjacent neighbors (top, bottom, left, and right).

Algorithm

Iterate through each row i from 0 to m-1.
Inside the row loop, iterate through each column j from 0 to n-1.
For the current cell mat[i][j], get the values of its four neighbors, treating out-of-bounds neighbors as -1.
Check if mat[i][j] is strictly greater than all four neighbors.
If it is, return the coordinates [i, j].

The algorithm iterates through each cell (i, j) from (0, 0) to (m-1, n-1). For each cell mat[i][j], we compare its value with its four neighbors. The neighbors are mat[i-1][j] (top), mat[i+1][j] (bottom), mat[i][j-1] (left), and mat[i][j+1] (right). We must handle boundary conditions. The problem simplifies this by stating the matrix is surrounded by an outer perimeter with the value -1. So, if a neighbor is outside the matrix bounds, its value is considered -1. If mat[i][j] is strictly greater than all its existing neighbors, it is a peak, and we return its coordinates [i, j]. Since the problem guarantees that a peak always exists, this method will eventually find and return one.

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 currentVal = mat[i][j];
                int top = (i > 0) ? mat[i - 1][j] : -1;
                int bottom = (i < m - 1) ? mat[i + 1][j] : -1;
                int left = (j > 0) ? mat[i][j - 1] : -1;
                int right = (j < n - 1) ? mat[i][j + 1] : -1;

                if (currentVal > top && currentVal > bottom && currentVal > left && currentVal > right) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1}; // Should not be reached as per problem statement
    }
}

Complexity Analysis

Time Complexity: O(m * n), where `m` is the number of rows and `n` is the number of columns. In the worst case, we might have to scan the entire matrix.Space Complexity: O(1), as we only use a constant amount of extra space for variables.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient for large matrices and does not meet the time complexity requirement of the problem, which is O(m log(n)) or O(n log(m)).

Code Solutions

Checking out 3 solutions in different languages for Find a Peak Element II. Click on different languages to view the code.

class Solution { public int [] findPeakGrid ( int [][] mat ) { int l = 0 , r = mat . length - 1 ; int n = mat [ 0 ]. length ; while ( l < r ) { int mid = ( l + r ) >> 1 ; int j = maxPos ( mat [ mid ]); if ( mat [ mid ][ j ] > mat [ mid + 1 ][ j ]) { r = mid ; } else { l = mid + 1 ; } } return new int [] { l , maxPos ( mat [ l ])}; } private int maxPos ( int [] arr ) { int j = 0 ; for ( int i = 1 ; i < arr . length ; ++ i ) { if ( arr [ j ] < arr [ i ]) { j = i ; } } return j ; } }

Video Solution

Watch the video walkthrough for Find a Peak Element II

Algorithms:

Binary Search

Data Structures:

ArrayMatrix

Companies:

Zeta |