= Solution
Keep the entries before column `j`, discard any old entry at `j`, and retain those after it. Insert the replacement only when it is nonzero.
``
def set(i: Int, j: Int, x: Double): Unit = {
require(0 <= i && i < N && 0 <= j && j < N)
val before = rows(i).takeWhile(e => e._1 < j)
val after = rows(i).dropWhile(e => e._1 <= j)
val middle: Row = if (x == 0.0) Nil else List((j, x))
rows(i) = before ::: middle ::: after
}
``
All indices in `before` are below `j` and all in `after` are above it, so the <representation invariant> is preserved. Other rows and all other column values remain unchanged:
$$
\boxed{A'_{ij}=x,\qquad A'_{kl}=A_{kl}\text{ when }(k,l)\ne(i,j).}
$$
Assigning zero removes storage for that entry. The <time complexity> is linear in the stored row length.
Back to article page
