algoadvance

Leetcode 885. Spiral Matrix III

Problem Statement

You are given R (rows) and C (columns) a positive integer representing the dimensions of a grid. You are also given r0 (starting row) and c0 (starting column) the starting position in the grid.

Return the sequence of cells visited in a spiral order starting from (r0, c0).

The grid will contain R * C elements, and you should return a list of pairs denoting the cells in the grid as they are visited in the spiral order.

Example

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

Constraints

• 1 <= R <= 100
• 1 <= C <= 100
• 0 <= r0 < R
• 0 <= c0 < C

Clarifying Questions

1. Boundaries Check: Do we need to handle out of bounds explicitly?
   • No, because you only need to record cells within the grid dimension R x C.
2. Are there any invalid inputs to handle?
   • The constraints ensure valid inputs, so no need to handle invalid inputs explicitly.

Strategy

1. Direction & Moves:
   • Consider directions as Right, Down, Left, Up corresponding to (0, 1), (1, 0), (0, -1), (-1, 0).
   • Use a direction counter to cycle through the four directions.
2. Spiral Movement:
   • Start from (r0, c0).
   • Increase the steps for which you need to move in the current direction until you cover the grid size.
3. Tracking & Bounds Checking:
   • Ensure that each move is within bounds and track all valid moves.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>> result;
        int directions[4][2] = \{\{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Right, Down, Left, Up
        int steps = 1; // Number of steps in the current direction
        int d = 0; // Direction index

        result.push_back({r0, c0});
        if (R * C == 1) return result; // If the grid is 1x1

        int visited = 1; // Number of cells visited

        while (visited < R * C) {
            for (int i = 0; i < 2; ++i) { // Two turns per distance increment
                for (int j = 0; j < steps; ++j) {
                    r0 += directions[d][0];
                    c0 += directions[d][1];

                    if (r0 >= 0 && r0 < R && c0 >= 0 && c0 < C) { // Within bounds
                        result.push_back({r0, c0});
                        visited++;
                        if (visited >= R * C) return result; // Early exit if all cells visited
                    }
                }
                d = (d + 1) % 4; // Change direction
            }
            steps++; // Increase steps after every full cycle (two turns)
        }

        return result;
    }
};

Time Complexity

• The entire grid will be visited once in a spiral manner.
• Time Complexity: (O(R \times C)) since each cell is visited once.
• Space Complexity: (O(R \times C)) for storing the result vector.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?