Let $M$ be an $(n \times n)$ matrix where each element is a distinct positive integer. Construct another matrix $M'$ by permuting the rows and/or permuting the columns, such that the elements of one row appear in increasing order (while looking from left to right) and those of one column appear in decreasing order (while looking from top to bottom).
- Describe an $O(n^2)$ time algorithm for constructing $M'$. Justify your analysis.
- Propose a data structure that supports your algorithm. Clearly explain how much additional storage, other than the matrix itself, is required in your algorithm.