3989. Maximum Consistent Columns in a Grid
Description
You are given a 2D integer array grid of size m x n, and an integer limit.
You may remove zero or more columns from the grid, but at least one column must remain. The relative order of the remaining columns must be preserved.
A grid is called consistent if for every row i, and for every pair of adjacent remaining columns a and b with a < b, the following holds: |grid[i][b] - grid[i][a]| <= limit.
Return the maximum number of columns that can remain such that the resulting grid is consistent.
Example 1:
Input: grid = [[-2,0,3]], limit = 2
Output: 2
Explanation:
- Remove column 2 and keep columns 0 and 1, which gives
|grid[0][1] − grid[0][0]| = |0 − (−2)| = 2 <= limit. - Thus, the maximum number of columns that can remain is 2.
Example 2:
Input: grid = [[1,-1,1],[2,2,2]], limit = 1
Output: 2
Explanation:
- Remove column 1 and keep columns 0 and 2, which gives
|grid[0][2] − grid[0][0]| = |1 − 1| = 0 <= limitand|grid[1][2] − grid[1][0]| = |2 − 2| = 0 <= limit.
- Thus, the maximum number of columns that can remain is 2.
Example 3:
Input: grid = [[-5,5]], limit = 9
Output: 1
Explanation:
- Remove either column 0 or column 1, since
|grid[0][1] − grid[0][0]| = |5 − (−5)| = 10 > limit. - Thus, the maximum number of columns that can remain is 1.
Constraints:
1 <= m == grid.length <= 2501 <= n == grid[i].length <= 250-105 <= grid[i][j] <= 1050 <= limit <= 105
Solutions
Solution 1
Thinking
After deletions, every pair of neighboring kept columns must differ by at most \(\textit{limit}\) in every row. Order is fixed, so we want the longest column subsequence meeting that adjacent constraint.
When the number of columns is moderate, a LIS-style DP works: \(\textit{dp}[j]\) is the longest consistent sequence ending at \(j\), and \(i\to j\) is legal only if every row satisfies the limit.
This directory has no implemented solution yet; the walkthrough stops at that column DP.
1 | |
1 | |
1 | |
1 | |