LeetCode Entry
2373. Largest Local Values in a Matrix
Max pooling by 3x3 matrix
2373. Largest Local Values in a Matrix easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/600
Problem TLDR
Max pooling by 3x3 matrix #easy
Intuition
The easiest way is to just iterate over the neighbours each time. (However one can possible find an algorithm to do a running-max with a monotonic stack)
Approach
Let’s try to write it shorter this time.
Complexity
-
Time complexity: \(O(n^2k^4)\), where k = 3 is constant
-
Space complexity: \(O(n^2)\)
Code
fun largestLocal(grid: Array<IntArray>) =
Array(grid.size - 2) { y -> IntArray(grid.size - 2) { x ->
(0..8).maxOf { grid[y + it / 3][x + it % 3] }
}}
pub fn largest_local(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut res = vec![vec![0; grid.len() - 2]; grid.len() - 2];
for y in 0..res.len() { for x in 0..res.len() {
res[y][x] = (0..9).map(|i| grid[y + i / 3][x + i % 3]).max().unwrap()
}}; res
}