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:

1. Pick the middle row of the current search interval and find the column index of its maximum element, say it's at column j.
2. 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.
3. 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.
4. 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.
5. 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:

1. 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).

2. 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.

3. 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.

4. 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).

5. 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.

6. 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.

7. 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]))]

Example Walkthrough

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

Suppose we have the following 3x4 matrix mat:

13  4 5 6
22  3 8 5
31 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

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.