= Solution
Entry $(j,x)$ in source row `i` becomes entry $(i,x)$ in destination row `j`. Visit source rows in descending order and prepend, producing increasing destination column order without a sorting pass.
``
def transpose: SparseMatrix = {
val out = new SparseMatrix(N)
var i = N - 1
while (i >= 0) {
for ((j, x) <- rows(i)) {
out.rows(j) = (i, x) :: out.rows(j)
}
i -= 1
}
out
}
``
Before processing source row `i`, each destination row contains exactly the contributions from source rows with index greater than `i`, in increasing index order. Prepending index `i` preserves that order, and each source position is unique. Hence the <representation invariant> holds and
$$
\boxed{\mathrm{out}_{ji}=A_{ij},\qquad O(N+M)\text{ time}.}
$$
The source <sparse matrix> is unchanged.
Back to article page
