CareerCup

the idea is use DP to find the height, left, right for each element.

if(matrix[i][j] == '0'){
height[i][j] = 0; left[i][j] = 0; right[i][j] = 0; //because it's an obstacle
}
else{
height[i][j] = 1 --- if matrix[i-1][j] == '0';
height[i][j] = matrix[i-1][j] + 1 --- otherwise

left[i][j] = max(left[i-1][j], the index of the first obstacle on the element's left);
right[i][j] = min(right[i-1][j], the index of the first obstacle on the element's right)
}

then we just go through the elements and find the max area, which is height*(right-left).

idea from: hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba

//oj.leetcode.com/problems/maximal-rectangle/
public int maximalRectangle(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0){
            return 0;
        }
        else{
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] lefts = new int[row][col];
            int[][] rights = new int[row][col];
            int[][] heights = new int[row][col];
            int[] leftObs = new int[col];
            int[] rightObs = new int[col];
            
            findLeftRightObs(0, matrix, leftObs, rightObs);
            
            for(int i=0; i<col; i++){
                if(matrix[0][i] != '0'){
                    heights[0][i] = 1;
                    lefts[0][i] = leftObs[i];
                    rights[0][i] = rightObs[i];
                }
            }
            
            for(int i=1; i<row; i++){
                findLeftRightObs(i, matrix, leftObs, rightObs);
                for(int j=0; j<col; j++){
                    if(matrix[i][j] != '0'){
                        if(matrix[i-1][j] == '0'){
                            heights[i][j] = 1;
                            lefts[i][j] = leftObs[j];
                            rights[i][j] = rightObs[j];
                        }
                        else{
                            heights[i][j] = 1+heights[i-1][j];
                            lefts[i][j] = (int)Math.max(lefts[i-1][j], leftObs[j]);
                            rights[i][j] = (int)Math.min(rights[i-1][j], rightObs[j]);
                        }
                    }
                }
            }
            int max = 0;
            for(int i=0; i<row; i++){
                for(int j=0; j<col; j++){
                    if((rights[i][j]-lefts[i][j])*heights[i][j]>max){
                        max = (rights[i][j]-lefts[i][j])*heights[i][j];
                    }
                }
            }
            return max;
        }
    }
    
    public void findLeftRightObs(int row, char[][] matrix, int[] leftObs, int[] rightObs){
        int obs = 0;
        for(int i=0; i<matrix[0].length; i++){
            if(matrix[row][i] == '0'){
                leftObs[i] = i;
                obs = i+1;
            }
            else{
                leftObs[i] = obs;
            }
        }
        obs = matrix[0].length;
        for(int i=matrix[0].length-1; i>=0; i--){
            if(matrix[row][i] == '0'){
                rightObs[i] = obs;
                obs = i;
            }
            else{
                rightObs[i] = obs;
            }
        }
    }

How many google interviews are you having the last few weeks? WOAH.

hi Obiwana/GZPenny

int min_i = w;
int min_j = h;
int max_i = 0;
int max_j = 0; 

for ( int i = 0; i < min_i; ++i )
{
    int j = 0;
    while ( j < min_j && a[i][j] == 0 )
    {
        j++;
    }
    min_j = j;

    int j2 = w;
    while ( j2 > max_j && a[i][j2 - 1] == 0 )
    {
        j2--;
    }
    max_j = j2;
}

max_i--;
max_j--;

Is this question correct Min rectangle?
If you go for min rectangle then it should be of 1x1.

Scan through the array and store the (min_i, min_j) and (max_i, max_j) where a[i][j] == 1

int min_i = w;
int min_j = h;
int max_i = 0;
int max_j = 0;

for ( int i = 0; i < h; ++i )
{
int j = 0;
while ( j < min_j && a[i][j] == 0 )
{
j++;
}
min_j = j;

int j2 = w;
while ( j2 > max_j && a[i][j2 - 1] == 0 )
{
j2--;
}
max_j = j2;

if ( j < min_j)
{
min_i = min(i, min_i);
max_i = max(i+1, max_i);
}
}

max_i--;
max_j--;

int min_i = w; 
  int min_j = h; 
  int max_i = 0; 
  int max_j = 0; 

  for ( int i = 0; i < h; ++i ) 
  { 
    int j = 0; 
    while ( j < min_j && a[i][j] == 0 ) 
    { 
      j++; 
    } 
    min_j = j; 

    int j2 = w; 
    while ( j2 > max_j && a[i][j2 - 1] == 0 ) 
    { 
      j2--; 
    } 
    max_j = j2; 

    if ( j < min_j) 
    { 
      min_i = min(i, min_i); 
      max_i = max(i+1, max_i); 
    } 
  } 

  max_i--; 
  max_j--;

I guess the problem is to find out the max rectangle. It can be done with Dynamic Programming.
1) Create an array with size of the given array i.e. Sol[m][n] which is an array of tuple(left, right) and let input array by A[m][n]
2) Outer loop (i) from left to right and inner loop (j) from top to bottom
3) if A[j,i] = 0 then Sol[j,i] = (0,0)
else
Sol[j,i] = (Sol[j,i-1].right+1, Sol[j-1,i].left + 1)
The max rectangle will be where the product of the tuple is max. Here is how the solution array looks like

(0,0) (0,0) (0,0) (0,0) (0,0)
(0,0) (1,1) (1,2) (1,3) (0,0)
(0,0) (2,1) (2,2) (0,0) (0,0)
(0,0) (3,1) (0,0) (0,0) (0,0)
(0,0) (0,0) (0,0) (0,0) (0,0)

Time Complexity O(mn)
Space Complexity O(mn)

Maximum size square sub-matrix with all 1s
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

 
   0  1  1  0  1 
   1  1  0  1  0 
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0
The maximum square sub-matrix with all set bits is

    1  1  1
    1  1  1
    1  1  1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
     a)	Copy first row and first columns as it is from M[][] to S[][]
     b)	For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print 
   sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

---From : geeksforgeeks

trying to shrink the map from the edge to find the rectangle, ideally this won't need to visit all the nodes, worst case if there's only one black in the middle, will need to visit extra 1.5row.

#include <iostream>
#include <vector>

void findMinRectangle(const vector<vector<int> > &map) {
  const int num_row = map.size();
  const int num_column = map[0].size();

  int row_min = 0;
  int column_min = 0;
  int row_max = num_row - 1;
  int column_max = num_column - 1;

  // Finds the top.
  bool find_black = false;
  for (; row_min < num_row; ++row_min) {
    for (const auto &c: map[row_min]) {
      if (c == 1) {
        find_black = true;
        break;
      }
    }
    if (find_black) break;
  }
  if (!find_black) {
    // There is no black point in the map.
    cout << "No black in the map." << endl;
    return;
  }
  // Finds the left.
  find_black = false;
  for (; column_min < num_column; ++column_min) {
    for (int r = row_min; r < num_row; ++r) {
      if (map[r][column_min] == 1) {
        find_black = true;
        break;
      }
    }
    if (find_black) break;
  }
  // Finds the bottom.
  find_black = false;
  for (; row_max > row_min; --row_max) {
    for (int c = column_min; c < num_column; ++c) {
      if (map[row_max][c] == 1) {
        find_black = true;
        break;
      }
    }
    if (find_black) break;
  }
  // Finds the right.
  find_black = false;
  for (; column_max > column_min; --column_max) {
    for (int r = row_min; r <= row_max; ++r) {
      if (map[r][column_max] == 1) {
        find_black = true;
        break;
      }
    }
    if (find_black) break;
  }
  cout << 
      "(" << row_min << "," << column_min << ") - (" << 
      row_max << "," << column_max << ")" << endl;
}

As everyone else here, I'll assume the problem asks for the maximum rectangle (given by max area) found on the matrix. Also, my approach will only return the area of the max rectangle as opposed to returning the corner indexes (implementing this would be trivial based on my solution):

For each cell, determine the size of the largest row of non-obstacle spaces achievable.

Then, for each cell get the biggest of all possible rectangles created by all non-obstacle cells from the columns that start at the current cell and grow from bottom to top times the minimum of the largest row size (calculated before) of each row in the column.

Example:

0 0 1
0 1 1
1 1 1

Largest rows:
0 0 1
0 1 2
1 2 3

List of all possible max-rectangles per cell:
{ } { } { (1x1) }
{ } { (1x1) } { (2x1), (1x2) }
{ (1x1) } { (2x1), (1x2) } { (3x1), (2x2), (1x3) }

The maximum rectangle area is 4 because at cell (2,2) there exists a column of size 2 with widest achievable row of 2.

Time complexity: O(n^3) // Assuming board is nxn
Space complexity: O(n^2)

Code:

bool board [MAX_WIDTH][MAX_HEIGHT];
int max_rows [MAX_WIDTH][MAX_HEIGHT];

int rect_max_area(bool board [][MAX_HEIGHT], const int width, const int height)
{
    memset(max_rows, 0, width * height * sizeof(int));

    int max_area = 0;
    for (int row_index = 0; row_index < height; row_index++)
        for (int col_index = 0; col_index < width; col_index++)
            if (board[row_index][col_index])
            {
                max_rows[row_index][col_index] = 1;
                if (col_index > 0 && board[row_index][col_index - 1])
                    max_rows[row_index][col_index] +=
                        max_rows[row_index][col_index - 1];

                int height = 1;
                int local_max_area = 0;
                int h_index = row_index;
                int min_width = max_rows[row_index][col_index];
                while (h_index >= 0 && board[h_index][col_index])
                {
                    local_max_area = max(local_max_area, height * min_width);

                    height++;
                    h_index--;
                    min_width = min(min_width, max_rows[h_index][col_index]);
                }

                max_area = max(max_area, local_max_area);
            }

    return max_area;
}

The statement of the question is not clear. The clear statement should be: Find the largest rectangle that contains only 1's. For example, in the following case:
01
10
The largest one is only 1 because that the largest rectangle we can find that contains only 1's.

This is just Connected Component of graph theory problem I think (unless I am missing something?). So the solution would be to scan for the first black node, and then from there it's just a breadth or depth first search of "connected' nodes (that is, adjacent black ones) where that node hasn't already been visited. A recursive call passing int references for the min/max of x/y will yield the min rectangle coordinates. I did this is C# and can post that or convert to C++ since that seems to be preferred here. From wikipedia on Connected Component "It is straightforward to compute the connected components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning."

in C#

static int[][] PreCompute(int[][] matrix)
{
int rank = matrix[0].Length;
int[][] sum = new int[matrix.Length][];
for (int i = 0; i < matrix.Length; ++i)
{
sum[i] = new int[rank];

for (int j = 0; j < matrix[0].Length; ++j)
{
if (i == 0)
{
sum[i][j] = matrix[i][j];
}
else
{
sum[i][j] = sum[i-1][j] + matrix[i][j];
}
}
}

return sum;
}

static int FindMaxBlacks(int[][] matrix)
{
int[][] sum = PreCompute(matrix);
int x1 = 0;
int x2 = 0;
int y1 = 0;
int y2 = 0;
int maxSum = 0;
for (int i = 0; i < matrix.Length; ++i)
{
for (int j = i; j < matrix.Length; ++j)
{
int currentSum = 0;
int start = -1;
int end = -1;
for (int k = 0; k < matrix[0].Length; ++k)
{
int value = sum[j][k] - sum[i][k] + matrix[i][k];
if (value == j - i + 1)
{
if (start == -1)
{
start = k;
end = k;
}
else
{
end = k;
}
currentSum += value;
}
else
{
if (currentSum > maxSum)
{
x1 = i;
x2 = j;
y1 = start;
y2 = end;
maxSum = currentSum;
}

currentSum = 0;
start = -1;
end = -1;
}
}
}
}
Console.WriteLine("start = ({0}, {1}), end = ({2}, {3})", x1, y1, x2, y2);
return maxSum;
}

import sys

min_x = min_y = sys.maxint
max_x = max_y = -1

cur_y = -1

for line in sys.stdin:
    cur_y = cur_y + 1
    nodes = [int(token) for token in line.strip().split()]
    if 1 in nodes:       
        max_y = cur_y
        if min_y == sys.maxint:
            min_y = cur_y
        if nodes.index(1) < min_x:
            min_x = nodes.index(1)
        nodes.reverse()
        i = len(nodes) - 1 - nodes.index(1)
        if i > max_x:
            max_x = i

print min_x, min_y, max_x, max_y

#include<stdio.h>

void findSmallestRect(int matrix[6][6], int rows, int cols);

int main(void)
{

int matrix[6][6] =
{
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};

findSmallestRect(matrix, 6, 6);

return 0;

}

void findSmallestRect(int matrix[6][6], int rows, int cols)
{

bool rectCreated = false;

int top;
int bottom;

int left;
int right;

for(int row = 0; row < rows; row++)
{

for(int col = 0; col < cols; col++)
{

if(matrix[row][col])
{

if(!rectCreated)
{

top = row;
bottom = row;

left = col;
right = col;

rectCreated = true;

}
else
{

if(row < top)
{
top = row;
}
else if(row > bottom)
{
bottom = row;
}

if(col < left)
{
left = col;
}
else if(col > right)
{
right = col;
}

}

}

}

}

printf("Top: %d\n", top);
printf("Bottom: %d\n", bottom);

printf("Left: %d\n", left);
printf("Right: %d\n", right);

}

#include<stdio.h>

void findSmallestRect(int matrix[6][6], int rows, int cols);

int main(void)
{

	int matrix[6][6] = 
	{
		{0, 0, 0, 0, 0, 0}, 
		{0, 0, 0, 1, 0, 0}, 
		{0, 0, 1, 1, 0, 0}, 
		{0, 1, 1, 1, 1, 0}, 
		{0, 0, 0, 0, 0, 0}, 
		{0, 0, 0, 0, 0, 0}
	};

	findSmallestRect(matrix, 6, 6);

	return 0;

}

void findSmallestRect(int matrix[6][6], int rows, int cols)
{

	bool rectCreated = false;

	int top;
	int bottom;

	int left;
	int right;

	for(int row = 0; row < rows; row++)
	{
	
		for(int col = 0; col < cols; col++)
		{

			if(matrix[row][col])
			{

				if(!rectCreated)
				{
			
					top = row;
					bottom = row;
				
					left = col;
					right = col;

					rectCreated = true;
			
				}
				else
				{
			
					if(row < top)
					{
						top = row;
					}
					else if(row > bottom)
					{
						bottom = row;
					}

					if(col < left)
					{
						left = col;
					}
					else if(col > right)
					{
						right = col;
					}

				}
			
			}
		
		}
	
	}

	printf("Top: %d\n", top);
	printf("Bottom: %d\n", bottom);

	printf("Left: %d\n", left);
	printf("Right: %d\n", right);

}

package com.google.practice;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Pointe implements Comparable<Pointe>{
	int x;
	int y;
	int pointSpot;
	public Pointe(int x,int y,int pointSpot){
		this.x = x;
		this.y = y;
		this.pointSpot = pointSpot;
	}
	@Override
	public int compareTo(Pointe o) {
		// TODO Auto-generated method stub
		return Double.compare(this.pointSpot, o.pointSpot);
	}
}

public class BlacknWhite {
	public static void main(String[] arg){
		int n=5,m=5;
		int[][] board = {{0,0,0,0,0},
						 {0,0,0,0,0},
						 {0,0,0,0,0},
						 {0,0,0,0,0},
						 {0,0,0,0,1}};
		
		findMinRec(board,n,m);						
	}
	
	public static void findMinRec(int[][] board,int n,int m){
		List<Pointe> corner = findTopCorner(board,n);
		Collections.sort(corner);
		if(corner.size()==0)
			System.out.println("No Black found");
		else if(corner.size()==1)
			printResult(corner.get(0).x, corner.get(0).y, corner.get(0).x, corner.get(0).y);
		else if(corner.size()==4 || (corner.get(0).pointSpot==1 && corner.get(1).pointSpot==2)){
			int x1 = corner.get(0).x,y1= corner.get(0).y,x2 = corner.get(1).x,y2 = corner.get(1).y;
			if(corner.size()==4 || corner.size()==3){
				if( corner.size()==3){
					if(corner.get(2).pointSpot==3){
						corner.add(new Pointe(corner.get(0).x,corner.get(0).y,4));
					}else
						corner.add(new Pointe(corner.get(1).x,corner.get(1).y,3));
					Collections.sort(corner);
				}
				if(corner.get(3).y < corner.get(0).y)
						y1 = corner.get(3).y;

				if(corner.get(2).x<corner.get(0).x)
						x1 = corner.get(2).x;

				if(corner.get(2).y>corner.get(1).y)
						y2 = corner.get(2).y;

				if(corner.get(3).x>corner.get(1).x)
						x2 = corner.get(3).x;

				}
			printResult(x1, y1, x2, y2);
		}else{
			if(corner.size()==3){
				if(corner.get(0).pointSpot==1){
					printResult(corner.get(0).x, corner.get(0).y, corner.get(1).y, corner.get(2).x);
				}else{
					printResult(corner.get(1).x, corner.get(2).y, corner.get(0).x, corner.get(0).y);
				}
			}else {
				if(corner.get(0).pointSpot==2)
					printResult(corner.get(1).x, corner.get(1).y, corner.get(0).x, corner.get(0).y);
				else
					printResult(corner.get(0).x, corner.get(0).y, corner.get(1).x, corner.get(1).y);
			}
		}
	}
	
	public static List<Pointe> findTopCorner(int[][] board,int n){
		List<Pointe> points = new ArrayList<Pointe>();
		
		boolean topLeft=false;Pointe tLeft = new Pointe(-1,-1,1);
		boolean topRight=false;Pointe tRight = new Pointe(-1,-1,3);
		boolean bottomLeft=false;Pointe bLeft = new Pointe(-1,-1,4);
		boolean bottomRight=false;Pointe bRight = new Pointe(-1,-1,2);
		
		for(int i1=0,i2=n-1;i1<=n/2;i1++,i2--){
			for(int j1=0,j2=n-1;j1<=n/2;j1++,j2--){
				if(points.size()==4)
					return points;
				if(!topLeft){
					if(board[i1][j1]==1 || board[j1][i1]==1){
						topLeft = true;
						if(board[i1][j1]==1){
							tLeft.x = i1;
							tLeft.y = j1;
						}
						else{
							tLeft.x = j1;
							tLeft.y = i1;
						}
						points.add(tLeft);
					}
				}
				if(!topRight){
					if(board[i1][j2]==1 || board[j1][i2] == 1){
						topRight = true;
						if(board[i1][j2]==1){
							tRight.x = i1;
							tRight.y = j2;
						}
						else{
							tRight.x = j1;
							tRight.y = i2;
						}
						points.add(tRight);
					}
				}
				if(!bottomLeft){
					if(board[i2][j1]==1 || board[j2][i1]==1){
						bottomLeft = true;
						if(board[i2][j1]==1){
							bLeft.x = i2;
							bLeft.y = j1;
						}
						else{
							bLeft.x = j2;
							bLeft.y = i1;
						}
						points.add(bLeft);
					}
				}
				if(!bottomRight){
					if(board[i2][j2]==1 || board[j2][i2]==1){
						bottomRight = true;
						if(board[i2][j2]==1){
							bRight.x = i2;
							bRight.y = j2;
						}
						else{
							bRight.x = j2;
							bRight.y = i2;
						}
						points.add(bRight);
					}
				}
			}
		}
		return points;
	}
	
	public static void printResult(int x1,int y1,int x2,int y2){
		System.out.println("("+x1+","+y1+")-("+x2+","+y2+")");
	}
}

Good or bad, this also works for 1's that are not connected. Finds the enclosing minimum rectangle. O(n^2) but pruned to 1/4th of total time.