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

 

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

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding   🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Justin
Guest
Justin

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();
}

}

}

wpDiscuz