Propogate zeros to rows & columns of a matrix

Given a matrix of integers, if there are zeros in a particular position, make the whole of the corresponding row & column as zeros. Be as space conservative as possible.

The most straightforward solution to the problem is to have 2 arrays, one for storing the positions of zeros in the rows & the other for the columns. Obviously, we've to do better than this.

We can do the same with a single array too. The basic idea is to scan the matrix either row-by-row or column-by-column. Let's assume row-wise scan for this solution. While doing this scan, mark the columns having zeros in the array. If there's a zero in a row, make the whole row as zeros. After completing the row-wise scan, look at the array for the columns having zeros & make them all zeros in the second pass.

There's a beautiful third solution to this problem. Here we just use 2 variables to store the information required. Scan the first row & the first column and if there is a zero in those, mark the same in the two variables. Now, start scanning without the first row & column. If you encounter a zero, mark the same in the first element of the corresponding row & column as zero. Once this pass is completed, using the information in the first row & column, propagate the zeros to the other rows & columns. Finally, based on the information available in the 2 variables, modify the first row / column as required.

Indexing

Found this site http://puzzles.nigelcoldwell.co.uk/index.htm recently. Has a lot of good puzzles. Have heard about 50% of those in school & college. Nice to workout those things again.

On similar note, the site http://www.ihas1337code.com (now moved to http://www.leetcode.com/) is a very valuable source for interview preparation for the big giants.

Find the median of two sorted arrays

This is one of those rare problems where the solution for the generalized problem is just as costly as the solution for a specific case. In other words, we can find any k^th item of this combined array with the same complexity.

The brute-force approach is to do a merge-sort & find the median. The cost of this would be O(n+m) where n is the size of the first array & m is the size of the second. Second simple way is to see that we don't need to do a complete merge-sort but rather just till we find the k^th element. Hence the cost would be down to O(k). Obviously, we need something better than this. Turns out that this can be done in O(lg n + lg m).

First, compare the middle elements of A and B, which we identify as A_i and B_j. If A_i is between B_j and B_j-1, we have just found the i+j-1 smallest element. Therefore, if we choose i and j such that i+j = k+1, we are able to find the k^th smallest element. Basically, the above can be stated as,

Maintaining the invariant
i + j = k + 1,

If B_j-1 < A_i < B_j, then A_i must be the k^th smallest,
or else if A_i-1 < B_j < A_i, then B_j must be the k^th smallest.

When one of the above condition is satisfied for our initial i & j, we are done. Otherwise, we need to think about which set to use for the further comparisons.

If A_i < B_j, then A_i < B_j-1, because otherwise, we must have chosen A_i. This means that, the chosen A_i is quite low and we must include bigger elements from the set A (i.e., from i+1 to n). On the other hand, the chosen value from B is already too large. Hence, we shall not consider anything above the current chosen value of B (i.e., from 1 to j-1). So, basically we are shrinking our sample space in a logarithmic fashion & hence the final cost would be O(lg n + lg m).

Number of rectangles in a chessboard

I was asked by an interviewer to find out the number of squares in a chessboard to start with. I simply took the iterative approach. For a 1x1 board has 1, 2x2 board has 5, 3x3 board has 14 & so on. It all easily fits into the series 1², 1² + 2², 1² + 2² + 3² etc., Hence, for a 8x8 chessboard, it would be sum of squares of the numbers from 1 to 8.

Then he asked me if the same approach would work for finding out the number of rectangles in the board. I tried something for a couple of minutes & it didn't seem to form any pattern. Later while looking up on the net for the solution, I realized that for finding the rectangles, any iterative approach would be simply futile.

The actual solution to the problem is very simple. Let's see how it works for a square first. The basic idea is to find out the number of possible types of squares & to see where all they can be fit. For example, the square of size 1x1 can be fit in 64 positions, the square of size 2x2 can be fit in 49 positions, the square of size 3x3 can be fit in 36 positions and so on.

For a rectangle, the same thing applies. We need to first identify the various possible shapes of the rectangles that can be formed. Anything from 1x1 to 1x8 and 8x1 to 8x8 is possible. We need to find out where all these would fit & that would be it.