You are given an m x n integer matrix, grid, containing distinct positive integers.

Your task is to replace each integer in the matrix with a positive integer such that the following conditions are satisfied:

1. Preserve relative order: The relative order of every two elements that are in the same row or column should stay the same after the replacements.

2. Minimize maximum value: The maximum number in the matrix after the replacement should be as small as possible.

The relative order is preserved if, for all pairs of elements in the original matrix, the following condition holds:

If grid[r1][c1] > grid[r2][c2] and either r1 == r2 or c1 == c2, then the corresponding replacement values must also satisfy grid[r1][c1] > grid[r2][c2].

For example, if grid = [[2, 4, 5], [6, 3, 8]], valid replacements could be:

• [[1, 2, 3], [2, 1, 4]]

• [[1, 2, 3], [3, 1, 4]]

Return the resulting matrix after the replacement. If there are multiple valid solutions, return any of them.

Constraints:

• m $==$ grid.length

• n $==$ grid[i].length

• $1 \leq m, n \leq 30$

• $1 \leq m \times n \leq 900$

• $1 \leq$ grid[i][j] $\leq 10^5$

• The grid consists of distinct integers.

The solution begins by extracting all the elements from the grid along with their positions (row index and column index) and sorting them in ascending order based on their original values. This ensures that elements with smaller values are processed before those with larger ones. To maintain the correct ordering within each row and column, the algorithm uses two auxiliary arrays to keep track of the highest value assigned so far in each row and column. As each cell is processed, its new value is determined by taking the greater of the current maximums in its row and column, then adding one. This guarantees that each new value is strictly greater than those already assigned in the same row or column, preserving the required ordering. After assigning this value, the row and column trackers are updated accordingly. This process continues for all elements in the grid, and terminates once every cell has been assigned a new value. At that point, the updated grid is returned, ensuring that the relative order is preserved and the overall maximum value is minimized.

Now, let’s look at the solution steps below:

1. Flatten the grid into a list named cells, where each element is a tuple of the form (grid[i][j], i, j) representing the value and its coordinates (row index and column index). This helps track each cell's original position.

2. Sort the cells list in ascending order based on the original grid values. This ensures that elements are processed in increasing value order, preserving the relative ordering requirements.

3. Create two arrays, row_max and col_max, to track the highest values that will be assigned in each row and column of the result grid.

4. Iterate through each (value, i, j) in the sorted cells list:

   1. Compute the new value as max(row_max[i], col_max[j]) + 1. This maintains the increasing order within the row and column.

   2. Assign the new value to grid[i][j].

   3. Update row_max[i] and col_max[j] with the new value.

5. Return the grid after all cells have been processed. The resultant matrix will preserve the required ordering and minimize the maximum assigned value.

Let’s look at the illustration below to better understand the solution.