Spiral Matrix

Easy
0/40
profile
Contributed by
91 upvotes
Asked in companies
TsysZycus

Problem statement

You are given a 2D matrix ‘MATRIX’ of ‘N’*’M’ dimension. You have to return the spiral traversal of the matrix.

Example:

Input:
MATRIX = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ]
Output:
1 3 5 7 20 60 34 30 23 10 11 16

Explanation: Starting from the element in the first row and the first column, traverse from left to right (1 3 5 7), then top to bottom (20 60), then right to left (34 30 23), then bottom to up (10) and then left to right (11 16).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input will contain two integers denoting the dimensions of the matrix ‘N’ and ‘M’. 
The following 'N' lines contain ‘M’ integers each.
Output Format:- 
Output is printed on a separate line.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints: 
1 <= N, M <= 10^5
1 <= MATRIX [ i ] [ j ] <= 10^9
The sum of N*M over all test cases is less than 2*10^5.
Time Limit: 1 sec
Sample Input 1:
3 3
1 3 7
10 12 15
19 20 21
Sample Output 1:
1 3 7 15 21 20 19 10 12
Explanation Of Sample Input 1:
Input:
MATRIX = [ [1, 3, 7], [10, 12, 15], [19, 20, 21] ], 
Output:
1 3 7 15 21 20 19 10 12

Explanation: Starting from the element in the first row and the first column, traverse from left to right (1 3 7), then top to bottom (15 21), then right to the left (20 19), then bottom to up (10) and then left to right (12).
Sample Input 2:
4 4
1 5 9 13
14 15 16 17
19 20 21 50
59 60 71 80
Sample Output 2:
1 5 9 13 17 50 80 71 60 59 19 14 15 16 21 20
Hint

Stimulate the problem statement.

Approaches (1)
Naive approach

Approach:

  • We print the elements one by one, beginning with the outermost layers.
  • Create and initialize variables with the top as the starting row index, the bottom as the ending row index, the left as the starting column index, and the right as the ending column index.
  • We use 4 for loops. First will print elements from left to the right, then from top to bottom, next from right to left, and from bottom to top at the end.

 

Algorithm:

Function [int] spiralMatrix([int][int] MATRIX):

  1. Initialize four integer variables, ‘top’, ’left, ’bottom’, and ‘right’, to 0, 0, N-1, and M-1, respectively.
  2. Initialize an empty array ‘ans’.
  3. While ‘top’ <= ‘bottom’ and ‘left’ <= ‘right’:
    • For ‘i’ form ‘left’ to ‘right’:
      • ‘ans’.push( MATRIX[top][i] ).
    • ‘top’++
    • for ‘i’ form ‘top’ to ‘bottom’:
      • ‘ans’.push( MATRIX[i][right] ).
    • ‘right’--
    • If ‘top’ <= ‘bottom’
      • for ‘i’ from ‘right’ to ‘left’:
        • ‘ans’.push( MATRIX[bottom][i] ).
      • ‘bottom’–
    • If ‘left’ <= ‘right’
      • for ‘i’ from ‘bottom’ to ‘top’:
        • ‘ans’.push( MATRIX[i][left] ).
      • ‘left’–
  4. Return ‘ans’.
Time Complexity

O( N*M ), Where ‘N’ and ‘M’ are the given matrix ‘MATRIX’ dimensions. 

 

We are traversing all the N*M elements of the matrix. Hence, the overall time complexity will be O( N*M ).

Space Complexity

O( 1 ). 

 

We are taking O( 1 ) extra space for variables. Hence, the overall space complexity will be O( 1 ).

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