{x}
blog image

Find a Peak Element II

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] <= 105
  • No two adjacent cells are equal.

1901. Find a Peak Element II

Problem Description

The problem asks to find a peak element in a 2D matrix. A peak element is an element that is strictly greater than all its adjacent neighbors (left, right, top, bottom). The matrix is surrounded by a perimeter of -1. The algorithm must run in O(m log n) or O(n log m) time.

This solution uses binary search to efficiently find a peak element. The approach leverages the property that if an element is not a peak, then at least one of its neighbors is larger. This allows us to iteratively narrow down the search space.

Algorithm:

  1. Binary Search on Rows: Perform binary search on the rows of the matrix.
  2. Find Row Maximum: In each iteration of the binary search, find the column index j of the maximum element in the current row mid.
  3. Compare with Neighbor: Compare the element mat[mid][j] with its bottom neighbor mat[mid + 1][j].
    • If mat[mid][j] > mat[mid + 1][j], then a peak must exist in the upper half of the matrix (rows 0 to mid). Update the right boundary r = mid.
    • Otherwise, a peak must exist in the lower half (rows mid + 1 to m-1). Update the left boundary l = mid + 1.
  4. Termination: The loop terminates when l == r. At this point, the row l contains a peak element. Find the column index of the maximum element in this row.
  5. Return Peak: Return the coordinates [l, j] of the peak element.

Time Complexity: O(n log m) (or O(m log n) if we perform binary search on columns instead). The binary search takes O(log m) iterations. In each iteration, finding the maximum element in a row takes O(n) time.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        l, r = 0, len(mat) - 1
        while l < r:
            mid = (l + r) // 2
            j = mat[mid].index(max(mat[mid]))  #Find index of max in row
            if mat[mid][j] > mat[mid + 1][j]:
                r = mid
            else:
                l = mid + 1
        j = mat[l].index(max(mat[l])) #Find index of max in final row
        return [l, j]

Explanation of Python code:

  • l and r are the left and right boundaries for the binary search on rows.
  • mid is the middle row index.
  • mat[mid].index(max(mat[mid])) efficiently finds the column index j of the maximum element in row mid. The max() function finds the maximum value and index() finds its index.
  • The comparison mat[mid][j] > mat[mid + 1][j] determines which half to search in the next iteration.
  • After the loop finishes, the row index l contains a peak. The code then finds the column index of the maximum value in that row.

Code Implementations in other languages

The logic remains the same across different languages. The primary differences lie in the syntax for array/list manipulation and finding the maximum element and its index. The examples below are provided without detailed comments as the algorithm is explained in detail above.

Java:

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

C++:

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int l = 0, r = mat.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            int j = max_element(mat[mid].begin(), mat[mid].end()) - mat[mid].begin();
            if (mat[mid][j] > mat[mid + 1][j]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int j = max_element(mat[l].begin(), mat[l].end()) - mat[l].begin();
        return {l, j};
    }
};

Go:

func findPeakGrid(mat [][]int) []int {
    l, r := 0, len(mat)-1
    for l < r {
        mid := (l + r) / 2
        j := maxPos(mat[mid])
        if mat[mid][j] > mat[mid+1][j] {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return []int{l, maxPos(mat[l])}
}
 
func maxPos(arr []int) int {
    maxIndex := 0
    for i := 1; i < len(arr); i++ {
        if arr[i] > arr[maxIndex] {
            maxIndex = i
        }
    }
    return maxIndex
}

Javascript:

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findPeakGrid = function(mat) {
    let l = 0, r = mat.length - 1;
    while (l < r) {
        let mid = Math.floor((l + r) / 2);
        let j = mat[mid].indexOf(Math.max(...mat[mid]));
        if (mat[mid][j] > mat[mid + 1][j]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    let j = mat[l].indexOf(Math.max(...mat[l]));
    return [l, j];
};

TypeScript:

function findPeakGrid(mat: number[][]): number[] {
    let l = 0, r = mat.length - 1;
    while (l < r) {
        let mid = Math.floor((l + r) / 2);
        let j = mat[mid].indexOf(Math.max(...mat[mid]));
        if (mat[mid][j] > mat[mid + 1][j]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    let j = mat[l].indexOf(Math.max(...mat[l]));
    return [l, j];
}

Rust:

impl Solution {
    pub fn find_peak_grid(mat: Vec<Vec<i32>>) -> Vec<i32> {
        let mut l = 0;
        let mut r = mat.len() - 1;
        while l < r {
            let mid = (l + r) / 2;
            let j = mat[mid].iter().enumerate().max_by_key(|&(_, x)| x).unwrap().0;
            if mat[mid][j] > mat[mid + 1][j] {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        let j = mat[l].iter().enumerate().max_by_key(|&(_, x)| x).unwrap().0;
        vec![l as i32, j as i32]
    }
}

These examples showcase the adaptability of the binary search approach across various programming languages, highlighting the core algorithmic efficiency. Remember to adapt the code based on the specific requirements of your coding environment and chosen language.