885. Spiral Matrix III
Problem Description
In this LeetCode problem, you are given the dimensions of a grid (rows x cols
) and a starting cell within that grid, defined by its row (rStart
) and column (cStart
). Your task is to simulate a walk from the starting cell in a clockwise spiral pattern until you have visited every cell in the grid. This spiral pattern means you move east, then south, then west, and finally north, increasing the distance you move in a specific direction before turning by one cell each time you complete a full cycle (east, south, west, and north). As you perform this walk, even if you move outside the grid's boundaries, you keep the pattern, and you may return to the grid's boundary later. The goal is to visit all cells on the grid and return a list of their coordinates in the order they were visited.
Intuition
The problem can be solved by simulating the walk in a spiral pattern as described. The intuition behind this solution is to track movement direction and counter changes in direction while traversing the grid. We should keep in mind that it is necessary to handle cases where the walk takes us outside the grid boundary.
We initialize the solution by adding the starting position to our result set. If the grid is of size 1x1, the problem is already solved with this step. For larger grids, we have to begin walking in a spiral. We know that for a spiral walk, the number of steps we take in the east or west directions (horizontal steps) will always be one more than the number of steps we took in the previous vertical movement (north or south). Conversely, the number of steps we take in the north or south direction will be equal to the number of steps we will take in the next horizontal movement.
To implement this pattern, we maintain a variable k
that represents how many steps we should move in the current direction. We start with k = 1
, as the first move after the starting position is just one step to the right (east). We then increase k
by 2 after a full cycle of directions (east > south > west > north) to account for the changing step count in the spiral path.
For each direction, we move k
steps, updating our current position and conditionally add the new position to the result set if it lies within the grid's boundaries. We keep doing so until we have visited all rows * cols
cells.
Solution Approach
The implementation of the solution follows a pattern-based approach by simulating movements on the grid. Here's how it's done step by step:
- We define a list
ans
to keep track of the cells visited, starting with the initial cell[rStart, cStart]
. - We check if the grid size is
1x1
. If so, we immediately returnans
because the single starting cell is the only cell to visit. - We then set
k = 1
, which will determine the number of steps we take in a given direction before turning. Thisk
will be increased as necessary to simulate the spiral pattern. - A
while True
loop begins, which will run until we've visited allrows * cols
cells of the grid. - Inside the loop, we iterate over a list of direction increments and the corresponding step counts. The list has tuples in the format
[dr, dc, dk]
, wheredr
is the row increment (0 for east or west, 1 for south, -1 for north),dc
is the column increment (1 for east, -1 for west, 0 for north or south), anddk
being the number of steps to move in that direction. - For each direction, we run another loop for
dk
steps:- For each step, we update
rStart
andcStart
withdr
anddc
respectively. - We then check if the new position is within the grid's boundaries by verifying
0 <= rStart < rows
and0 <= cStart < cols
. If yes, we append the position toans
. - We check if we have visited
rows * cols
cells. If we have, we returnans
as the complete list of visited cells.
- For each step, we update
- After completing the movement in all four directions, we increment
k
by 2 to maintain the spiral pattern for the next cycle of directions.
The algorithm utilizes simple iteration and directional increments to traverse the grid in a predictable, spiral pattern. No complex data structures are necessary beyond a list to hold the visited cell coordinates. The pattern's consistency allows us to increment k
strategically, ensuring we expand our traversal in a spiraling outward fashion. This method provides full coverage of the grid while recording our path.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider a grid of size 3x3
, where our starting cell is at rStart = 1
and cStart = 1
(the center of the grid).
- We initialize
ans
with the starting cell, soans = [[1, 1]]
. - Since the grid size is not
1x1
, we proceed with the solution. - We set
k = 1
as our initial step length for the eastward move. - Since the grid has more than one cell, we enter the
while True
loop to start the spiral traversal. - The first direction from our starting cell is east. We only need to move one step east (
dc = 1, dr = 0
). We move to cell[1, 2]
, which is within the grid. We add this toans
, resulting inans = [[1, 1], [1, 2]]
. - Next is to move one step south (
dc = 0, dr = 1
). We move to[2, 2]
. Again, it's within the grid, soans
becomesans = [[1, 1], [1, 2], [2, 2]]
. - Following is westward movement, but since
k
is1
, we'd move only one step west (dc = -1, dr = 0
) to[2, 1]
. We add this toans
, making itans = [[1, 1], [1, 2], [2, 2], [2, 1]]
. - The last direction in this cycle is north (
dc = 0, dr = -1). We move one step north to
[1, 1], but since this cell has already been visited, we don't add it again to
ans`. - We've completed a full cycle (east > south > west > north), so we increment
k
by 2, makingk = 3
. - For the next eastward movement, we will move three steps, but after one step, we're already at the edge. The next position would be
[1, 3]
, within the grid, so it's added toans
-ans = [[1, 1], [1, 2], [2, 2], [2, 1], [1, 3]]
. - Continuing the cycle, we go south three steps, adding positions
[2, 3]
and[3, 3]
toans
. - Going west for three steps, we add
[3, 2]
and[3, 1]
toans
. - Finally, moving north, we add
[2, 1]
and the last remaining cell[1, 1]
is ignored as it's already visited. - All cells of the
3x3
grid have been added toans
, and the traversal is complete.
The final ans
, with the cells visited in the order of the spiral from the center, would be:
[[1, 1], [1, 2], [2, 2], [2, 1], [1, 3], [2, 3], [3, 3], [3, 2], [3, 1], [2, 1]]
This example demonstrated the simulated spiral movement through a grid following the solution approach outlined.
Solution Implementation
1class Solution:
2 def spiralMatrixIII(self, rows: int, cols: int, r_start: int, c_start: int) -> List[List[int]]:
3 # Initialize the answer list with the starting cell
4 result = [[r_start, c_start]]
5
6 # If there's only one cell, return it immediately
7 if rows * cols == 1:
8 return result
9
10 # 'k' represents the number of steps we take in a given direction before turning
11 # It starts at 1 and gets incremented after finishing an east and north pass
12 k = 1
13
14 # Continue generating the spiral pattern until we've filled the result with all cells
15 while True:
16 # Each iteration goes in the pattern: East, South, West, North
17 # 'dr' and 'dc' represent the change to rows and cols respectively
18 # 'dk' represents how many steps we take in each direction before turning
19 for dr, dc, dk in [[0, 1, k], [1, 0, k], [0, -1, k + 1], [-1, 0, k + 1]]:
20 # Repeat the movement 'dk' times for the current orientation
21 for _ in range(dk):
22 # Update the current position
23 r_start += dr
24 c_start += dc
25 # If we're still within the bounds of the matrix, add to result
26 if 0 <= r_start < rows and 0 <= c_start < cols:
27 result.append([r_start, c_start])
28 # If the result is now filled with all matrix cells, return it
29 if len(result) == rows * cols:
30 return result
31 # Increment 'k' for the next spiral arm to have the correct step count
32 k += 2
33
34# The return type should be List[List[int]], but this cannot be used directly in a code snippet
35# without importing List from typing. Be sure to include that in your actual implementation.
36```
37
38Make sure to include the import statement for `List` from the `typing` module at the beginning of your code if you're running this outside of LeetCode's environment where the import might be implicit:
39
40```python
41from typing import List
42
1class Solution {
2 public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
3 // Determine the total number of elements in the matrix
4 int totalElements = rows * cols;
5 // Initialize the answer array with a size equal to the number of elements
6 int[][] result = new int[totalElements][2];
7 // Starting position is the first element in the result array
8 result[0] = new int[] {rStart, cStart};
9
10 // If there's only one element, return the result immediately
11 if (totalElements == 1) {
12 return result;
13 }
14
15 int index = 1; // Start from the second element in the result array
16
17 // Loop indefinitely; the exit condition is when all matrix elements have been added to result
18 for (int k = 1; ; k += 2) {
19 // Directions and step increment: right, down, left, and up
20 int[][] directions = new int[][] {
21 {0, 1, k}, // Move right k steps
22 {1, 0, k}, // Move down k steps
23 {0, -1, k + 1}, // Move left (k+1) steps
24 {-1, 0, k + 1} // Move up (k+1) steps
25 };
26
27 // Iterate through each direction
28 for (int[] dir : directions) {
29 int rowStep = dir[0], colStep = dir[1], steps = dir[2];
30
31 // Move within the current direction for 'steps' times
32 while (steps-- > 0) {
33 // Move to the next cell in the current direction
34 rStart += rowStep;
35 cStart += colStep;
36
37 // Check if the current cell is within the boundaries of the matrix
38 if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
39 // Add the current cell to the result
40 result[index++] = new int[] {rStart, cStart};
41 // If we've added all matrix elements to the result, return the result
42 if (index == totalElements) {
43 return result;
44 }
45 }
46 }
47 }
48 }
49 }
50}
51
1class Solution {
2public:
3 vector<vector<int>> spiralMatrixIII(int rows, int cols, int startRow, int startCol) {
4 int totalCells = rows * cols; // Total number of cells in the matrix
5 vector<vector<int>> result; // This will store the path of the spiral
6 result.push_back({startRow, startCol}); // Starting position
7
8 // If there is only one cell in the matrix, return the result now
9 if (totalCells == 1) {
10 return result;
11 }
12
13 // Spiral can be formed by increasing the steps in the east and north directions,
14 // and then increasing by an additional step when moving west and south.
15 for (int stepIncrease = 1; ; stepIncrease += 2) {
16 // Directions are East, South, West, North.
17 // The third value in each vector holds the number of steps to take in that direction.
18 vector<vector<int>> directions = {{0, 1, stepIncrease}, // Move right (East)
19 {1, 0, stepIncrease}, // Move down (South)
20 {0, -1, stepIncrease + 1}, // Move left (West)
21 {-1, 0, stepIncrease + 1}}; // Move up (North)
22
23 // Go through each of the four directions
24 for (auto& dir : directions) {
25 // 'dir' is vector<int> that contains the row increment, column increment, and number of steps.
26 int rowIncrement = dir[0];
27 int colIncrement = dir[1];
28 int steps = dir[2];
29
30 // Move the number of steps in the current direction
31 while (steps-- > 0) {
32 // Update the starting position
33 startRow += rowIncrement;
34 startCol += colIncrement;
35
36 // Check if the new position is within the matrix bounds
37 if (startRow >= 0 && startRow < rows && startCol >= 0 && startCol < cols) {
38 result.push_back({startRow, startCol}); // Add to result
39 // If we've added all cells, return the result
40 if (result.size() == totalCells) {
41 return result;
42 }
43 }
44 }
45 }
46 }
47 }
48};
49
1function spiralMatrixIII(rows: number, cols: number, startRow: number, startCol: number): number[][] {
2 // Total number of cells in the matrix
3 const totalCells: number = rows * cols;
4 // This will store the path of the spiral
5 const path: number[][] = [[startRow, startCol]];
6
7 // If there is only one cell in the matrix, return the path now
8 if (totalCells === 1) {
9 return path;
10 }
11
12 // Loop wherein each iteration potentially adds two sides of the spiral.
13 for (let stepIncrease = 1; ; stepIncrease += 2) {
14 // Directions are East, South, West, North.
15 // Each tuple contains the row and column increments, and the number of steps to take.
16 const directions: [number, number, number][] = [
17 [0, 1, stepIncrease], // Move right (East)
18 [1, 0, stepIncrease], // Move down (South)
19 [0, -1, stepIncrease + 1], // Move left (West)
20 [-1, 0, stepIncrease + 1] // Move up (North)
21 ];
22
23 for (const [rowIncrement, colIncrement, steps] of directions) {
24 // Initialize a variable for the number of steps to be taken in the current direction
25 let stepsRemaining = steps;
26
27 // Move the number of steps in the current direction
28 while (stepsRemaining-- > 0) {
29 // Update the starting position
30 startRow += rowIncrement;
31 startCol += colIncrement;
32
33 // Check if the new position is within the matrix bounds
34 if (startRow >= 0 && startRow < rows && startCol >= 0 && startCol < cols) {
35 // Add the new position to the path
36 path.push([startRow, startCol]);
37 // If we've added all cells, return the path
38 if (path.length === totalCells) {
39 return path;
40 }
41 }
42 }
43 }
44 }
45}
46
47// Example use:
48// const result = spiralMatrixIII(5, 6, 1, 4);
49// console.log(result); // This would log the spiral matrix to the console.
50
Time and Space Complexity
The given Python code generates all the coordinates in a matrix in a spiral order starting from a given cell (rStart, cStart)
. Considering each coordinate in a rows x cols
grid needs to be visited exactly once, let's analyze both the time complexity and space complexity of the code.
Time Complexity:
The time complexity of this function can be analyzed by understanding the number of steps taken to complete the spiral. The number of steps increases as the spiral grows. The spiral growth is implemented by incrementing the step size k
after every two directions (right-up
and left-down
). Initially, k
starts at 1, and after each full cycle (right -> down -> left -> up), k
is incremented by 2. This means that for a matrix that requires n
cycles to fill, the total number of steps S
would be the sum of an arithmetic series:
S = 1 + 2 + 3 + 4 + ... + (2n - 1) + 2n
This sum is equal to n(2n + 1)
, which is O(n^2)
.
Since n
is proportional to the larger dimension of the matrix (rows
or cols
), and the number of iterations required to cover all cells of the matrix will be bound by the total number of cells, we can conclude that the time complexity is O(max(rows, cols)^2)
.
Space Complexity:
The space complexity of the algorithm is determined by the amount of space needed to store the output. Since the output ans
is a list of all coordinates in the matrix, it needs to store exactly rows * cols
elements.
Thus, the space complexity is O(rows * cols)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!