Spiral Matrix III

Leetcode Problem:

• Spiral Matrix III

Summary

• Find the positions of a 2D grid in a clockwise spiral shape.

Approach

• The solution uses a while loop to traverse the grid in a clockwise spiral shape
• It starts at the given start position and moves in a direction (right, down, left, up) for a specified number of steps
• The direction is updated after each step, and the position is added to the result list if it is within the grid boundaries.

Complexity

• O(rows * cols)

Explain

• The solution uses four arrays `dy` and `dx` to represent the possible directions (up, down, left, right) in the grid
• The `ans_cnt` variable keeps track of the number of positions visited, and the `cnt` variable keeps track of the number of steps in the current direction
• The `dir` variable keeps track of the current direction
• The solution uses a while loop to traverse the grid, and it adds the current position to the result list if it is within the grid boundaries.

Solution Code:

class Solution {
public:
    vector> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector> ans;
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        int ans_cnt = 0;
        int cnt = 1;
        int dir = 0;
        ans.push_back({rStart, cStart});
        ans_cnt++;
        while(ans_cnt < rows * cols){
            for(int i = 0 ; i < 2; i++){
                for(int j = 0 ; j < cnt; j++){
                    rStart += dy[dir];
                    cStart += dx[dir];
                    if (rStart < 0 || rStart >= rows || cStart < 0 || cStart >= cols){
                        continue;
                    }
                    ans.push_back({rStart, cStart});
                    ans_cnt++;
                }
                dir = (dir + 1) % 4;
            }
            cnt++;
        }
        return ans;
    }
};