FastPrep
Problem · Matrix

Find All Local Maximums

Learn this problem
● MediumMeta logoMetaINTERNOA
See Meta hiring insights

Problem statement

See the Image Source section at the very bottom of the page for the original problem statemetn :)

Given a matrix of integers, your task is to find all local maximums. An element is considered a local maximum if it is non-zero and no greater or equal elements exist within its defined region. The region for an element at matrix[i][j] is a square centered at (i, j) with a side length of (matrix[i][j] * 2 + 1), excluding the square's corners. For example, if matrix[2][2] is the element, the region would be a 5x5 square (as (matrix[2][2] * 2 + 1) equals 5), with only non-corner elements considered. If part of the region falls outside the matrix, only the portion within the matrix is evaluated. Your task is to return a 2D array containing the coordinates [row, col] of each local maximum, sorted first by row and then by column in case of ties. While an optimal solution isn’t required, the solution should have a time complexity no worse than O(matrix.length² * matrix[0].length²).

˚˖𓍢ִ໋🌷͙֒✧˚Endless thanks to Charlotte baby.🎀༘⋆C

Function

findAllLocalMaximums(matrix: int[][]) → int[][]

Examples

Example 1

matrix = [[3,0,0,0,0],[0,0,1,0,0],[0,0,2,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,3,0,0,3]]return = [[0,0],[2,2]]

The value 3 at [0,0] has no greater or equal value in the in-bounds portion of its region. For the value 2 at [2,2], the larger value at [0,0] is one of the four excluded corners, and the remaining values in its region are smaller. The other non-zero cells are disqualified by a greater or equal value in their regions.

More Meta problems

drafts saved locally
public int[][] findAllLocalMaximums(int[][] matrix) {
  // write your code here
}
matrix[[3,0,0,0,0],[0,0,1,0,0],[0,0,2,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,3,0,0,3]]
expected[[0,0],[2,2]]
checking account