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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find a Peak Element II

Number: 2047

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, TikTok, Bloomberg, Xing

Problem Description

Given a 0-indexed m x n matrix where no two adjacent cells are equal and the matrix is implicitly surrounded by an outer perimeter with the value -1, find any peak element. A peak element is defined as one that is strictly greater than its adjacent neighbors (up, down, left, and right). Return the coordinates [i, j] of any peak element. The solution must run in O(m log(n)) or O(n log(m)) time.

Key Insights

  • The problem can be solved using a binary search approach along one of the dimensions (rows or columns).
  • For a chosen mid row (or column), find the global maximum element in that row.
  • By comparing the maximum element with its top and bottom neighbors, decide in which half to continue the search.
  • Because no two adjacent cells are equal and considering the -1 border, a peak is guaranteed to be found.

Space and Time Complexity

Time Complexity: O(m log(n)) (if binary search is performed on rows) or O(n log(m)) (if binary search is performed on columns) Space Complexity: O(1) (in-place with only constant extra space)

Solution

We use a binary search based algorithm on rows. At each step, we choose a mid row and scan that row to find the maximum element (its column index). Then, we compare this element with its top and bottom neighbors (if available). If the element is greater than both, it's a peak. Otherwise, if the neighbor above or below is greater, we continue the search in that direction. This guarantees that we converge to a peak element. The main trick is performing a binary search on one dimension while scanning the other dimension completely to find a local maximum, thus reducing the overall search space.

Code Solutions

# Python solution using binary search on rows

def findPeakGrid(mat):
    # Get the dimensions of the matrix
    m, n = len(mat), len(mat[0])
    
    # Binary search on rows
    top, bottom = 0, m - 1
    while top <= bottom:
        mid_row = (top + bottom) // 2
        
        # Find the column index with the maximum element in the mid_row
        max_col = 0
        for j in range(n):
            if mat[mid_row][j] > mat[mid_row][max_col]:
                max_col = j
        
        # Check the top and bottom neighbors (using -1 for out-of-bound)
        up_val = mat[mid_row - 1][max_col] if mid_row - 1 >= 0 else -1
        down_val = mat[mid_row + 1][max_col] if mid_row + 1 < m else -1
        
        # If the mid element is greater than its neighbors, return its position
        if mat[mid_row][max_col] > up_val and mat[mid_row][max_col] > down_val:
            return [mid_row, max_col]
        # If the top neighbor is greater, move up
        elif up_val > mat[mid_row][max_col]:
            bottom = mid_row - 1
        # Else if the bottom neighbor is greater, move down
        else:
            top = mid_row + 1

# Example usage:
# print(findPeakGrid([[10,20,15],[21,30,14],[7,16,32]]))
← Back to All Questions