medium Spiral Matrix III

Problem Statement

You are given four positive integers rows, cols, rStart, and cStart. You start at cell (rStart, cStart) in a grid of size rows x cols. The grid's top-left corner is at (0, 0) and the bottom-right corner is at (rows-1, cols-1).

You need to visit every cell of this grid by walking in a clockwise spiral pattern. If you move outside the grid's boundaries, you continue walking outside but will return to the grid later.

Return an array of coordinates representing the order of cells visited during this walk.

Examples

1. Example 1:

• Input: rows = 4, cols = 4, rStart = 2, cStart = 2

• Output: [[2,2],[2,3],[3,3],[3,2],[3,1],[2,1],[1,1],[1,2],[1,3],[3,0],[2,0],[1,0],[0,0],[0,1],[0,2],[0,3]]
• Explanation: Start at (2,2), move right to (2,3), down to (3,3), left to (3,2), (3,1), up to (2,1), and continue to other cells in a similar way.

1. Example 2:

• Input: rows = 3, cols = 3, rStart = 0, cStart = 0

• Output: [[0,0],[0,1],[1,1],[1,0],[0,2],[1,2],[2,2],[2,1],[2,0]]
• Explanation: Start at (0,0), move right to (0,1), continue down to (1,1), then left to (1,0), then out of boundary and reach to (0,2), down to (1,2), (2,2), and finally left to (2,1), (2, 0).

1. Example 3: - Input: rows = 5, cols = 5, rStart = 4, cStart = 4

• Output: [[4,4],[4,3],[3,3],[3,4],[4,2],[3,2],[2,2],[2,3],[2,4],[4,1],[3,1],[2,1],[1,1],[1,2],[1,3],[1,4],[4,0],[3,0],[2,0],[1,0],[0,0],[0,1],[0,2],[0,3],[0,4]]
• Explanation: Output shows the spiral matrix traversal according to the problem statement.

Constraints:

• 1 <= rows, cols <= 100
• 0 <= rStart < rows
• 0 <= cStart < cols

Solution

To solve this problem, we'll simulate the movement in a spiral pattern starting from the given initial cell. We'll maintain the current direction, changing directions when necessary to cover the entire grid. We'll keep moving in the current direction until we need to turn, ensuring we cover all cells. The traversal continues even if the current cell goes out of bounds, ensuring we eventually return to valid cells. This method ensures all cells are visited systematically and in the correct order. We'll store the coordinates of the visited cells in a result array.

Step-by-Step Algorithm

1. Initialize Variables:

   • Create a 2D array result to store the coordinates of cells in the order they are visited.
   • Set initial direction to right (dx = 0, dy = 1).
   • Initialize numVisited = 0 to keep track of the number of cells visited.
   • Initialize directionChange = 0 to count the number of direction changes.
   • Use a temporary variable temp for swapping directions.

2. Loop Until All Cells Are Visited:

   • While numVisited < rows * cols:
     • This ensures we visit all cells in the grid.
     • Increment directionChange at the start of each iteration to handle the next direction change.

3. Move in the Current Direction:

   • For each step in the range 0 to directionChange // 2 + 1:
     • The number of steps taken in each direction increases by one after every two direction changes, ensuring the spiral pattern.
     • Check if the current cell is within grid boundaries:
       • If 0 <= rStart < rows and 0 <= cStart < cols:
         • Record the cell's coordinates in result and increment numVisited.
     • Move to the next cell in the current direction by updating rStart and cStart with dx and dy.

4. Change Direction:

   • After completing the steps in the current direction:
     • Swap directions:
       • Use temp to temporarily hold dx.
       • Update dx to dy and dy to -temp to change direction in the order: right -> down -> left -> up.

5. Return the Result:

   • After all cells are visited, return the result array containing the coordinates of cells in the spiral order.

Algorithm Walkthrough

For rows = 4, cols = 4, rStart = 2, cStart = 2:

1. Initialization:

   • result = []
   • Initial direction: right (dx = 0, dy = 1)
   • numVisited = 0
   • directionChange = 0
   • Starting cell: (2, 2)

2. Traversal:

   • Step 1:

     • Move right 1 step:
       • Visit (2, 2), append to result, increment numVisited to 1
       • rStart = 2, cStart = 3
     • Change direction to down:
       • dx = 1, dy = 0
     • Increment directionChange to 1

   • Step 2:

     • Move down 1 step:
       • Visit (2, 3), append to result, increment numVisited to 2
       • rStart = 3, cStart = 3
     • Change direction to left:
       • dx = 0, dy = -1
     • Increment directionChange to 2

   • Step 3:

     • Move left 2 steps:
       • Visit (3, 3), append to result, increment numVisited to 3
       • rStart = 3, cStart = 2
       • Visit (3, 2), append to result, increment numVisited to 4
       • rStart = 3, cStart = 1
     • Change direction to up:
       • dx = -1, dy = 0
     • Increment directionChange to 3

   • Step 4:

     • Move up 2 steps:
       • Visit (3, 1), append to result, increment numVisited to 5
       • rStart = 2, cStart = 1
       • Visit (2, 1), append to result, increment numVisited to 6
       • rStart = 1, cStart = 1
     • Change direction to right:
       • dx = 0, dy = 1
     • Increment directionChange to 4

   • Step 5:

     • Move right 3 steps:
       • Visit (1, 1), append to result, increment numVisited to 7
       • rStart = 1, cStart = 2
       • Visit (1, 2), append to result, increment numVisited to 8
       • rStart = 1, cStart = 3
       • Visit (1, 3), append to result, increment numVisited to 9
       • rStart = 1, cStart = 4 (out of bounds)
     • Change direction to down:
       • dx = 1, dy = 0
     • Increment directionChange to 5

   • Step 6:

     • Move down 3 steps:
       • Visit (2, 4), (3, 4), and (4, 4). All are out of bounds.
     • Change direction to left:
       • dx = 0, dy = -1
     • Increment directionChange to 6

   • Step 7:

     • Move left 4 steps:
       • Visit (4, 3), (4, 2), (4, 1) and (4, 0). All are out of bounds.
     • Change direction to up:
       • dx = -1, dy = 0
     • Increment directionChange to 7

   • Step 8:

     • Move up 4 steps:
       • Visit (3, 0), append to result, increment numVisited to 10
       • rStart = 2, cStart = 0
       • Visit (2, 0), append to result, increment numVisited to 11
       • rStart = 1, cStart = 0
       • Visit (1, 0), append to result, increment numVisited to 12
       • rStart = 0, cStart = 0
       • Visit (0, 0), append to result, increment numVisited to 13
       • rStart = 0, cStart = 1
     • Change direction to right:
       • dx = 0, dy = 1
     • Increment directionChange to 8

   • Step 9:

     • Move right 5 steps:
       • Visit (0, 1), append to result, increment numVisited to 14
       • rStart = 0, cStart = 2
       • Visit (0, 2), append to result, increment numVisited to 15
       • rStart = 0, cStart = 3
       • Visit (0, 3), append to result, increment numVisited to 16
       • rStart = 0, cStart = 4
       • Visit other elements but which are out of bounds.

3. Return Result:

   • Once all cells are visited, return the result array containing the coordinates of visited cells.

The final output will be: [[2,2],[2,3],[3,3],[3,2],[3,1],[2,1],[1,1],[1,2],[1,3],[3,0],[2,0],[1,0],[0,0],[0,1],[0,2],[0,3]]

Code

public class Solution {

  public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    int[][] result = new int[rows * cols][2];
    int dx = 0,
      dy = 1; // Initial direction: right
    int numVisited = 0; // Number of cells visited
    int directionChange = 0; // Number of direction changes
    int temp; // Temporary variable for swapping directions

    for (int steps = 0; numVisited < rows * cols; ++directionChange) {
      for (int step = 0; step < directionChange / 2 + 1; ++step) {
        // Check if the current cell is within grid boundaries
        if (
          0 <= rStart && rStart < rows && 0 <= cStart && cStart < cols
        ) result[numVisited++] = new int[] { rStart, cStart };

        // Move to the next cell in the current direction
        rStart += dx;
        cStart += dy;
      }
      // Change direction: right -> down -> left -> up
      temp = dx;
      dx = dy;
      dy = -temp;
    }
    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] result1 = solution.spiralMatrixIII(4, 4, 2, 2);
    printResult(result1);
    int[][] result2 = solution.spiralMatrixIII(3, 3, 0, 0);
    printResult(result2);
    int[][] result3 = solution.spiralMatrixIII(5, 5, 4, 4);
    printResult(result3);
  }

  private static void printResult(int[][] result) {
    for (int[] cell : result) {
      System.out.print("[" + cell[0] + "," + cell[1] + "] ");
    }
    System.out.println();
  }
}

Complexity Analysis

Time Complexity:

• The algorithm iterates over each cell of the grid exactly once. Since the total number of cells is rows * cols, the time complexity is .

Space Complexity:

• The result array stores the coordinates of all cells in the grid, which requires space proportional to the number of cells. Thus, the space complexity is .