Print Matrix

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in company
ZS Associates

Problem statement

You are given two integers N and M. You are required to return the matrix of size N * M characters such that every element of the matrix can be X or O, and it must satisfy the following condition.

The Xs and Os must be filled. Alternatively, the matrix should have the outermost rectangle of Xs, then a rectangle of Os, then a rectangle of Xs, and so on.

For Example: 
N = 3 and M = 3

Required Matrix-

XXX
XOX
XXX
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘M’ denoting the number of rows and columns in the required matrix.
Output Format: 
For each test case print 'N' strings denoting 2D matrix satisfying the above conditions.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function and return the matrix.
Constraints: 
1 <= T <= 50
1 <= N <= 100
1 <= M <= 100

Time Limit: 1 sec.
Sample Input 1:
2
4 4
3 4
Sample Output 1:
XXXX
XOOX
XOOX
XXXX
XXXX
XOOX
XXXX
Explaination:
In test case 1:
N is 4 and M is also 4, so a matrix of size 4 * 4 is required to output. In the matrix, the outermost rectangle is filled with X and then adjacent to it with O and so on. 

Hence the required matrix will be :
XXXX
XOOX
XOOX
XXXX

In test case 2:
N is 3 and M is also 4, so a matrix of size 3 * 4 is required to output. In the matrix, the outermost rectangle is filled with X and then adjacent to it with O and so on. 

Hence the required matrix will be :
XXXX
XOOX
XXXX
Sample Input 2:
2
5 3
1 2
Sample Output 2:
XXX
XOX
XOX
XOX
XXX
XXX
Hint

Try to fill each rectangle one by one.

Approaches (1)
Iterative approach

We can see that for, given ‘N’ and ‘M’, we have exactly (min('N', ‘M’) + 1) / 2 rectangles to fill. So, we can iterate through each and every rectangle starting from the outermost one and fill it with the required character. 

 

Algorithm-

 

  1. Declare empty matrix of size ‘N’  * ‘M’
  2. Find the value of (min( 'N' , ‘M’ ) + 1) / 2 and store it in integer ‘T’.
  3. Run a loop on ‘T’ from 0 to ‘T’ - 1.
    • initialize two variables ‘X’ and ‘Y’, with the value ‘T’.
    • Using a while loop increment ‘X’ till ‘N’ - ‘T’ with constant ‘Y’ and for each position update the value at that position. If ‘T’ is even, then the value will be ‘O’ else ‘X’.
    • Now, Increment Y with the same procedure till ‘M’ - ‘T’  and update the value at that position and again after 'Y' is ‘N’ - ‘T’ decrement ‘X’ till ‘T’ and update the value at each position.
    • At last, decrement the ‘Y’ till ‘T’ and update the value of each position.
  4. Return the matrix.
Time Complexity

O(N * M), where ‘N’ is the number of rows in the matrix and ‘M’ is the number of columns in the matrix.

 

We are visiting each cell at once so it will take ‘N’ * ‘M’ iterations, hence, time complexity will be O(N * M). 

Space Complexity

O(N * M), where ‘N’ is the number of rows in the matrix and ‘M’ is the number of columns in the matrix.

 

We are using a matrix of size ‘N’  *  ‘M’ to store the answer so, space complexity will be O(N * M). 

Code Solution
(100% EXP penalty)
Print Matrix
Full screen
Console