The “Spiral Matrix” problem is a fascinating algorithmic challenge that tests your ability to traverse a matrix in a specific order. This problem is often asked in technical interviews and demonstrates your understanding of multi-dimensional arrays and traversal techniques.
Problem Statement
Given a matrix of (m \times n) elements (where (m) is the number of rows and (n) is the number of columns), return all elements of the matrix in spiral order.
Example:
- Input:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
- Output:
[1, 2, 3, 6, 9, 8, 7, 4, 5]
Java Solution
import java.util.ArrayList;
import java.util.List;
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix.length == 0) return result;
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// Traverse from left to right
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++;
// Traverse from top to bottom
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
// Check if we are still within the bounds
if (top <= bottom) {
// Traverse from right to left
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--;
}
if (left <= right) {
// Traverse from bottom to top
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++;
}
}
return result;
}
public static void main(String[] args) {
SpiralMatrix solution = new SpiralMatrix();
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
List<Integer> result = solution.spiralOrder(matrix);
System.out.println("Spiral order: " + result); // Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
}
}
Code Breakdown
- Class Declaration
public class SpiralMatrix {
This line declares a public class named SpiralMatrix.
- spiralOrder Method
public List<Integer> spiralOrder(int[][] matrix) {
This method takes a 2D array (matrix) and returns a list of integers representing the spiral order.
- Result Initialization
List<Integer> result = new ArrayList<>();
if (matrix.length == 0) return result;
An ArrayList is initialized to store the result, and a check is performed to return an empty list if the matrix is empty.
- Define Boundaries
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
Four variables are initialized to define the current boundaries of the matrix: top, bottom, left, and right.
- Traversal Loop
while (top <= bottom && left <= right) {
A loop continues until the boundaries collapse.
- Traverse Left to Right
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++;
This loop adds elements from the top row and then increments the top boundary.
- Traverse Top to Bottom
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
This loop adds elements from the rightmost column and then decrements the right boundary.
- Check and Traverse Right to Left
if (top <= bottom) {
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--;
}
This conditional checks if we are still within the bounds before traversing the bottom row.
- Check and Traverse Bottom to Top
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++;
}
This conditional checks if we are still within the bounds before traversing the leftmost column.
Time and Space Complexity
- Time Complexity: (O(m \times n))
Each element in the matrix is processed exactly once. - Space Complexity: (O(1)) (excluding the output)
The additional space used is constant since we only maintain a few variables for the boundaries.
Example Output
For the given input:
Input:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Output: Spiral order: [1, 2, 3, 6, 9, 8, 7, 4, 5]
This output confirms that the elements are returned in spiral order.
Conclusion
The “Spiral Matrix” problem is an excellent exercise in matrix traversal techniques. Mastering this problem can enhance your problem-solving skills and prepare you for more complex algorithmic challenges in coding interviews.
For any questions or modifications, feel free to reach out to Divi Tech HR Solutions at info@divisolutions.in.
If you found this blog helpful, please leave a comment and like the post!
0 Comments