Sometimes we need to traverse a matrix and change the elements along the way according to some given rules. The difficulty with such problems is that current modifications of some elements could alter the process of the following modifications. One such example is the “set matrix zeroes” problem. When we set a certain column or row to all zeroes, we are destroying the information about which elements are not zeroes along that row or column and very soon the entire matrix will become all zeroes. One solution is to use two lists to store the row/column IDs on which we have a zero and after we have gathered all the information we do a second pass thorough the matrix and turn the corresponding rows and columns to zeroes. This approach uses extra memory. A better approach with no extra memory usage is to use the first row and first column to keep the indexes of the row and column indexes of the zero elements. This solution is from CTCI v6 page 204.

Another example is the “bomberman game” problem, in which a bomb can explode and change a set of elements surrounding it. The same issue exists for this problem. So my solution in the following uses a separate list to keep track of bomb locations and go through the matrix two times. The first time is to gather information about the locations of the bombs and their affected elements. The second time is to modify the matrix based on the information gathered in the previous pass.

A third example is the “cavity map” problem, in which we need to find and mark the elements that are larger than their neighbors. Again, my solution following uses two passes of the entire matrix. The first pass finds out all the elements that are larger than their four neighbors and store their row/column numbers into two separate lists (one for row number, the other for column number). In the second pass, all selected elements are marked.

Leave a Reply

Your email address will not be published. Required fields are marked *