CareerCup

Nice problem!

We have a number different approaches for solving this. I've assumed n and m to be equal for the sake of an easier analysis. Inequality of n and m has no effect on the validity of the solutions.

One is the naive approach, which picks two cells at a time and checks if those two cells can be upper left and bottom right cells of a valid rectangle. This solution has a time complexity of O(n^6).

Another approach is a dynamic programming approach. In this approach we first pre-process to calculate for every cell mx(i,j) the number of zeroes in the rectangle defined by (1,1) to (i,j). We do this with the simple formula below using the principle of inclusion and exclusion:

zeroes(i,j) = zeroes(i-1,j) + zeroes(i,j-1) - zeroes(i-1,j-1)

After that for every two cells in the matrix, we first check if those two cells define boundary of a rectangle. If they do so, we check if there is zero in between using the information we obtained previously. This approach has a running time of O(n^5).

We can do better, however. We first, pre-process the matrix to obtain the matrix of the number of zeroes like the previous approach. We have an additional pre-processing step here. We calculate for every cell that has a one in it, the number of consecutive ones immediately to the right, left, up, and down of that cell. After that for every two cell A & B we check if they define a valid boundary using the immediate ones information found previously. If they do we check if they enclose a zero similar to the previous solution. This approach runs in O(n^4).

We STILL can do better. This solution is a bit complex and my explanation of what goes in my head may not be comprehensive enough. :-)
We have two pre-processing steps. In the first step, we calculate the number of consecutive ones above every cell leading to that cell. The other pre-processing step is calculating for every cell mx(i,j), the number of zeroes in row i until column j. After that for we do the following operations on every two column i and j. We go forward one row, k, at a time and count the number of valid rectangles that have mx(k,i)---mx(k,j) as their lower edge. Feel free to check my code to get a feeling of how it is calculated. I'll be more than happy to discuss that. :-) This solution has cubic running time, and I cannot think of a better one.

My C++ implementation for the O(n^3) solution:

#include <iostream>
#include <algorithm>

using namespace std;

int zerocnt[1010][1010], oneline[1010][1010], fulllines[1010], mtrx[1010][1010];

int solve(int **mx, int n, int m)
{
	for (int i = 0; i<n; i++)
	{
		mtrx[i][0] = 0;
		oneline[i][0] = 0;
		zerocnt[i][0] = 0;
	}
	for (int j = 0; j<m; j++)
	{
		mtrx[0][j] = 0;
		oneline[0][j] = 0;
		zerocnt[0][j] = 0;
	}
	for (int i = 0; i<n; i++)
	for (int j = 0; j<m; j++)
	{
		mtrx[i + 1][j + 1] = mx[i][j];
		oneline[i + 1][j + 1] = (mtrx[i + 1][j + 1] == 1 ? oneline[i][j + 1] + 1 : 0);
		zerocnt[i + 1][j + 1] = (mtrx[i + 1][j + 1] == 0 ? 1 : 0) + zerocnt[i + 1][j];
	}

	int ans = 0;

	for (int i = 1; i <= m - 2; i++)
	for (int j = i + 2; j <= m; j++)
	{
		int closestzero = -1;
		fulllines[0] = 0;
		for (int k = 1; k <= n; k++)
		{
			fulllines[k] = fulllines[k - 1];
			if (zerocnt[k][j] != zerocnt[k][i])
			{
				closestzero = k;
				continue;
			}

			++fulllines[k];

			int shortline = min(oneline[k][i], oneline[k][j]);

			if (closestzero > (k - shortline) + 1)
				ans += fulllines[closestzero] - fulllines[(k - shortline)];

		}
	}

	return ans;
}

only 3 rectangles are present.

Conditons :
1. The rectangles will always enclose some 0’s. e.g. last two vertical lines does not constitute a rectangle.

Compute all possible Vertical/Horizontal lines in this matrix first. Then check overlap b/w horizontal and Vertical lines to detect rectangles.

Integral Image concept is there to compute any rectangle sum (any size, any location) to check whether it contains zeros.

This traverses n elements twice, so it's O(n)

/*
 * FindRectangle.cc
 *
 *  Created on: Apr 21, 2014
 *      Author: Tom Tong
 */

#include <iostream>
#include <vector>

using namespace std;

class TrackNode {
public:
	TrackNode() : right_(0), below_(0) {}

	int getRight() { return right_; }
	void addRight(TrackNode n) { right_ += n.getRight() + 1; }
	void setRight(int i) { right_ = i; }

	int getBelow()  { return below_; }
	void addBelow(TrackNode n) { below_ += n.getBelow() + 1; }
	void setBelow(int i) { below_ = i; }

protected:
	int right_, below_;
};



int main(int , char**)
{
	int matrix[][6]=  {0,0,1,1,1,1,
					   1,1,1,0,1,1,
					   1,0,1,0,1,1,
					   1,1,1,0,1,1,
					   0,0,1,0,1,1,
					   0,1,1,0,1,1,
					   0,0,1,1,1,1};

	int width = sizeof(matrix[0])/sizeof(matrix[0][0]);
	int height = sizeof(matrix)/sizeof(matrix[0]);
	cout << "w:" << width << ", h:" << height << endl;

	vector<TrackNode> nodes(width*height);
	int i, j;
	// this is O(n), since it traverses the matrix once.
	for(j = height - 1; j >= 0; j--)
		for(i = width - 1; i >= 0; i--)
		{
			if (matrix[j][i] != 0)
			{
				int pos = j*width+i;
				TrackNode& node = nodes[pos]; // 6*6+5 is the last one
				if (j == (height-1)) // end of row
					node.setBelow(1);
				else
					node.addBelow(nodes[pos + width]);
				if (i == (width-1)) // end of col
					node.setRight(1);
				else
					node.addRight(nodes[pos + 1]);
			}
		}

	// this is just for displaying data, not counted for O().
	for(j = 0; j < height; j++)
	{
		for(i = 0; i < width; i++)
		{
			cout << nodes[j*width+i].getRight() << "," << nodes[j*width+i].getBelow() << " ";
		}
		cout << endl;
	}

	int countRect = 0;
	// this is O(n), since it traverses the TrackNode vector once.
	for(j = 0; j < height; j++)
		{
			for(i = 0; i < width; i++)
			{
				int pos = j*width+i;
				TrackNode& node = nodes[pos];
				if(node.getRight() > 1 &&
					node.getBelow() > 1)
				{
					TrackNode& left = nodes[pos + node.getRight() - 1];
					TrackNode& below = nodes[pos + (node.getBelow() - 1)*width];
					if (left.getBelow() >= node.getBelow() &&
							below.getRight() >= node.getRight())
					{
						countRect++;
						cout << "rect at corner: " << j << "," << i << endl;
					}
				}
			}
		}

	cout << "found " << countRect << " rectangles." << endl;

	return 0;
}