Solving Leetcode 54. Spiral Matrix. Spirally traversing a matrix

Problem statement

Given an m x n matrix, return all elements of the matrix in spiral order.

This problem seems little tricky but it is very easy to understand once you realize how spiral order works. And this question often comes up on interviews so here’s what I did! In a regular matrix, like the one below where each column represents an element and each row its corresponding multiple of three (3), we can follow four different directions: going right will take us down from any given pointy-ness; moving left brings us closer toward zero while going upward boosts our score by one unit every time – that means

Example I/O

Let’s say we have an input array [[1,2,3],[4,5,6],[7,8,9]]

The expected output is a list of integers in spiral order, that is [1,2,3,6,9,8,7,4,5].

Optimized solution

Let’s remember, we’re dealing with 2D arrays. The most optimized solution to Leetcode 54. Spiral Matrix is to use a single loop that iterates over the matrix and prints out the elements in a clockwise spiral order, as described above. This solution is much more efficient than using multiple nested loops.

Here is the example in JavaScript:

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
        if (!matrix.length) return [];
    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let right = matrix[0].length - 1;
    const res = [];
    while (true) {
        // go right
        for (let i = left; i <= right; i++) {
            res.push(matrix[top][i]);
        }
        top++;
        if (top > bottom) break;
        // go down
        for (let i = top; i <= bottom; i++) {
            res.push(matrix[i][right]);
        }
        right--;
        if (right < left) break;
        // go left
        for (let i = right; i >= left; i--) {
            res.push(matrix[bottom][i]);
        }
        bottom--;
        if (bottom < top) break;
        // go up
        for (let i = bottom; i >= top; i--) {
            res.push(matrix[i][left]);
        }
        left++;
        if (left > right) break;
    }
    return res;
};

1. Initialize the result array, and pointers for the top, bottom, left and right edges of the matrix.
2. While the pointers haven’t crossed over each other:
   • Traverse the top edge of the matrix from left to right.
   • Traverse the right edge of the matrix from top to bottom.
   • Traverse the bottom edge of the matrix from right to left, if top <= bottom.
   • Traverse the left edge of the matrix from bottom to top, if left <= right.
3. Return the result array

Code in Java:

List<Integer> result = new ArrayList<>();
 if(matrix.length == 0) return result;
 int rowBegin = 0;
 int rowEnd = matrix.length - 1;
 int colBegin = 0;
 int colEnd = matrix[0].length - 1;
 while(rowBegin <= rowEnd && colBegin <= colEnd){
     // Traverse Right
     for(int i = colBegin; i <= colEnd; i++){
         result.add(matrix[rowBegin][i]);
     }
     rowBegin++;
     // Traverse Down
     for(int i = rowBegin; i <= rowEnd; i++){
         result.add(matrix[i][colEnd]);
     }
     colEnd--;
     if(rowBegin <= rowEnd){
         // Traverse Left
         for(int i = colEnd; i >= colBegin; i--){
             result.add(matrix[rowEnd][i]);
         }
     }
     rowEnd--;
     if(colBegin <= colEnd){
         // Traver Up
         for(int i = rowEnd; i >= rowBegin; i--){
             result.add(matrix[i][colBegin]);
         }
     }
     colBegin++;
 }
 return result;

This is an example of the 2-pointer method to traverse the matrix in a spiral order. This approach uses four pointers: top, bottom, left, and right to keep track of the current boundaries of the spiral.

The approach starts by initializing these pointers to the edges of the matrix. The outer while loop keeps track of the overall spiral traversal, and it continues to execute while the top pointer is less than or equal to the bottom pointer and the left pointer is less than or equal to the right pointer.

The first for loop iterates through the top row of the matrix from the left pointer to the right pointer and pushes the elements to the result array. Then, the top pointer is incremented, next inner loop iterates through the rightmost column of the matrix from the top pointer to the bottom pointer and pushes the elements to the result array. The right pointer is decremented.

Then there is an if block to check if top is less than bottom, if it is true it iterates through the bottom row of the matrix from the right pointer to the left pointer and pushes the elements to the result array and decrements the bottom pointer.

Finally, there is another if block to check if left is less than right, if it is true it iterates through the leftmost column of the matrix from the bottom pointer to the top pointer and pushes the elements to the result array and increments the left pointer.

This algorithm visits each element in the matrix exactly once and return the elements in the spiral order.

Time and space complexity

The approach which we used above was the use of a 2-pointer method which goes through the matrix once, visiting each element exactly once. This method takes O(n) time complexity where n is the total number of elements in the matrix. The space complexity is O(1) because we only use a small number of variables to keep track of the current position and direction.

Conclusion:

Solving Leetcode 54, also known as Spiral Matrix, requires traversing a given matrix in a spiral order. There are multiple ways to approach this problem, each with its own advantages and disadvantages. One approach is to use a 2-pointer method (Shown above) to traverse the matrix in a spiral order. Another approach could have been to use a recursion technique. It’s important to note that this is just one of the ways of solving this problem and there may be other solutions as well. In any case, understanding the problem, thinking through the solution, and practicing different approaches are key to solving Leetcode problems such as this one.