Data structure to efficiently add zero-rows to a sparse matrix

Question

I would like to create a data structure representing a sparse matrix, where the number of non-zero values is $\mathcal{O}(n)$ (the matrix is $n\times n$).

The matrix should support the following operations with the following time complexities:

1. peek/poke an entry in the matrix - $\mathcal{O}(n)$.
2. add a row of zeros somewhere in the matrix - $\mathcal{O}(1)$.

I tried simply using a linked list or a list of lists but these approach doesn't work because when we add a zero row all indices get mixed up.

Answer 1

An easy but probably undesired way is doing the operation lazily. The list of lists representation can be modified slightly to support "add row" in $O(1)$ time.

When you add a row, you don't actually touch the main structure. But only add the row index to the list as an "unprocessed operation". This is $O(1)$ time.

When you access an entry, check for the unprocessed operation list. If there are unprocessed operations, sort and merge the added rows to the main structure. This can be done in $O(n)$ time.

Answer 2

You can achieve $O(\log n)$ time for all operations, by using a balanced binary search tree for the index that maps from a row index to the row. Such a tree can support $O(\log n)$ time lookup of any index, and can also support inserting a row in $O(\log n)$ time. Each row can be represented in any convenient way, e.g., a hashtable that maps from column index to the value, or a tree to representing this mapping.

Answer 3

You can use your lists of list representation. But your main list $M$ will be a circular, double linked list. A new row will be inserted at the head of $M$, which takes $O(1)$ time. Each row will store its own row position $p$. Now, it's possible for multiple rows to have the same row position at any time. Say you insert $r_i$ first as row 0 then $r_j$ next, again as row 0. Inserting $r_j$ should have "pushed" $r_i$ one position forward, however we will not update $r_i$'s position until later. Note that $r_j$ will appear in front of $r_i$ in $M$. In general, it's possible that a new row $r$ inserted at position $p$ to "push" some rows that were inserted much earlier if the position of these rows is $\geq p$. Updating all row positions will be done during peek.

We will use $r.p$ to represent the stored position of a given row $r$. Now for peek, we will use "bucket-sort" like technique. Create a new array $B$ whose size is $n$, the current number of rows in $M$. This array is actually an array of linked list (like a hash table). Now traverse $M$ backwards, removing each row along the way. When a row $r$ is removed, insert it at the head of list $B[r.p]$. This will empty $M$ and transfer everything to $B$, but rows with different positions are stored in separate buckets. As for rows with the same position, their order in $B$ are preserved. From the example above, $r_i$ and $r_j$ will be stored on the same bucket and $r_j$ will still be in front of $r_i$. Let $i = 0$. Empty $B$ by removing the contents (rows) of each bucket one at a time starting from $B[0]$ up to $B[n-1]$. When a row $r$ is removed from $B$, set $r.p = i$, increment $i$, then insert it to $M$ but this time at the tail. Inserting at the tail of a circular, double linked list also takes $O(1)$ time. Observe that once $B$ is empty all rows have their correct position and are stored in $M$ in order of their position. Now you can start traversing $M$ to peek the row you need. Transferring rows from $M$ to $B$ back and forth takes $O(n)$ time and the actual accessing of a row takes $O(n$) time, thus overall you have $O(n)$ for peek.