Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a problem where I have to change all the Xs in a 2D array into 0s, and I have to calculate the minimum steps (where a single step consists of changing an entire row or column) required to do so. For example, in an array like-

[[X, X, X],

[X, 0, 0],

[X, 0, 0]]

The minimum number of steps required here is 2.

I thought of a brute force approach (where I am checking row-wise once and column-wise thence and then comparing them to check which takes minimum number of steps) but that would give me an answer of 3, which is not the desired output.

Any help, or clue, regarding how I should approach this problem would be appreciated, thanks!

share|improve this question
    
Are there other numbers in there besides X that you must not change? –  whatsisname Oct 5 '13 at 17:33
    
No. All these X are identical, and only they must be changed to 0. Consider another example [[0,0,0], [0,X,0], [X,0,X]] The minimum steps here would be 2, and the output array would look like: [[0,0,0], [0,0,0], [0,0,0]] –  Tarun Verma Oct 5 '13 at 17:44
1  
Perhaps there is an O(1) linear algebra solution? Let me think about it... –  recursion.ninja Oct 5 '13 at 18:22
    
@awashburn I'd really, really appreciate that, thanks! –  Tarun Verma Oct 5 '13 at 18:31
    
Shouldn´t this post be in StackOverflow? –  Hbas Oct 5 '13 at 19:28

2 Answers 2

up vote 1 down vote accepted

If a "step" is changing out a row or column, then your goal is to do the change-outs that will affect the most Xes before you do those that cover fewer.

The way to figure that out is to traverse the entire array once and keep track of the number of Xes in each row and column. For a minor variant on your example, the end result of that calculation would look like this:

   C C C
   1 2 3
R1 X X X -- 3 Total
R2 0 X 0 -- 1 Total
R3 0 X 0 -- 1 Total
   | | |
   1 3 1 Totals

Break that information out into a list (read each item as "3 Xes in Row 1", "1 X in Row 2", etc.):

3/R1  1/R2  1/R3  1/C1  3/C2  1/C3

A descending sort of the counts makes it pretty obvious which one to change out first:

3/R1  3/C2  1/R2  1/R3  1/C1  1/C3

Change out R1, make note of that as your first step and remove it from the list. When you change out a row with Xes, the columns that contained those Xes (all of them in this case) now contain one less. This means you have to reduce the count in each column where you found an X:

0/C1  1/R2  1/R3  2/C2  0/C3

That change blows the sort order right out of the water, because now the item that's going to wipe out the most Xes is no longer up front. A re-sort fixes that and reveals column 2 as the next step:

2/C2  1/R2  1/R3  0/C1  0/C3

After a change-out, decrement and re-sort, you're down to this:

0/R2  0/R3  0/C1  0/C3

A zero first element means you've reached the end because anything following it will also be zero, meaning no more Xes in the array. Anything else means you repeat the process.

Not only will you get the number of steps out of this, you'll also get a list of what those steps are.

You also don't necessarily have to do a sort, either. You can simply traverse the list each time, and hold onto the element with the largest count. If you're using a language that has a sorted collection available, writing this would be a piece of cake.

share|improve this answer

That seens to be an interview and/or college exercise question, so I will give you just some directions...

Imagine that each possible matrix (the arrays with X and zeroes) are nodes in a graph. From each node, you can generate another one with the steps that you mentioned (change a line or change a column).

So, with:

[[X, X, X],    
[X, 0, 0],    
[X, 0, 0]]

You can go to:

[[0, 0, 0],    
[X, 0, 0],    
[X, 0, 0]]

or

[[0, X, X],    
[0, 0, 0],    
[0, 0, 0]]

or

[[X, X, 0],    
[X, 0, 0],    
[X, 0, 0]]

or

(Goes on...)

Now you should, from the initial matrix, try to do a breadth-first search (see this wikipedia link and/or your favorite algorithm book) for a matrix that satisfies your condition: all zeroes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.