Skip to main content
Talentd

Largest Local Values in a Matrix II - Solution & Explanation

MediumArrayMatrixPrefix Sum4 min read
Practice this problem

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 x rows and x columns 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 x rows and x columns of (3, 3).
  • The four cells with both row and column distances equal to x = 2 are 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 <= 200
  • 1 <= m == matrix[i].length <= 200
  • 0 <= 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).

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force k×k ScanO(n * m * k^2)O(1)Small matrices or when simplicity is preferred
2D Sliding Window with Monotonic DequeO(n * m)O(n * m)Large grids or interview settings requiring optimal performance

Video Solution

Weekly Contest 502 | leetcode 3931|leetcode 3932 | leetcode 3933 | leetcode 3934 | Binary Search • Code With Vick • 841 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Largest Local Values in a Matrix II easy or hard?
The problem is generally considered medium difficulty. The brute force idea is straightforward, but reaching the optimal O(n * m) solution requires recognizing the sliding window maximum pattern and applying it in two dimensions.
Largest Local Values in a Matrix II Python/Java solution
Most implementations follow the two-phase sliding window strategy. Use a deque to compute row-wise window maxima, store them in an intermediate matrix, and then apply another deque-based window vertically. This pattern translates cleanly to Python collections.deque or Java ArrayDeque.
How to solve Largest Local Values in a Matrix II in O(n)?
The near-linear solution uses the sliding window maximum technique with a monotonic deque. Compute horizontal window maxima for each row, then compute vertical maxima over those results. Each element is pushed and popped from the deque at most once, giving O(n * m) total complexity.
What is the best approach for Largest Local Values in a Matrix II?
The optimal solution uses a 2D sliding window combined with a monotonic deque. First compute row-wise sliding window maxima, then run another sliding window vertically on the intermediate results. This reduces repeated scanning and achieves O(n * m) time complexity instead of O(n * m * k^2).
Is Largest Local Values in a Matrix II asked at Google/Amazon/Meta?
Matrix sliding window and local maximum problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations of this problem test knowledge of sliding window maximum, monotonic queues, and efficient matrix traversal patterns.
What data structure is used in Largest Local Values in a Matrix II?
The optimized approach relies on a monotonic deque (double-ended queue). It stores candidate indices for the maximum within the current sliding window while maintaining elements in decreasing order, enabling constant-time access to the window maximum.
What is the time complexity of Largest Local Values in a Matrix II?
The brute force approach checks every k×k region directly and runs in O(n * m * k^2) time. The optimized sliding window solution processes each matrix element a constant number of times, resulting in O(n * m) time complexity with O(n * m) auxiliary space.

Ready to solve this problem?

Practice Largest Local Values in a Matrix II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays