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:

  1. 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.

  2. Tracking Row and Column Maximums: Two arrays row_max and col_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
  3. 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)]
  4. 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] and col_max[j]. We then update both row_max and col_max at index i and j 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example 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.

  1. 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)]
  2. Tracking Row and Column Maximums:

    • Initialize row_max and col_max to keep track of the max values so far:
    1row_max = [0, 0]
    2col_max = [0, 0, 0]
  3. Constructing the Result Matrix:

    • Initialize the ans matrix with zeroes to build the solution:
    1ans = [[0, 0, 0], [0, 0, 0]]
  4. Iterating and Assigning New Values:

    • Iterate over sorted nums and replace values in ans while updating row_max and col_max:
      • For (3, 1, 0) -> ans becomes:

        1ans = [[0, 0, 0], [1, 0, 0]]

        And row_max and col_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 and col_max update to:

        1row_max = [2, 1]
        2col_max = [1, 2, 0]
      • Repeat this process for each element in nums.

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.

  1. 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 of O(m * n).

  2. Next, the sort operation on this list of tuples has a time complexity of O(m * n log(m * n)), since it sorts the list with respect to the values in the grid.

  3. Then, the code iterates over the sorted list nums with m * n elements, performing constant-time operations inside the loop. This contributes O(m * n) to the time complexity.

  4. The updates to row_max and col_max are also constant-time operations, happening m * 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:

  1. The list nums which stores the tuples has a space complexity of O(m * n) because it stores each element of the grid.

  2. Two arrays, row_max and col_max, each with a length of m and n respectively, resulting in O(m) and O(n) space used.

  3. The ans list is a 2D list of the same size as the input grid, yielding a space complexity of O(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.


Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄