Formatted question description: https://leetcode.ca/all/1901.html

1901. Find a Peak Element II

Level

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:

Image text

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:

Image text

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^5
  • No two adjacent cells are equal.

Solution

Use binary search. Initialize low = 0 and high = m - 1. Each time let mid be the mean of low and high, and find maxIndex such that mat[mid][maxIndex] is the greatest element in the row mat[mid]. If mat[mid][maxIndex] < mat[mid + 1][maxIndex], then let low = mid + 1. Otherwise, let high = mid.

When the row is determined using binary search, find the greatest element in the row and get the column index of the greatest element. Return the row index and the column index.

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int low = 0, high = m - 1, maxIndex = 0;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            maxIndex = getMaxIndex(mat[mid], n);
            if (mat[mid][maxIndex] < mat[mid + 1][maxIndex])
                low = mid + 1;
            else
                high = mid;
        }
		maxIndex = getMaxIndex(mat[low], n);
        return new int[]{low, maxIndex};
    }
    
    public int getMaxIndex(int[] arr, int n) {
        int index = 0, maxNum = 0;
        for (int i = 0; i < n; i++) {
            if (maxNum < arr[i]) {
                maxNum = arr[i];
                index = i;
            }
        }
        return index;
    }
}

All Problems

All Solutions