2371. Minimize Maximum Value in a Grid
Problem Description
The problem presents a challenge to minimize the maximum value in a given m x n
matrix, grid
, while maintaining the relative ordering of numbers in their respective rows and columns. In this context, "relative order" means that if a number is greater than another number in the same row or column in the original matrix, it must remain greater in the transformed matrix. The objective is to do so by replacing each element in the matrix with a new positive integer and ensuring that the new maximum number in the matrix is as small as possible.
A fundamental requirement is that the original matrix contains distinct positive integers. This constraint simplifies the problem, as we do not need to consider the case where two elements are equal. The challenge is to determine the smallest possible replacements that satisfy the aforementioned relative order conditions.
Intuition
To maintain the relative order within rows and columns, we look at the individual elements' ranks when compared to other elements within the same rows and columns. The key observation is that the smallest number can be replaced by 1, the second smallest by 2, and so on, without changing their relative positions. However, simply increasing each subsequent element by 1 does not always work, especially when an element is not the smallest in its row or column.
The approach for finding the solution is twofold: Firstly, sort all of the elements in the grid based on their value while keeping track of their original positions. This allows us to process the elements in increasing order, ensuring that each replacement maintains the overall relative ordering structure of the grid.
Secondly, maintain two arrays row_max
and col_max
, where row_max[i]
indicates the largest number assigned so far in row i
, and col_max[j]
the largest number in column j
. As we process each element in sorted order, we determine its new value by taking the maximum of row_max[i]
and col_max[j]
for its position (i, j)
and then add 1 to it. This ensures that the new number will be larger than any previously assigned number in the same row or column, maintaining the relative order. The two arrays are then updated with this new value to reflect the new maximum values for that row and column.
By using this method, we can iterate through all the elements in the grid only once, after sorting, and consistently assign the minimum required number that maintains both the ordering and the constraint of minimizing the maximum number in the resultant matrix.
Learn more about Union Find, Graph, Topological Sort and Sorting patterns.
Solution Approach
The solution approach takes advantage of a few powerful algorithms and data structures to organize and process data efficiently. Here's how the solution implements the approach step by step:
-
Sorting: The original matrix elements are expanded into a list of tuples
nums
, where each tuple contains an element value along with its row and column indices. This list is then sorted primarily by the value, which means the tuples will be arranged in ascending order according to the elements of the matrix they represent.1nums = [(v, i, j) for i, row in enumerate(grid) for j, v in enumerate(row)] 2nums.sort()
This organizing strategy is crucial because it allows for the iteration over the matrix elements in order of their size. Since each element is associated with its original position, we can apply the exact replacements required, maintaining the relative order.
-
Tracking Row and Column Maximums: Two arrays
row_max
andcol_max
are used to keep track of the highest value that has been assigned to each row and column, respectively. Initiated with zeros, these arrays will update with each assignment made in the following steps:1row_max = [0] * m 2col_max = [0] * n
-
Constructing the Result Matrix: A new matrix
ans
is initialized with zero values, where the solution will be built incrementally.1ans = [[0] * n for _ in range(m)]
-
Iterating and Assigning New Values: The algorithm then iterates over this sorted list of tuples. For each tuple, which corresponds to an element from the original grid, we determine the replacement number. This number is one greater than the maximum of the current values of
row_max[i]
andcol_max[j]
. We then update bothrow_max
andcol_max
at indexi
andj
to reflect this new maximum.1for _, i, j in nums: 2 ans[i][j] = max(row_max[i], col_max[j]) + 1 3 row_max[i] = col_max[j] = ans[i][j]
In this implementation, Python list comprehensions, tuple unpacking, and sorting mechanisms are powerful tools used to streamline the solution process. This approach ensures that each element's relative value to its neighbors is preserved while the overall maximum value in the matrix is minimized. The end result is a matrix ans
that meets all the stipulated requirements and can be returned as the solution to the problem.
Thus, the solution makes effective use of familiar data structures (such as lists) and algorithmic patterns (like sorting and iteration) to solve a relatively complex problem in an efficient and straightforward manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a 2x3
matrix as an example to illustrate the solution approach.
Imagine we have the following matrix grid
:
18 4 6 23 5 9
The challenge is to minimize the maximum number after replacing numbers while maintaining their relative ordering.
-
Sorting:
- Expand the elements of
grid
into a list of tuples containing the value with its row and column index:
1nums = [(8, 0, 0), (4, 0, 1), (6, 0, 2), (3, 1, 0), (5, 1, 1), (9, 1, 2)]
- After sorting
nums
by value, we get:
1nums = [(3, 1, 0), (4, 0, 1), (5, 1, 1), (6, 0, 2), (8, 0, 0), (9, 1, 2)]
- Expand the elements of
-
Tracking Row and Column Maximums:
- Initialize
row_max
andcol_max
to keep track of the max values so far:
1row_max = [0, 0] 2col_max = [0, 0, 0]
- Initialize
-
Constructing the Result Matrix:
- Initialize the
ans
matrix with zeroes to build the solution:
1ans = [[0, 0, 0], [0, 0, 0]]
- Initialize the
-
Iterating and Assigning New Values:
- Iterate over sorted
nums
and replace values inans
while updatingrow_max
andcol_max
:-
For
(3, 1, 0)
->ans
becomes:1ans = [[0, 0, 0], [1, 0, 0]]
And
row_max
andcol_max
update to:1row_max = [0, 1] 2col_max = [1, 0, 0]
-
For
(4, 0, 1)
->ans
becomes:1ans = [[0, 2, 0], [1, 0, 0]]
And
row_max
andcol_max
update to:1row_max = [2, 1] 2col_max = [1, 2, 0]
-
Repeat this process for each element in
nums
.
-
- Iterate over sorted
The final ans
matrix after completing the iterations will look like this:
12 2 3 21 2 4
In this new ans
matrix, the relative ordering is maintained, and the maximum value, which is 4
, is minimized compared to the original grid
. The ans
matrix can be returned as the solution to the problem.
Solution Implementation
1class Solution:
2 def min_score(self, grid):
3 """
4 This method finds the minimum score for each cell in the grid such that
5 each row and column contains unique scores.
6 It sorts the cells initially and uses those values to ensure the uniqueness.
7 """
8 # Get the dimensions of the grid
9 num_rows, num_cols = len(grid), len(grid[0])
10
11 # Flatten the grid into a list of tuples (value, row_index, col_index)
12 flatten_grid = [(value, row_index, col_index) for row_index, row in enumerate(grid) for col_index, value in enumerate(row)]
13
14 # Sort the flatten_grid based on the cell values
15 flatten_grid.sort()
16
17 # Initialize lists to keep track of the maximum score in each row and column
18 row_max = [0] * num_rows
19 col_max = [0] * num_cols
20
21 # Create an answer grid initialized with zeros
22 ans_grid = [[0] * num_cols for _ in range(num_rows)]
23
24 # Iterate over sorted cells and assign the minimum required score
25 for value, row_index, col_index in flatten_grid:
26 # The score for the cell is 1 more than the max of the row and column seen so far
27 ans_grid[row_index][col_index] = max(row_max[row_index], col_max[col_index]) + 1
28 # Update the current row and column max values
29 row_max[row_index] = col_max[col_index] = ans_grid[row_index][col_index]
30
31 # Return the answer grid with all scores filled in
32 return ans_grid
33
34# Example usage:
35# solution_instance = Solution()
36# grid = [[3, 1], [2, 4]]
37# print(solution_instance.min_score(grid)) # Should output the minimum score grid based on the input grid
38
1class Solution {
2 public int[][] minScore(int[][] grid) {
3 int rows = grid.length; // Number of rows in the grid
4 int cols = grid[0].length; // Number of columns in the grid
5
6 // This list will hold the value, row, and column for each cell in the grid
7 List<int[]> cellDetails = new ArrayList<>();
8
9 // Populate the list with cell details
10 for (int i = 0; i < rows; ++i) {
11 for (int j = 0; j < cols; ++j) {
12 cellDetails.add(new int[] {grid[i][j], i, j});
13 }
14 }
15
16 // Sort the cell details based on the cell value
17 Collections.sort(cellDetails, (a, b) -> a[0] - b[0]);
18
19 // Arrays to keep track of the maximum score in each row and column
20 int[] rowMaxScores = new int[rows];
21 int[] colMaxScores = new int[cols];
22
23 // Answer grid to hold the minimum required scores
24 int[][] minScores = new int[rows][cols];
25
26 // Update the answer grid with the minimum required scores,
27 // looping through the cells by increasing order of their values
28 for (int[] cell : cellDetails) {
29 int cellValue = cell[0]; // The value of the cell
30 int row = cell[1]; // The row index of the cell
31 int col = cell[2]; // The column index of the cell
32
33 // Compute the minimum score for this cell based on the max scores in the current row and column
34 minScores[row][col] = Math.max(rowMaxScores[row], colMaxScores[col]) + 1;
35
36 // Update the row and column max scores with the newly computed score
37 rowMaxScores[row] = minScores[row][col];
38 colMaxScores[col] = minScores[row][col];
39 }
40
41 // Return the completed grid with minimum required scores
42 return minScores;
43 }
44}
45
1class Solution {
2public:
3 vector<vector<int>> minScore(vector<vector<int>>& grid) {
4 // Create a vector that will store the value and its coordinates
5 vector<tuple<int, int, int>> cells_with_values;
6 int rows = grid.size(), cols = grid[0].size();
7
8 // Populate the vector with the grid values and their corresponding coordinates
9 for (int row = 0; row < rows; ++row) {
10 for (int col = 0; col < cols; ++col) {
11 cells_with_values.push_back({grid[row][col], row, col});
12 }
13 }
14
15 // Sort the vector of tuples based on the cell values in non-decreasing order
16 sort(cells_with_values.begin(), cells_with_values.end());
17
18 // Create vectors to keep track of the maximum scores for each row and column
19 vector<int> row_max_scores(rows);
20 vector<int> col_max_scores(cols);
21
22 // Initialize the answer grid with the same dimensions as the input grid
23 vector<vector<int>> answer(rows, vector<int>(cols));
24
25 // Iterate over the sorted cell values
26 for (auto [value, row, col] : cells_with_values) {
27 // Calculate the score for the current cell, which is 1 plus the max score of the current row or column
28 answer[row][col] = max(row_max_scores[row], col_max_scores[col]) + 1;
29
30 // Update the max score for the current row and column to be the score of the current cell
31 row_max_scores[row] = col_max_scores[col] = answer[row][col];
32 }
33
34 // Return the populated answer grid
35 return answer;
36 }
37};
38
1function minScore(grid: number[][]): number[][] {
2 // Get the dimensions of the grid
3 const rows = grid.length;
4 const cols = grid[0].length;
5
6 // Create an auxiliary array to hold grid elements and their coordinates
7 const elements = [];
8 for (let i = 0; i < rows; ++i) {
9 for (let j = 0; j < cols; ++j) {
10 elements.push({
11 value: grid[i][j],
12 row: i,
13 col: j
14 });
15 }
16 }
17
18 // Sort the elements array based on the value in ascending order
19 elements.sort((a, b) => a.value - b.value);
20
21 // Create arrays to keep track of the maximum score in each row and column
22 const rowMaxScores = new Array(rows).fill(0);
23 const colMaxScores = new Array(cols).fill(0);
24
25 // Initialize an answer grid with the same dimensions as the input grid
26 const answerGrid = Array.from({ length: rows }, () => new Array(cols));
27
28 // Process each element in the sorted list
29 for (const element of elements) {
30 // Calculate the score for the current element's position
31 const score = Math.max(rowMaxScores[element.row], colMaxScores[element.col]) + 1;
32
33 // Update the answer grid with the new score
34 answerGrid[element.row][element.col] = score;
35
36 // Update the maximum score counters for the current row and column
37 rowMaxScores[element.row] = score;
38 colMaxScores[element.col] = score;
39 }
40
41 // Return the completed answer grid
42 return answerGrid;
43}
44
Time and Space Complexity
Time Complexity
The given code has several distinct operations, each contributing to the overall time complexity.
-
First, the list comprehension iterates over each element in the
m x n
grid to create a list of tuples. This operation has a time complexity ofO(m * n)
. -
Next, the
sort
operation on this list of tuples has a time complexity ofO(m * n log(m * n))
, since it sorts the list with respect to the values in the grid. -
Then, the code iterates over the sorted list
nums
withm * n
elements, performing constant-time operations inside the loop. This contributesO(m * n)
to the time complexity. -
The updates to
row_max
andcol_max
are also constant-time operations, happeningm * n
times.
Combining all the above steps, the overall time complexity of the code is O(m * n log(m * n)) + O(m * n) + O(m * n)
, which simplifies to O(m * n log(m * n))
since the log term will dominate at scale.
Space Complexity
The space complexity can be analyzed based on the data structures used:
-
The list
nums
which stores the tuples has a space complexity ofO(m * n)
because it stores each element of the grid. -
Two arrays,
row_max
andcol_max
, each with a length ofm
andn
respectively, resulting inO(m)
andO(n)
space used. -
The
ans
list is a 2D list of the same size as the input grid, yielding a space complexity ofO(m * n)
.
Therefore, the total space complexity is O(m * n) + O(m) + O(n)
, which simplifies to O(m * n)
when m and n are of the same order.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.