A square matrix $A$ of $N*N$ contains $-1,1$ only. I can swap any two elements in the array as many times a I want. What is the minimum positive integer $M$ such that $A[i][j]=1$ for all pairs of $(i,j)$ where $|i-j|>M$.
Some observations :
1.If it's a diagonal matrix, ,then $M$ will be $0$.
2.If it has no $1$ in it then answer will $N-1$ as no matter how many shifts I do,there will still be some $-1$'s outside the main diagonal, so the $M$ won't become $0$.
Eg : $N=3$
\begin{bmatrix} -1 & 1 & 1 \\ 1 & -1 & -1 \\ -1 & -1 & 1 \\ \end{bmatrix}
Now the smallest $M=2$. But if I swap $A[3][1]$ , $A[3][3]$ the matrix becomes \begin{bmatrix} -1 & 1 & 1 \\ 1 & -1 & -1 \\ 1 & -1 & -1 \\ \end{bmatrix}
Now the smallest $M=1$.
How do I find the smallest $M$ ? Is there a pattern to this ?
The answer only depends on the number of $-1$s. If the number of $-1$s fit in the main diagonal of the matrix, the answer is 0. If the number of $-1$s fit in the $first$ $2k+1$ ($k < n$) diagonals (the main diagonal and $k$ diagonals immediately above and $k$ below the main diagonal), then the answer is k.