saket.kumar29
BAN USERpackage com.algo;
import java.util.Arrays;
public class MaxPerimeter {
public static int findMaxPermiter(boolean[][] rect) {
int row = rect.length;
int col = rect[0].length;
int maxPerimeter = 0;
for(int i=0; i<col; i++) {
int[] boundary = new int[row];
for(int j=i;j<col;j++) {
for(int k=0;k<row;k++) {
if(!rect[k][j] || !rect[k][i])
boundary[k] = 0;
else
boundary[k] += 1;
}
int maxWidth = maxConsecutiveNonZero(boundary, j-i+1);
if(maxWidth != 1 && j-i != 0)
maxPerimeter = Math.max(maxPerimeter, 2 * ((j-i+1) + maxWidth-2));
}
}
return maxPerimeter;
}
private static int maxConsecutiveNonZero(int[] boundary, int target) {
//System.out.println(Arrays.toString(boundary) + " target " + target);
int start = -1;
int end = 0;
int maxWidth = 1;
while(end < boundary.length) {
if(start == -1 && boundary[end] == target)
start = end;
else if(boundary[end] == target) {
maxWidth = Math.max(end - start + 1, maxWidth);
} else if(boundary[end] == 0) {
start = -1;
}
end++;
}
//System.out.println("max width " + maxWidth);
return maxWidth;
}
public static void main(String[] args) {
boolean[][] rectange = { {true, true, true, true},
{false, true, true, false},
{true, true, true, true}
};
int ans = findMaxPermiter(rectange);
System.out.println("Perimeter is: " + ans);
}
}
This works work all test cases.
- saket.kumar29 March 15, 2019boundary array keeps count of consecutive 1's and sets it to 0 if start/end boundary element is 0/false.
maxConsecutiveNonZero function returns max consecutive width whose boundary equals target. The target is width of the rectangle.