Spiral Matrix III

Moderate
0/80
Average time to solve is 15m
4 upvotes
Asked in company
Flipkart limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 4
1 1
2 1
0 0
Sample Output 1:
1 1
1 2
1 0
0 0
0 1
0 2
0 3
1 3
0 0
1 0

Explanation for Sample 1:

 For the 1st test case:
 The path followed is illustrated below.


Ninja initially starts from position (1, 1) and moves from (1,1) -> (1,2) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3). 
Note that even though (2, 0), (2, 1), (2, 2) and (2, 3) are not in the matrix, Ninja visits those cells, but they should not be included in our result.

For the second test case:
The path followed is: (0,0) -> (0,1) -> (1,1) -> (1,0). Similarly we don’t append coordinates (0, 1) and (1, 1) in the result as they lie outside the matrix.
Sample Input 2 :
2
3 4
1 3
2 2
1 0
Sample Output 2 :
1 3
2 3
2 2
1 2
0 2
0 3
2 1
1 1
0 1
2 0
1 0
0 0
1 0
1 1
0 0
0 1
Hint

Can we simulate the position of Ninja at each point in time?

Approaches (1)
Simulation

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'.
Time Complexity

O(max(N, M) ^ 2), where ‘N’ denotes the number of rows and ‘M’ denotes the number of columns.

 

Note that the number of cells we iterate through is at most 4 * max(N, M) ^ 2 as the side of the rectangle that Ninja visited is at most 2 * max(N, M). 

 

Since for each cell, we do a constant number of operations, the total complexity is O(constant * 2 * max(N, M) ^ 2) which is equivalent to O(max(N, M) ^ 2).

Space Complexity

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

 

Since we are using a 2D array to store our result, the overall space complexity is O(N * M).

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