Fill Binary Matrix with Alternating Rectangles of 0 and 1

Given a M x N binary matrix, fill it with alternating rectangles of 0 and 1.


For example,


Input: 10 x 8 matrix

Output:

1   1   1   1   1   1   1   1
1   0   0   0   0   0   0   1
1   0   1   1   1   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   1   1   1   0   1
1   0   0   0   0   0   0   1
1   1   1   1   1   1   1   1

 

 
The idea is to fill the matrix by following the spiral order. All elements involved in each alternating run in spiral order are filled by either 0 or 1 based on input from last run. To maintain the spiral order four loops are used, each for top, right, bottom and left corner of the matrix.

C++

Download   Run Code

Output:

1   1   1   1   1   1   1   1
1   0   0   0   0   0   0   1
1   0   1   1   1   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   1   1   1   0   1
1   0   0   0   0   0   0   1
1   1   1   1   1   1   1   1

Java

Download   Run Code

Output:

[1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 1, 1, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 1, 1, 1, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1]

 

Another approach:

A M x N matrix has min(ceil(M/2), ceil(N/2)) rectangular cycles. A cycle is formed by ith row, (N-i+1)th column, (M-i+1)th row and ith column where i varies from 1 to min(ceil(M/2), ceil(N/2)). The idea is for each rectangular cycle, we associate a value to it. For outer cycle, the value will be 0, for second cycle, the value will be 1 and third cycle will have value 2 and so on.. Below figure shows 4 cycles in a 10 x 8 matrix marked by value 0 – 3.


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

Now depending upon whether the assigned value is odd or even for a matrix cell, we assign 0 or 1 to the output matrix.

C++

Download   Run Code

Output:

1   1   1   1   1   1   1   1
1   0   0   0   0   0   0   1
1   0   1   1   1   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   1   1   1   0   1
1   0   0   0   0   0   0   1
1   1   1   1   1   1   1   1

Java

Download   Run Code

Output:

[1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 1, 1, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 1, 1, 1, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1]

 
Time complexity of above solution is O(M*N).
Auxiliary space used by the program is O(1).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding   🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Justin
Guest

nice..

Rev
Guest

public class FillMatrix {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
sc.close();
int[][] matrix=new int[n][n];

for(int j=0;j<n;j++)
{

{
matrix[0][j]=1;
}

}

for(int i=1;i<n/2;i++){
for(int j=0;j<n;j++)
{
int level = i;
if (j =n-level){
matrix[i][j] = matrix[level – 1][j];
}
else {
if (matrix[level-1][j] == 0) {
matrix[i][j] = 1;
} else {
matrix[i][j] = 0;
}
}
}
}

for(int i=0;i<n/2;i++)
{
for(int j=0;j=0;i–)
{
for(int j=0;j<n;j++)
{
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}

}

}