Maximum Consistent Columns in a Grid solution and explanation
4 more videos on this problem
Leetcode 3989 | Maximum Consistent Columns in a Grid | Dynamic Programming | Weekly contest 510CodeWithMeGuys · 13:41 · 231 views
LeetCode 3989 | Maximum Consistent Columns in a Grid | Hard | Weekly Contest 510 | ExplainedDesignSchool · 13:59 · 148 views
3989. Maximum Consistent Columns in a Grid (Leetcode Hard)Programming Live with Larry · 13:28 · 113 views
LeetCode 3989 | Maximum Consistent Columns in a Grid | LIS | JavaCode Kage · 9:30 · 111 views
LeetCode 510 - 3989 Maximum Consistent Columns in a GridManjeet Dhayal · 17:05 · 47 views
The problem
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
Approach overview
Problem Overview: You need to find the maximum number of columns in a grid that can be treated as consistent under the problem’s row and column constraints. The core challenge is recognizing that columns with the same structural pattern behave identically, even when values are transformed or normalized.
Approach 1: Brute Force Column Comparison (Time: O(m * n2), Space: O(1))
The direct approach compares every pair of columns cell by cell. For each column, iterate through all remaining columns and verify whether their values satisfy the consistency rule across every row. This works for small grids because it does not require additional preprocessing or auxiliary structures. The downside is the quadratic comparison cost across columns, which becomes expensive when n is large.
Approach 2: Column Signature Hashing (Time: O(m * n), Space: O(n))
The optimized solution converts every column into a normalized signature and stores the frequency in a hash map. You iterate through each column, build a compact representation using its row values, and use hash lookup to count matching patterns in constant time. The key insight is that consistent columns share the same normalized structure, so repeated comparisons are unnecessary. This approach is the standard interview solution because it reduces repeated work and scales efficiently for dense grids.
Instead of comparing columns repeatedly, you preprocess each column once and group equivalent columns together. In most implementations, the signature is stored as a string, tuple, or bitmask depending on language constraints. Using a bitmask can further reduce memory overhead when the grid is binary. Problems built around pattern grouping often rely on hash maps, bit manipulation, and lightweight array traversal.
Approach 3: Bitmask Compression (Time: O(m * n), Space: O(n))
When the grid contains only binary values, each column can be compressed into an integer bitmask. As you iterate through rows, shift bits into the mask and use the final integer as the hash key. This avoids string construction costs and improves cache efficiency in lower-level languages like C++ and Java. The algorithmic complexity stays linear, but the implementation becomes more optimized for competitive programming constraints.
Recommended for interviews: Start with the brute force comparison to demonstrate that you understand the consistency condition. Then move to the hash-based grouping approach, since interviewers usually expect you to eliminate repeated column scans and reduce the complexity to O(m * n). If constraints are tight and the grid is binary, mentioning bitmask compression shows strong optimization awareness.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Column Comparison | O(m * n²) | O(1) | Small grids or when optimizing is unnecessary |
| Hash Map with Column Signatures | O(m * n) | O(n) | General case and interview-preferred solution |
| Bitmask Compression | O(m * n) | O(n) | Binary grids with tight memory or performance constraints |
Frequently asked questions
Is Maximum Consistent Columns in a Grid easy or hard?
Maximum Consistent Columns in a Grid is generally classified as a hard problem because the main challenge is identifying the correct normalization strategy. The brute force solution is straightforward, but deriving the optimal hashing approach requires stronger pattern recognition skills.
Maximum Consistent Columns in a Grid Python/Java solution
Python solutions usually store column signatures as tuples or strings inside a dictionary. Java implementations commonly use HashMap<String, Integer> or integer bitmasks for binary grids. Both approaches achieve O(m * n) complexity.
How to solve Maximum Consistent Columns in a Grid in O(n)?
The standard optimized solution is effectively O(m * n) because every grid value must be read at least once. Build a normalized signature for each column and store it in a hash map. The highest frequency of any signature gives the maximum consistent columns.
What is the best approach for Maximum Consistent Columns in a Grid?
The best approach uses a hash map to group normalized column patterns. Each column is converted into a compact signature, and matching signatures are counted in O(1) average lookup time. This reduces the overall complexity to O(m * n).
Is Maximum Consistent Columns in a Grid asked at Google/Amazon/Meta?
Grid normalization and hash-based grouping problems appear frequently in interviews at Google, Amazon, and Meta. Variants involving row flips, column patterns, and binary matrix transformations are common in hard-level rounds.
What data structure is used in Maximum Consistent Columns in a Grid?
The primary data structure is a hash map that stores column signatures and their frequencies. Some optimized implementations also use bitmasks to compress binary column states into integers for faster lookup.
What is the time complexity of Maximum Consistent Columns in a Grid?
The optimal hashing solution runs in O(m * n) time, where m is the number of rows and n is the number of columns. Every cell is processed once while constructing column signatures. Space complexity is typically O(n) for storing frequencies.