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.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.