1901. Find a Peak Element II

Problem Description

In this problem, we are given a 2D grid mat which is represented by an m x n matrix, where m is the number of rows and n is the number of columns. The task is to find a peak element in this grid. A peak element is defined as one that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom. The twist here is that this must be achieved under a strict time complexity of either O(m log(n)) or O(n log(m)), which means we cannot simply iterate over each element of the grid.

To make the problem more challenging, there are a few constraints:

The matrix uses zero-based indexing, which is a common representation for arrays and grids in programming.
Adjacent cells in the matrix are guaranteed to have different values (no two adjacent cells are equal), simplifying the search for peak elements since a peak won't be 'flanked' by equal values.
The entire matrix is imagined to be surrounded by an outer perimeter with the value -1 in each cell, ensuring that edge elements can also be considered peaks if they are greater than all their in-bounds neighbors.

The output of the problem should be the coordinates [i, j] of any peak element, in the form of a two-element array.

Intuition

To find a peak element efficiently without checking every single element in the matrix, we can leverage the fact that a row's maximum element is greater than the elements directly to its left and right (since no two adjacent elements are equal). Then the idea is to identify if this maximum element is also a peak in the vertical direction. To exploit this property, binary search comes into play, as it allows us to significantly reduce the number of elements we inspect in order to find a peak.

We apply binary search with the following reasoning:

Pick the middle row of the current search interval and find the column index of its maximum element, say it's at column j.
Now check the element just above (if it exists) and below the maximum element found in the middle row. This is essentially checking whether this maximum element is also greater than its top and bottom adjacent cells.
If the element is greater than the element below (the element in the next row, same column), then a peak must exist in the upper part of the search interval, so we reduce the search interval to the upper half.
If the element is less than the element below, then a peak must exist in the lower part of the search interval, so we adjust the search interval to the lower half.
Continue this approach recursively until we narrow the search down to one row, then the maximum element in that row will be a peak element, because it is greater than its left and right neighbors by the definition of the maximum, and it is also greater than any top and bottom neighbor due to the binary search process.

This methodology guarantees that we find a peak in O(m log(n)) time if the binary search is applied on rows (for every row picked, we find the max in O(n) time), or O(n log(m)) time if applied on columns (again, finding the max in each column within O(m) time). The solution's effectiveness comes from never having to check all the elements and using the binary search to repeatedly halve the search space.

Learn more about Binary Search patterns.

Solution Approach

To implement the solution to find a peak element in the matrix, we utilize binary search owing to its logarithmic time complexity, which fits the problem's requirement. The reference solution approach outlines a methodical strategy that uses binary search in a non-standard way, adapted to a 2D context.

Here's the step-by-step implementation breakdown:

Initialize Search Space: We start by defining the search space as the entire set of rows in the matrix with l (left) being the first row index (0) and r (right) being the last row index (len(mat) - 1).
Binary Search on Rows: We apply binary search on the row indices. The loop continues as long as l < r, implying that we have more than one row remaining in our search space.
Find Local Maximum in Row: In every iteration of the binary search, we calculate the middle row index mid between l and r. Then we find the column index j of the maximum value in the midth row using max(mat[mid]) and its associated index method index(). The column index j of this maximum value effectively serves as a candidate for the peak's column index.
Compare with the Element Below: We compare the found maximum value mat[mid][j] with the value directly below it mat[mid + 1][j] (since the matrix is surrounded by -1, we are assured that there are no out-of-bound issues).
Adjust Search Space: If mat[mid][j] is greater, then a peak must exist at or above this row, and we set r = mid. If not, a peak must be below it, and we update l = mid + 1.
Convergence: When l equals r, the while loop exits, indicating that we have narrowed down to a single row. Now, the maximum element of this row mat[l] is guaranteed to be a peak element, since it is greater than its left and right neighbors (as it is the maximum), and the binary search ensures it's greater than any top and bottom neighbors.
Return Coordinates: Finally, the coordinates of the peak element are the row index l and the column index of the maximum value in the lth row, found using mat[l].index(max(mat[l])). The function then returns [l, j_l].

The algorithm is efficient due to the binary search, and it effectively adheres to the required time complexity by limiting the elements it inspects in each iteration. No additional data structures are necessary, as we are simply manipulating indices and comparing elements directly within the given matrix.

Now, let's enclose key variables and code references within backticks to follow proper markdown convention for code formatting:

Initialize search space: l = 0, r = len(mat) - 1
Loop condition: while l < r
Find local maximum: j = mat[mid].index(max(mat[mid]))
Compare with element below: if mat[mid][j] > mat[mid + 1][j]
Adjust search space: r = mid or l = mid + 1
Convergence to single row: when l == r
Return coordinates: [l, mat[l].index(max(mat[l]))]

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have the following 3x4 matrix mat:

3  4 5 6
2  3 8 5
1 10 2 3

Step 1: Initialize Search Space

Here, l = 0 and r = 2 because we have three rows in total (0-indexed).

Step 2: Binary Search on Rows

We start with l < r, so we need to apply the binary search.

Step 3: Find Local Maximum in Mid Row

Calculate the middle row, mid = (l + r) // 2 (using integer division). Initially, l = 0 and r = 2, so mid = 1.

Now, we find the maximum in the middle row mat[1], which is 8 at column index j = 2.

Step 4: Compare with Element Below

We compare the value mat[mid][j] with the value directly below it mat[mid + 1][j].

In this case, mat[mid][j] = 8 and mat[mid + 1][j] = 2. Since 8 is greater than 2, we are on the right path.

Step 5: Adjust Search Space

As our comparison shows that mat[mid][j] is greater than mat[mid + 1][j], we set r = mid, which is now r = 1.

Step 6: Convergence

The loop continues, and now we find that l = r, meaning we are focused on a single row, which is the first one.

Step 7: Return Coordinates

We then find the maximum in the 1st row, mat[l], which is 10 at column j_l = 1.

So finally, we return the coordinates [l, j_l], which gives us [1, 1], as the peak element's position.

Putting it into the code context:

Updated search space: r = 1
Loop termination: l = r = 1
Final peak element's coordinates: [1, 1]

This example demonstrates the complete process from initialization to narrowing down the search interval using binary search until finding a peak element, without ever needing to check each element individually.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findPeakGrid(self, matrix: List[List[int]]) -> List[int]:
5        # Define the row boundaries for the search
6        low, high = 0, len(matrix) - 1
7      
8        # Continue the binary search while the search space has more than 1 row
9        while low < high:
10            mid = (low + high) // 2  # Find the middle row
11            max_col_index = matrix[mid].index(max(matrix[mid]))  # Find the column index of the maximum element in the middle row
12          
13            # Compare the max element of mid row with the element directly below it in the next row
14            if matrix[mid][max_col_index] > matrix[mid + 1][max_col_index]:
15                high = mid  # The peak lies on or before the mid row
16            else:
17                low = mid + 1  # The peak lies after the mid row
18      
19        # After exiting the loop, 'low' is the row where the peak element is located
20        # Find the column index of the maximum element in the 'low' row
21        peak_col_index = matrix[low].index(max(matrix[low]))
22      
23        # Return the position [row, column] of the peak element
24        return [low, peak_col_index]
25
26# Example usage:
27# sol = Solution()
28# print(sol.findPeakGrid([[1, 4], [3, 2]]))  # Output would be [0, 1], since 4 is the peak in this case
29

1class Solution {
2    public int[] findPeakGrid(int[][] matrix) {
3        // Initialize left and right pointers for the binary search on rows
4        int left = 0, right = matrix.length - 1;
5        // Get the number of columns for later use
6        int columns = matrix[0].length;
7
8        // Using binary search to find the peak row
9        while (left < right) {
10            int mid = (left + right) / 2; // Find the middle index between left and right
11            int maxColumnIndex = findMaxPosition(matrix[mid]); // Find the index of the peak in the middle row
12
13            // Compare the peak element with the one right below it
14            if (matrix[mid][maxColumnIndex] > matrix[mid + 1][maxColumnIndex]) {
15                // If it's bigger, move the right pointer to the middle row
16                right = mid;
17            } else {
18                // If it's not bigger, move the left pointer to one row below the middle row
19                left = mid + 1;
20            }
21        }
22
23        // After exiting the loop, 'left' is the index of the peak row. We find the column index of the peak in that row
24        return new int[] {left, findMaxPosition(matrix[left])};
25    }
26
27    // Helper function to find the index of the maximum element in a given array (row)
28    private int findMaxPosition(int[] row) {
29        int maxIndex = 0; // Assume the first element is the maximum initially
30        // Iterate through the array
31        for (int i = 1; i < row.length; ++i) {
32            if (row[maxIndex] < row[i]) {
33                // If we find a bigger element, update the index
34                maxIndex = i;
35            }
36        }
37        // Return the index of the largest element in the row
38        return maxIndex;
39    }
40}
41

1class Solution {
2public:
3    vector<int> findPeakGrid(vector<vector<int>>& matrix) {
4        int left = 0; // Start index of the row search space
5        int right = matrix.size() - 1; // End index of the row search space
6
7        // Keep searching as long as the search space has more than one row
8        while (left < right) {
9            int mid = (left + right) / 2; // Find the mid index of the current search space
10
11            // Find the column index of the maximum element in the middle row
12            int maxColIndex = max_element(matrix[mid].begin(), matrix[mid].end()) - matrix[mid].begin();
13
14            // If the maximum element in the middle row is also a peak element
15            if (matrix[mid][maxColIndex] > matrix[mid + 1][maxColIndex]) {
16                // Peak element must be in the upper half of the matrix
17                right = mid;
18            } else {
19                // Peak element must be in the lower half of the matrix
20                left = mid + 1;
21            }
22        }
23      
24        // After the while loop, left == right, and it points to the peak row
25        // Find the column index of the maximum element in the peak row
26        int peakColIndex = max_element(matrix[left].begin(), matrix[left].end()) - matrix[left].begin();
27
28        // Return the position (row, column) of the peak element
29        return {left, peakColIndex}; 
30    }
31};
32

1function findPeakGrid(mat: number[][]): number[] {
2    let leftBound = 0; // Left boundary of the search space
3    let rightBound = mat.length - 1; // Right boundary of the search space
4
5    // Perform a binary search in the direction of the peak's row
6    while (leftBound < rightBound) {
7        let midRow = leftBound + Math.floor((rightBound - leftBound) / 2); // Middle index of the current search space
8        let maxElementColIndex = mat[midRow].indexOf(Math.max(...mat[midRow])); // Column index of max element in the middle row
9
10        // Compare the middle element with the one below it
11        if (mat[midRow][maxElementColIndex] > mat[midRow + 1][maxElementColIndex]) {
12            // If the middle element is greater, then the peak cannot be in the lower half, move the rightBound down
13            rightBound = midRow;
14        } else {
15            // If the middle element is not greater, then the peak is in the lower half, move the leftBound up
16            leftBound = midRow + 1;
17        }
18    }
19
20    // leftBound will be the row where the peak element is present
21    // Find the column index of the maximum element in the peak row
22    let peakColIndex = mat[leftBound].indexOf(Math.max(...mat[leftBound]));
23
24    // Return the coordinates of the peak
25    return [leftBound, peakColIndex];
26}
27

Time and Space Complexity

The time complexity of the provided code is O(n * log m), where m is the number of rows and n is the number of columns in the matrix mat. This stems from using binary search on the rows, which has a complexity of O(log m), combined with finding the maximum element in each middle row, which takes O(n). Since these operations are done for each step of the binary search, they result in the mentioned time complexity.

The space complexity of the code is O(1), indicating constant extra space usage irrespective of the input size. This is because the algorithm only uses a fixed amount of auxiliary space for variables like l, r, mid, and j, regardless of the dimensions of the input matrix.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know