Nostalgiabait

First consider the case $X \geq 0$. If $X<0$, construct a matrix for $|X|$ and then transpose it. Transposition swaps rows and columns, so it swaps $M_1$ and $M_2$ and changes the sign of their difference.

Every row contains $N$ distinct positive integers, so its maximum is at least $N$. Hence $M_2 \geq N$. Also, the maxima of the $N$ rows are distinct, so their minimum is at most $N^2-N+1$. Therefore

$$N \leq M_2 \leq N^2-N+1.$$

The same argument gives

$$N \leq M_1 \leq N^2-N+1.$$

Thus a necessary condition is

$$|X| \leq (N^2-N+1)-N=(N-1)^2.$$

Now suppose $0 \leq X \leq (N-1)^2$, and let $K=N^2-N+1$.

Set

$$H_{1,1}=K-X.$$

For every $2 \leq i \leq N$, set

$$H_{i,i}=K+i-1.$$

Thus the largest $N-1$ values $K+1,K+2,\cdots,N^2$ are placed on the diagonal.

If $X>0$, also set

$$H_{2,1}=K.$$

Fill every still-empty cell from top-left to bottom-right with the smallest positive integer that has not been used yet.

When $X>0$, we have $K-X \geq N$. Hence the other $N-1$ cells of the first row receive values smaller than $K-X$, so the maximum of the first row is $K-X$. For every later row, its diagonal entry is its maximum. Therefore

$$M_2=K-X.$$

Column $1$ contains $K$, while each other column contains one of $K+1,K+2,\cdots,N^2$. Hence

$$M_1=K.$$

Thus $M_1-M_2=X$.

When $X=0$, we have $H_{1,1}=K$, and the minimum row maximum and the minimum column maximum are both $K$, so the construction is also valid.

Therefore a solution exists exactly when $|X| \leq (N-1)^2$. Filling the matrix takes $O(N^2)$ time per case, or $O\left(\sum N^2\right)$ over the entire input.

Solution written by GPT5.6