Find A Peak Element Ii - Leetcode Solution

Problem Statement: A peak element in a two-dimensional array is an element that is greater than or equal to its four neighbors, left, right, top and bottom.

For example, in the picture below, the peak element is 9:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Find all peak elements in a given two-dimensional array. Return their indices as a list of lists.

Solution Approach:

To solve this problem, we need to find out all the local maximums or peak elements in the input matrix. For this purpose, we can apply a recursive divide-and-conquer approach by dividing the matrix into smaller sub-matrices at each step and finding the peak element in each sub-matrix. The peak element in a sub-matrix will be the element that is maximum among the elements in the sub-matrix and its neighbors. We can recur on the sub-matrix that contains the peak element until we reach the smallest sub-matrix where we can directly find the peak element. Finally, we can combine all the peak elements obtained from various sub-matrices to get the final answer.

Algorithm:

1. Define a recursive function findPeakElements() that takes the input matrix, row and column indices of the top-left and bottom-right corners of the sub-matrix as input.

2. If the sub-matrix contains only one element, return the index of the element as the peak element.

3. Calculate the middle column index midCol = (startCol + endCol) / 2.

4. Find the maximum element maxElement in the midCol-th column of the sub-matrix.

5. Find the row index maxRow of the maximum element maxElement in the midCol-th column.

6. If maxElement is greater than the elements in both of its adjacent columns, then maxElement is a peak element, return its index (maxRow, midCol).

7. Otherwise, if the element to the left of maxElement is greater than maxElement, then recur on the left half of the sub-matrix (findPeakElements(matrix, startRow, startCol, endRow, midCol-1)).

8. Otherwise, if the element to the right of maxElement is greater than maxElement, then recur on the right half of the sub-matrix (findPeakElements(matrix, startRow, midCol+1, endRow, endCol)).

9. If maxElement is not a peak element and we do not have any unexplored sub-matrix, then return an empty list.

10. Finally, combine all the peak elements obtained from various sub-matrices and return the final list.

Pseudo Code:

def findPeakElements(matrix, startRow, startCol, endRow, endCol):
    # Base Case: Sub-matrix contains only one element
    if startRow == endRow and startCol == endCol:
        return [[startRow, startCol]]
    
    # Calculate the middle column index
    midCol = (startCol + endCol) // 2
    
    # Find the maximum element in the midCol-th column of sub-matrix
    maxElement = matrix[startRow][midCol]
    maxRow = startRow
    for i in range(startRow, endRow+1):
        if matrix[i][midCol] > maxElement:
            maxElement = matrix[i][midCol]
            maxRow = i
    
    # If maxElement is a peak element, return its index
    if ((midCol == 0 or matrix[maxRow][midCol-1] <= maxElement) and 
        (midCol == len(matrix[0])-1 or matrix[maxRow][midCol+1] <= maxElement) and 
        (maxRow == 0 or matrix[maxRow-1][midCol] <= maxElement) and 
        (maxRow == len(matrix)-1 or matrix[maxRow+1][midCol] <= maxElement)):
        return [[maxRow, midCol]]
    
    # Recur on the left half of the sub-matrix
    if midCol > 0 and matrix[maxRow][midCol-1] > maxElement:
        return findPeakElements(matrix, startRow, startCol, endRow, midCol-1)
    
    # Recur on the right half of the sub-matrix
    if midCol < len(matrix[0])-1 and matrix[maxRow][midCol+1] > maxElement:
        return findPeakElements(matrix, startRow, midCol+1, endRow, endCol)
    
    # No peak element found in the sub-matrix
    return []

def findPeakElements2D(matrix):
    return findPeakElements(matrix, 0, 0, len(matrix)-1, len(matrix[0])-1)

Time Complexity: The time complexity of the above recursive divide-and-conquer algorithm is O(N * logM) where N is the total number of elements in the input matrix and logM is the number of times we can halve the matrix size and search for the peak element. The worst-case time complexity occurs when the input matrix is a square matrix where logM is logN (base 2).

Space Complexity: The space complexity of the above recursive divide-and-conquer algorithm is O(logM) where logM is the maximum depth of the recursion tree.

1