This puzzle is given as a coding example in the book Cracking the Coding Interview by Gayle Laakmann McDowell. The puzzle is:
Write an algorithm such that if an element in an M x N matrix is 0, its entire row and column are set to 0.
In other words, given an array, if an entry is 0, set all of the entries for its row and column to 0. A few rules:
- Make sure the program is correct. Don’t get carried away and fill the whole array with 0s.
- Be efficient. Don’t use more time or extra space than necessary.
- Don’t use tools that are specific to the .NET Framework or C#. For example, Array.Copy, MemCopy, RtlMoveMemory, and other tools can help you copy an array quickly. Don’t use any of those.
I’ll post the book’s solution (converted from Java into C#) and my solution next week.