algoadvance

Leetcode 885. Spiral Matrix III

Problem Statement

You are given R rows and C columns representing a matrix. You need to traverse the matrix in a spiral order starting from a given starting point (r0, c0). The matrix only contains one integer in each cell. Output the list of coordinates visited in a spiral order.

Clarifying Questions

  1. Are there any constraints on the values of R and C?
    • No specific constraints, but they are positive integers representing the size of the matrix.
  2. What are the permissible ranges for the starting point (r0, c0)?
    • 0 <= r0 < R and 0 <= c0 < C, ensuring the starting point is within matrix bounds.
  3. How should we handle coordinates that are outside the matrix boundaries?
    • Simply skip these coordinates and continue the traversal.

Strategy

  1. Initialize Directions:
    • We will use a list to represent movement directions in the order Right, Down, Left, Up (i.e., clockwise movement).
  2. Initialize Tracking Variables:
    • Use variables to keep track of the current position (r, c), the current direction, and the current number of steps in the current direction.
  3. Traversal Logic:
    • Use a loop to traverse the matrix:
      • Move in the current direction.
      • Collect coordinates if they are within the boundary.
      • Turn the direction when the requisite number of steps in that direction are completed.
      • Adjust the step count as you turn (for spiral logic).
  4. Stopping Condition:
    • The loop ends when we have collected R * C coordinates in the result list.

Code

Here is a Java implementation of the above strategy:

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrixIII {
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        int totalCells = R * C;
        int[][] result = new int[totalCells][2];
        int index = 0;
        
        // Directions: right, down, left, up
        int[][] directions = // use example from above
        int currentDirection = 0;
        int step = 1;
        
        // Start from the initial position
        int r = r0, c = c0;
        result[index++] = new int[]{r, c};
        
        while (index < totalCells) {
            for (int i = 0; i < 2; i++) { // Increment step number a pair of times
                for (int s = 0; s < step; s++) {
                    r += directions[currentDirection][0];
                    c += directions[currentDirection][1];
                    
                    if (r >= 0 && r < R && c >= 0 && c < C) {
                        result[index++] = new int[]{r, c};
                    }
                }
                currentDirection = (currentDirection + 1) % 4; // Turn to next direction
            }
            step++; // Increase step size after two direction turns
        }
        
        return result;
    }
}

Time Complexity

This implementation adheres to the constraints and requirements of the problem, ensuring efficient traversal and correct ordering of matrix coordinates in spiral order.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI