Largest Local Values in a Matrix II - Video Solutions
Weekly Contest 502 | leetcode 3931|leetcode 3932 | leetcode 3933 | leetcode 3934 | Binary Search
Largest Local Values in a Matrix II - Video Solution
Watch 7 video solutions for Largest Local Values in a Matrix II, a medium level problem involving Array, Matrix, Prefix Sum. This walkthrough by Code With Vick has 841 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an n x m integer matrix matrix containing non-negative integers.
A non-zero cell (row, col) checks the cells near it as follows:
- Let
x = matrix[row][col]. - Consider every cell within
xrows andxcolumns of(row, col). - Ignore cells that are outside the matrix.
- Ignore the cells where both the row distance and column distance are exactly
x.
The cell (row, col) is a local maximum if it is non-zero and no considered cell has a value greater than x.
Return an integer denoting the number of local maximums in matrix.
Example 1:
Input: matrix = [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,2,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]
Output: 1
Explanation:
- For the non-zero cell
(3, 3),x = matrix[3][3] = 2. - The highlighted cells are the considered cells within
xrows andxcolumns of(3, 3). - The four cells with both row and column distances equal to
x = 2are ignored. - No considered cell has a value greater than 2, so
(3, 3)is a local maximum. - There are no other non-zero cells, so the answer is 1.
Example 2:
Input: matrix = [[1,2],[3,4]]
Output: 1
Explanation:
Only the cell with value 4 is a local maximum. Every other non-zero cell considers a cell with a greater value.
Example 3:
Input: matrix = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5
Explanation:
- For a cell with value 1, the considered cells are the cell itself and its 4-directionally adjacent cells that are inside the matrix.
- Each of the five cells with value 1 only considers cells with values 0 or 1, so all five of them are local maximums.
Example 4:
Input: matrix = [[1,1],[1,1]]
Output: 4
Explanation:
All cells have the same value. Therefore, no cell considers another cell with a greater value, so all 4 cells are local maximums.
Constraints:
1 <= n == matrix.length <= 2001 <= m == matrix[i].length <= 2000 <= matrix[i][j] <= 200
Approach Overview
Problem Overview: You are given a matrix and must compute the maximum value inside every k × k local submatrix. For each valid top-left position of the window, return the largest element within that region. The challenge is avoiding repeated scans of the same cells when the window slides across the grid.
Approach 1: Brute Force Window Scan (O(n * m * k^2) time, O(1) space)
For every valid top-left cell of a k × k region, iterate through all k^2 elements and track the maximum. This directly follows the problem definition: nested loops pick the window, and two more loops scan the cells inside it. The implementation is simple and works well for small matrices or small k. However, the same elements are repeatedly re-scanned when the window moves one step right or down, which quickly becomes expensive for larger inputs.
Approach 2: 2D Sliding Window with Monotonic Deque (O(n * m) time, O(n * m) space)
The optimal approach treats the problem as a two‑stage sliding window maximum. First compute the maximum of every horizontal k-length segment in each row using a monotonic deque. This produces an intermediate matrix where each value represents the row-wise window maximum. Next apply the same sliding window technique vertically on this intermediate matrix to compute column-wise maxima. The deque maintains elements in decreasing order, allowing constant-time access to the window maximum while removing elements that fall out of the window.
This technique avoids reprocessing the same cells and reduces the complexity from scanning k^2 elements per window to amortized constant work per element. Sliding window maximum is a common pattern in arrays and matrix problems, and the monotonic queue structure also appears in advanced sliding window optimizations.
Recommended for interviews: Start by describing the brute force window scan to show you understand the definition of a local region. Then move to the optimized 2D sliding window using a monotonic deque. Interviewers typically expect this improvement because it demonstrates recognition of the sliding-window-maximum pattern and reduces the complexity from O(n * m * k^2) to O(n * m).
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force k×k Scan | O(n * m * k^2) | O(1) | Small matrices or when simplicity is preferred |
| 2D Sliding Window with Monotonic Deque | O(n * m) | O(n * m) | Large grids or interview settings requiring optimal performance |