Spiral Matrix Iii - Leetcode Solution

Problem Statement:

Given two integers R and C, representing the rows and columns of a matrix, and an integer r0 and c0, representing the row and column of the starting cell, return the coordinates of all cells in the matrix, in spiral order.

Example 1: Input: R = 1, C = 4, r0 = 0, c0 = 0 Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2: Input: R = 5, C = 6, r0 = 1, c0 = 4 Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2]]

Solution:

In order to solve this problem, we can start by creating an empty list to hold our coordinates and initializing some variables. We can use a counter variable to keep track of the number of cells we have added to our output list. We can also define the minimum and maximum row and column indices that we will use to traverse our spiral matrix.

Firstly, we can add the starting cell to our output list and increment our counter. Then, we can start traversing our matrix in a spiral pattern. We can use a while loop to continue until we have added all cells to our output list. Inside the while loop, we can add cells in the following order: right, down, left, up. We will continue this pattern until we have added all cells to our output list.

Here is the step-by-step algorithm:

1. Create an empty list to hold our output coordinates.
2. Add the starting cell (r0, c0) to our output list and increment the counter.
3. Define the minimum and maximum row and column indices as follows: min_row, max_row = r0, r0 min_col, max_col = c0, c0
4. Start traversing our matrix in a spiral pattern using a while loop: while counter < R * C:
5. Traverse to the right until we reach the maximum column index: for col in range(min_col + 1, max_col + 1):
6. Add the current cell to our output list and increment the counter: if 0 <= min_row < R and 0 <= col < C: output.append([min_row, col]) counter += 1
7. Update the minimum and maximum row indices: min_row = min(min_row, r0 + counter // 4) max_row = max(max_row, r0 + counter // 4)
8. Traverse down until we reach the maximum row index: for row in range(min_row + 1, max_row + 1):
9. Add the current cell to our output list and increment the counter: if 0 <= row < R and 0 <= max_col < C: output.append([row, max_col]) counter += 1
10. Update the minimum and maximum column indices: min_col = min(min_col, c0 + counter // 4) max_col = max(max_col, c0 + counter // 4)
11. Traverse to the left until we reach the minimum column index: for col in range(max_col - 1, min_col - 1, -1):
12. Add the current cell to our output list and increment the counter: if 0 <= max_row < R and 0 <= col < C: output.append([max_row, col]) counter += 1
13. Update the minimum and maximum row indices: min_row = min(min_row, r0 + (counter // 4) + 1) max_row = max(max_row, r0 + (counter // 4) + 1)
14. Traverse up until we reach the minimum row index: for row in range(max_row - 1, min_row - 1, -1):
15. Add the current cell to our output list and increment the counter: if 0 <= row < R and 0 <= min_col < C: output.append([row, min_col]) counter += 1
16. Update the minimum and maximum column indices: min_col = min(min_col, c0 + (counter // 4) + 1) max_col = max(max_col, c0 + (counter // 4) + 1)
17. Return the output list of coordinates.

Here is the Python implementation of the above algorithm:

class Solution: def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]: output = [[r0, c0]] counter = 1 min_row, max_row, min_col, max_col = r0, r0, c0, c0

    while counter < R * C:
        for col in range(min_col + 1, max_col + 1):
            if 0 <= min_row < R and 0 <= col < C:
                output.append([min_row, col])
                counter += 1
        min_row = min(min_row, r0 + (counter // 4))
        max_row = max(max_row, r0 + (counter // 4))
        
        for row in range(min_row + 1, max_row + 1):
            if 0 <= row < R and 0 <= max_col < C:
                output.append([row, max_col])
                counter += 1
        min_col = min(min_col, c0 + (counter // 4))
        max_col = max(max_col, c0 + (counter // 4))
        
        for col in range(max_col - 1, min_col - 1, -1):
            if 0 <= max_row < R and 0 <= col < C:
                output.append([max_row, col])
                counter += 1
        min_row = min(min_row, r0 + (counter // 4) + 1)
        max_row = max(max_row, r0 + (counter // 4) + 1)
        
        for row in range(max_row - 1, min_row - 1, -1):
            if 0 <= row < R and 0 <= min_col < C:
                output.append([row, min_col])
                counter += 1
        min_col = min(min_col, c0 + (counter // 4) + 1)
        max_col = max(max_col, c0 + (counter // 4) + 1)
    
    return output

Time Complexity:

The time complexity of this algorithm is O(max(R, C)^2) because in the worst case, we will have to traverse the entire matrix in a spiral pattern. The outer loop runs for R * C times, while the inner loops (traversing right, down, left, and up) can each run for at most (max(R, C) - 1) // 2 times.

Space Complexity:

The space complexity of this algorithm is O(R * C) because we need to store the output list of coordinates.

1