CareerCup

I'm assuming sparse means most of the matrix is full of 0s, and of the nonzero elements, a tiny fraction are positive.

I would augment the matrix with another data structure to hold the set of all negative values elements (if position in matrix matters, keep track of that too).
A nice data structure might be a hashSet keyed on the (i,j) position of the negative number in matrix.

Amortize the cost of keeping the extra data structure up to date by updating it during each insert/delete/modify in the matrix. So all these operations can clearly be kept at O(1) average ( assuming well designed hash table).

Now the query to return all negative elements is O(numNegativeElements)... just return the keys in hash table. I think this is optimal.

IF we aren't allowed to augment, I'd tell the interviewer to enlighten me...

I'm assuming sparse means most of the matrix is full of 0s, and of the nonzero elements, a tiny fraction are positive.

I would augment the matrix with another data structure to hold the set of all negative values elements (if position in matrix matters, keep track of that too).
A nice data structure might be a hashSet keyed on the (i,j) position of the negative number in matrix.

Amortize the cost of keeping the extra data structure up to date by updating it during each insert/delete/modify in the matrix. So all these operations can clearly be kept at O(1) average ( assuming well designed hash table).

Now the query to return all negative elements is O(numNegativeElements)... just return the keys in hash table. I think this is optimal.

IF we aren't allowed to augment, I'd tell the interviewer to enlighten me...

it just clicked that may be the interviewer was expecting me to just talk about hashing used in databases

simple,hint has been given in question,maintain sparse tree store blocks that is zero at the end maintain link of next list of block with zero value blocks,such structure called a free list.