Find a Peak Element II - Practice Coding Problems

Find a Peak Element II - Problem

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.

Input & Output

Example 1 — Basic 3x3 Matrix

$ Input: mat = [[1,4,3,2,0],[2,7,6,1,3],[5,0,1,4,8]]

› Output: [1,2]

💡 Note: Element at [1,2] is 6. It's greater than neighbors: 6 > 4 (top), 6 > 7 is false... Actually, 7 at [1,1] is greater than all neighbors: 7 > 4, 7 > 2, 7 > 6, 7 > 0. So return [1,1].

Example 2 — Single Peak

$ Input: mat = [[10,20,15],[21,30,14],[7,16,32]]

› Output: [1,1]

💡 Note: Element 30 at [1,1] is greater than all neighbors: 30 > 20, 30 > 21, 30 > 14, 30 > 16

Example 3 — Corner Peak

$ Input: mat = [[1,2],[3,4]]

› Output: [1,1]

💡 Note: Element 4 at [1,1] is greater than all neighbors: 4 > 3, 4 > 2. Boundary cells have value -1.

Constraints

m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 500
-10⁵ ≤ mat[i][j] ≤ 10⁵
No two adjacent cells are equal

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D grid where we need to find any peak element

Peak Definition

Element greater than all 4 neighbors (left, right, top, bottom)

Output

Return coordinates [row, col] of any peak element

Key Takeaway

🎯 Key Insight: Use binary search to eliminate half the search space by comparing column maximums with their neighbors

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is using binary search to eliminate columns by comparing the maximum element in the middle column with its neighbors. The optimal binary search approach achieves O(m log n) time complexity by intelligently reducing the search space. Time: O(m log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Element	O(mn)	O(1)	Check every element against its 4 neighbors to find a peak
Binary Search on Columns	O(m log n)	O(1)	Use binary search on columns and find max element in middle column

Brute Force - Check Every Element — Algorithm Steps

Iterate through each cell (i,j)
Check if mat[i][j] > all 4 neighbors
Return [i,j] when peak found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at mat[0][0]

Check Neighbors

Compare with left, right, top, bottom

Found Peak

Return coordinates when element > all neighbors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int mat[][100], int m, int n, int* result) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int isPeak = 1;
            
            // Check all 4 neighbors
            if (j > 0 && mat[i][j] <= mat[i][j-1]) isPeak = 0;
            if (j < n-1 && mat[i][j] <= mat[i][j+1]) isPeak = 0;
            if (i > 0 && mat[i][j] <= mat[i-1][j]) isPeak = 0;
            if (i < m-1 && mat[i][j] <= mat[i+1][j]) isPeak = 0;
            
            if (isPeak) {
                result[0] = i;
                result[1] = j;
                return;
            }
        }
    }
    
    result[0] = 0;
    result[1] = 0;
}

int main() {
    int mat[100][100];
    int m = 0, n = 0;
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small matrices
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                mat[m][n++] = atoi(ptr);
                while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                if (*ptr == ',') ptr++;
            }
            m++;
        }
        ptr++;
    }
    
    int result[2];
    solution(mat, m, n, result);
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

We check every cell in the m×n matrix once

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

28.5K Views

Medium-High Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Element — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler