We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find a Peak Element II

Difficulty: Medium

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

Key Insights

  • A peak element is defined as an element that is greater than its adjacent neighbors.
  • The problem guarantees that no two adjacent cells are equal, simplifying the comparison process.
  • The algorithm can leverage binary search to efficiently find a peak element in logarithmic time.
  • The matrix is surrounded by an outer boundary, ensuring that edge elements can still be compared safely.

Space and Time Complexity

Time Complexity: O(m log(n)) or O(n log(m))
Space Complexity: O(1) (the algorithm uses a constant amount of space)

Solution

To find a peak element, we can use a binary search approach. The idea is to pick the middle column of the matrix and find the maximum element in that column. This maximum element will either be a peak itself or will have a neighbor that is greater than it. If it has a neighbor that is greater, we can move our search to the side of the matrix where that neighbor is located. By repeatedly applying this process, we can efficiently converge to a peak element. This approach takes advantage of the matrix's properties and the fact that we only need to check one direction (left or right) based on the maximum found.

Code Solutions

def findPeakGrid(mat):
    m, n = len(mat), len(mat[0])
    
    def findMaxInColumn(col):
        max_row = 0
        for i in range(m):
            if mat[i][col] > mat[max_row][col]:
                max_row = i
        return max_row

    left, right = 0, n - 1
    while left <= right:
        mid = left + (right - left) // 2
        max_row = findMaxInColumn(mid)

        # Check neighbors
        if (mid == 0 or mat[max_row][mid] > mat[max_row][mid - 1]) and \
           (mid == n - 1 or mat[max_row][mid] > mat[max_row][mid + 1]):
            return [max_row, mid]  # Found a peak
        elif mid > 0 and mat[max_row][mid - 1] > mat[max_row][mid]:
            right = mid - 1  # Move left
        else:
            left = mid + 1  # Move right
← Back to All Questions