This is our solution and implementation to problem #54: Spiral Matrix on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Spiral Matrix on LeetCode.
Problem Analysis
Given an m x n matrix, or 2D list, we need to return a 1D list containing all items in the matrix. The output list should contain the items in order as if we traversed the matrix in a spiral pattern, starting at the top left, then moving to the right, down, left, and up, ignoring items we've already visited. We will need to determine an efficient way of making this traversal without redundant iteration or storage.
Implementation Strategy
We will define our iteration in terms of steps and substeps. A substep is a traversal from start to finish in a single direction. A step runs 4 substeps, one for each direction in the order of right, down, left, and up. During our stepping process, we'll implicity keep track of the cells we've already visited by maintaining values for xLeft, xRight, yTop, and yBottom. After each substep, we'll increment or decrement the appropriate variable. We'll know when we're done iterating when the number of elements in the output list is equal to the number of elements in the input matrix.
To summarize the algorithm
- Initialize the solutionList.
- Initialize variables to keep track of boundaries:
- xLeft: set to 0, indicating the leftmost position.
- xRight: set to matrix[0].length - 1, indicating the rightmost position.
- yTop: set to 0, indicating the topmost position.
- yBottom: set to matrix.length - 1, indicating the bottommost position.
- While true (we'll have break conditions within this loop):
- Move from xLeft to xRight and add each item matrix[x][yTop] to solutionList. This is a move from the top left to the top right.
- Increment yTop, indicating that we've processed the first row.
- Exit if we've added all items in the matrix, proceed otherwise.
- Move from yTop to yBottom and add each item matrix[xRight][y] to solutionList. This is a move from the top right to the bottom right.
- Decrement xRight, indicating that we've processed the right column.
- Exit if we've added all items in the matrix, proceed otherwise.
- Repeat those steps for the bottom row and leftmost columns.
- Return solutionList.
Space and Time Complexity
The space complexity, including the output list itself, is O(n), as the output list will contain every element, and we will only have a constant number of other variables not dependend upon the input size. The time complexity is O(n), as we will be touching each element in the matrix exactly once.
Additional Resources
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.