Matrix Boundary Traversal

Easy
0/40
profile
Contributed by
3 upvotes
Asked in company
Amazon

Problem statement

Given a matrix of integers containing ‘M’ rows and ‘N’ columns. Print the boundary elements of the matrix. The order of printing does not matter.

Note :

The output you will see will be in sorted order.
Your order of output does not matter.
You can return your result in any order.
Example : 
Input: ‘M’ = 2, ‘N’ = 2, ‘MAT’ = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

input

Output: [1, 2, 3, 4, 5, 8, 9, 12, 13, 14, 15, 16]
If we traverse the matrix in clockwise order from the top left then it will be 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5. Which in output will be shown in sorted order which is 1, 2, 3, 4, 5, 8, 9, 12, 13, 14, 15, 16.

output

Referring to the image above, we are printing only the elements that lie on the boundary.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test contains two integers ‘M’ and ‘N’ respectively.

The Next ‘M’ line contains ‘N’ elements denoting the matrix.
Output format : 
For each test case print the boundary elements.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
2 <= T <= 10
1 <= N, M <= 2000

Time Limit: 1 sec
Sample Input 1 :
2
3 2
5 3 
5 7 
5 5 
2 2
6 8 
5 5
Sample Output 1 :
3 5 5 5 5 7
5 5 6 8
Explanation Of Sample Input 1 :
For the first case:
If we do the clockwise traversal of boundary elements from the top left corner the traversal will be 5 3 5 7 5 5 but in output, you will see the elements sorted that is 3 5 5 5 5 7.

For the second case:
If we do the clockwise traversal of boundary elements from the top left corner the traversal will be 6 8 5 5 but in output, you will see the elements sorted that is 5 5 6 8.
Sample Input 2 :
2
3 3
7 3 5 
5 5 5 
8 7 7 
3 3
7 5 7 
7 2 6 
2 8 6
Sample Output 2 :
3 5 5 5 7 7 7 8
2 5 6 6 7 7 7 8
Hint

 Traverse the whole matrix but print only the selected.

Approaches (2)
Brute Force

We can traverse the whole matrix and print only those elements that are boundary elements and for all the other elements we can mark them as whitespace.

 

The steps are as follows:-

  1. Declare another matrix that stores the boundary values named 'ans'.
  2. Traverse the matrix.
  3. For i in the range[0, m-1].
    • For j in range[0, n-1].
      • Check if the i is 0 or m-1 or if j is 0 or j is n-1.
        • Append the value of 'mat[i][j]' into 'ans'.
  4. Return ‘ans’.
Time Complexity

O( N*M ).  

 

We are traversing the whole matrix of size M*N.

Hence time complexity will be O( M*N ).

Space Complexity

O( N + M ), Where N is the number of columns and M is the number of rows.

 

We are storing the answer in the array of size O( N + M ).

Hence space complexity is O( N + M ).

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