Last Updated: 19 Apr, 2021
Spiral Matrix III
Moderate
Asked in company
You are given a 2D matrix with ‘N’ rows and ‘M’ columns. The top-left cell has coordinates (0, 0), and the bottom-right cell has coordinates (N - 1, M - 1).
Ninja is initially at the cell with coordinates (R, C) and facing towards the east. He starts walking in a clockwise spiral shape and stops once he has covered each cell in our matrix.
Note:
Ninja continues to walk even if he steps outside the matrix in a clockwise spiral direction.
You have to find the list of coordinates present on the matrix in the order that Ninja visited them.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the number of rows and columns of the matrix.
The second line of each test case contains two space-separated integers, ‘R’ and ‘C’, denoting the initial coordinates of Ninja.
Output Format :
For each test case, return the list of coordinates present on the matrix in the order Ninja visited them.
Output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 1000
1 <= M <= 1000
0 <= R < N
0 <= C < M
Time Limit: 1sec
Approaches
We can simulate the position of Ninja at each time ignoring if he is on or off the matrix. Just by a little observation, we can note that the length of the straight paths are 1, 1, 2, 2, 3, 3, 4, 4, 5, 5…. This means that we move 1 step east, 1 step south, 2 steps west, 2 steps north, 3 steps east, and so on.
We can use this observation to simply simulate the position of Ninja and append the coordinates to a RESULT list if it lies in the matrix.
Algorithm:
- Store the initial position in variables ‘R’ and ’C’.
- Store direction of Ninja in a variable ‘NINJA_DIR’ from four possible directions mapped as follows:
- East => 0
- South => 1
- West => 2
- North => 3
- Initialize the resulting list as a 2D array ‘RESULT’, where each element of this would contain a list of 2 integers, which denote the coordinates of that cell. The array should be empty initially.
- While all points of the matrix are not visited, do:
- If the (‘R’, ‘C’) is within the matrix, insert it into ‘RESULT’.
- Update ‘R’ and ‘C’ using the observation made above.
- Update ‘NINJA_DIR’ while changing directions.
- Return 'RESULT'.