2047. Find A Peak Element Ii¶

LeetCode Problem View on GitHub

2047. Find a Peak Element II

Medium

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.

Solution¶

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int low = 0, high = m - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int maxR = -1, maxEle = -1;
            for (int i = 0; i < n; i++) {
                if (mat[i][mid] > maxEle) {
                    maxEle = mat[i][mid];
                    maxR = i;
                }
            }   

            int left = -1, right = -1;
            if (mid - 1 >= 0) 
                left = mat[maxR][mid - 1];
            if (mid + 1 < m) 
                right = mat[maxR][mid + 1];
            if (mat[maxR][mid] > left && mat[maxR][mid] > right) 
                return new int[]{maxR, mid};
            else {
                if (right > mat[maxR][mid])
                    low = mid + 1;
                else 
                    high = mid - 1;
            } 
        }
        return new int[]{-1, -1};
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here