Spiral Matrix – Revisited

Good morning. Hope your day is starting on the right note. Yesterday was a long and busy day. Something at work stated on Saturday extended at least through yesterday. I spent a lot of time on the phone, browsing code and looking at log files. It seems we know what is causing the problem. Currently I am in the midst of formulating approaches to address the issue. Hopefully all will be solved by tomorrow.

On a separate note, yesterday I had the opportunity to meet on-line a software engineer that works at a large software company. You never know what the future has reserved for you.

While I was browsing the LeetCode site, I found a problem that sounded somewhat familiar:  Spiral Matrix. That said; I had not solved the problem at LeetCode. I also looked for it in HackerRank without luck. I did find the post Spiral Matrix in my blog. Apparently I found the problem somewhere on the web and solved it in C/C++. The WordPress pluging I used at the time was / is having problems, so it is hard to follow it on-line. In addition I did not save the C/C++ code from February 17, 2017 in GitHub. So this post will cover the same problem using the Java programming language on a Windows 10 computer using the VSCode IDE.

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

Constraints:

o m == matrix.length
o n == matrix[i].length
o 1 <= m, n <= 10
o -100 <= matrix[i][j] <= 100
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
    }
}

The description of the problem and associated examples provided by LeetCode, make it easy to understand what is required. All we have to do is come up with the Java code to get it done as elegant as possible.

Because I have worked on a solution in the past in C/C++, we will generate a few implementations. Software development is both a science and an art. In addition of an elegant solution we should strive to come up with some logic and comments to make it easier to understand and perhaps optimize of enhance in the future.

Since I will develop the code on my machine and not directly on the LeetCode site using the provided IDE, we will have to develop a test scaffolding which should handle the data input, transformation to what the function / method at hand requires, invoke the function / method and return the results. Such code IS NOT PART OF THE SOLUTION.

If you copy and paste the code for the different approaches we will cover, they all were accepted by LeetCode. Hopefully you will come with a more elegant and efficient approach.

[[1,2,3],[4,5,6],[7,8,9]]
main <<< str ==>[1,2,3],[4,5,6],[7,8,9]<==
main <<< strArr: [1,2,3, 4,5,6, 7,8,9]
main <<< m: 3 n: 3
main <<< matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
main <<< spiralOrder0: [1, 2, 3, 6, 9, 8, 7, 4, 5]
main <<< spiralOrder1: [1, 2, 3, 6, 9, 8, 7, 4, 5]
main <<< spiralOrder2: [1, 2, 3, 6, 9, 8, 7, 4, 5]


[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
main <<< str ==>[1,2,3,4],[5,6,7,8],[9,10,11,12]<==
main <<< strArr: [1,2,3,4, 5,6,7,8, 9,10,11,12]
main <<< m: 3 n: 4
main <<< matrix:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
main <<< spiralOrder0: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
main <<< spiralOrder1: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
main <<< spiralOrder2: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]


[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
main <<< str ==>[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]<==
main <<< strArr: [1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,16]
main <<< m: 4 n: 4
main <<< matrix:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 16]
main <<< spiralOrder0: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
main <<< spiralOrder1: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
main <<< spiralOrder2: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]


[[1]]
main <<< str ==>[1]<==
main <<< strArr: [1]
main <<< m: 1 n: 1
main <<< matrix:
[1]
main <<< spiralOrder0: [1]
main <<< spiralOrder1: [1]
main <<< spiralOrder2: [1]


[[1],[2]]
main <<< str ==>[1],[2]<==
main <<< strArr: [1, 2]
main <<< m: 2 n: 1
main <<< matrix:
[1]
[2]
main <<< spiralOrder0: [1, 2]
main <<< spiralOrder1: [1, 2]
main <<< spiralOrder2: [1, 2]


[[1,2]]
main <<< str ==>[1,2]<==
main <<< strArr: [1,2]
main <<< m: 1 n: 2
main <<< matrix:
[1, 2]
main <<< spiralOrder0: [1, 2]
main <<< spiralOrder1: [1, 2]
main <<< spiralOrder2: [1, 2]

We have all the test cases provided by LeetCode in addition of some I used to test some end conditions.

It seems that we are provided a line with an array of arrays on integer that represent the matrix for each test case. Our test software appears to read the input line and extract a string of arrays with the associated values. Both string and array of strings are displayed for us to quickly verify this are moving along fine.

The dimensions of the matrix are probably computed and displayed. The integer matrix appears to be created and populated. So far all is well. We just need to implement the required function / method and display the results. It seems we have three different attempts and they all return the same values. That is important, but they all were submitted to LeetCode and they were all accepted as we will see shortly. Please note that the three approaches are similar and they are just refinements of the first one.

   /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read input line ****
        String str = br.readLine().trim();

        // **** close buffered reader ****
        br.close();

        // **** remove leading and trailing brackets ****
        str = str.substring(1, str.length() - 1);

        // ???? ????
        System.out.println("main <<< str ==>" + str + "<==");

        // **** split string into rows ****
        String[] strArr = str.split("\\],\\[");

        // **** remove bracker from first and last strings ****
        strArr[0] = strArr[0].substring(1);
        strArr[strArr.length - 1] = strArr[strArr.length - 1].substring(0, strArr[strArr.length - 1].length() - 1);

        // ???? display string array ????
        System.out.println("main <<< strArr: " + Arrays.toString(strArr));

        // **** create and populate matrix ****
        int[][] matrix = new int[strArr.length][];
        for (int i = 0; i < strArr.length; i++) {

            // **** ****
            String[] sa = strArr[i].split(",");

            // **** create matrix array for current row ****
            matrix[i] = Arrays.stream(sa).mapToInt(Integer::parseInt).toArray();
        }

        // ???? determine the matrix dimensions ????
        int m = matrix.length;
        int n = matrix[0].length;
        System.out.println("main <<< m: " + m + " n: " + n);
        
        // ???? display the matrix ????
        System.out.println("main <<< matrix: ");
        for (int[] arr : matrix)
            System.out.println(Arrays.toString(arr));

        // **** perform spiral traversal ****
        List<Integer> lst = spiralOrder0(matrix);

        // **** display results ****
        if (lst != null)
            System.out.println("main <<< spiralOrder0: " + lst.toString());
        else
            System.out.println("main <<< spiralOrder0: null");

        // **** perform spiral traversal ****
        lst = spiralOrder1(matrix);

        // **** display results ****
        if (lst != null)
            System.out.println("main <<< spiralOrder1: " + lst.toString());
        else
            System.out.println("main <<< spiralOrder1: null");

        // **** perform spiral traversal ****
        lst = spiralOrder2(matrix);

        // **** display results ****
        if (lst != null)
            System.out.println("main <<< spiralOrder2: " + lst.toString());
        else
            System.out.println("main <<< spiralOrder2: null");
    }

The test scaffolding uses a buffered reader to read the input line. On the first few test cases, the input line was just copied from the LeetCode site. We then removed the leading and trailing brackets. The resulting string is displayed.

We then split the string into string arrays and store the strings in an array. We have to remove the leading bracket from the first array and the closing bracket from the last array. We then display the string array.

We are ready to create and populate a two dimensional array which will be used as an argument for the function we need to implement.

We then determine and display the matrix dimensions. They are not required as arguments but I decided to do so. We then display the contents of the matrix.

At this point we are ready to call the spiralOrder() function and collect the results in a list. We then display the contents of the list to verify our answer. Two more attempts follow.

    /**
     * Given an m x n matrix, return all elements of the matrix in spiral order.
     * O(n) where n == # elements in matrix.
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 37 MB, less than 78.15% of Java online submissions.
     */
    static List<Integer> spiralOrder0(int[][] matrix) {

        // **** sanity check(s)****
        if (matrix == null || matrix.length == 0) 
            return null;

        // **** determine matrix dimensions ****
        int m = matrix.length;
        int n = matrix[0].length;

        // **** initialization ****
        List<Integer> lst   = new LinkedList<Integer>();
        boolean[][] visited = new boolean[m][n];
        int r               = 0;
        int c               = 0;

        // **** traverse the matrix (right, down, left, and up) ****
        for (int k = 0; k < m * n; ) {

            // **** go right ****
            for ( ; c < n && visited[r] == false; c++) {
                lst.add(matrix[r]);
                visited[r] = true;
                k++;
            }

            // **** go down ****
            for (r++, c--; r < m && visited[r] == false; r++) {
                lst.add(matrix[r]);
                visited[r] = true;
                k++;
            }

            // **** go left ****
            for (r--, c--; c >= 0 && visited[r] == false; c--) {
                lst.add(matrix[r]);
                visited[r] = true;
                k++;
            }

            // **** go up ****
            for (r--, c++; r >= 0 && visited[r] == false; r--) {
                lst.add(matrix[r]);
                visited[r] = true;
                k++; 
            }

            // **** adjust r and c to start next cycle ****
            r++;
            c++;
        }

        // **** return list of values ****
        return lst;
    }

This is the first attempt. We perform some sanity checks and determine the matrix dimensions. We will need them as we traverse the matrix in a spiral fashion.

We initialize a set of variables. The results will be appended to the linked list in which we will return the answer. I was not sure if we would need an array to flag the cells we visited. When I started I had a few approaches in mind. If time is available I like to pursue an idea to completion. That said, as we will see here, with some minor changes we can reduce the space requirements by not using the visited array.

We will traverse the matrix in the proper order to perform a spiral pattern while traversing the matrix. We will have to hit each cell in the matrix once so our linked list will end with m * n elements.

We start by moving from left to right. As we progress we add the value in the current cell to the linked list, we flag we have visited the cell and increment the count of cells visited.

The process repeats with loops to go down, from right to left and finally up. When done we update the row and column variables to start the next pass. Note we started on matrix cell [0, 0] and if there is a second pass we need to start at the cell [1, 1]. This process repeats as long as there are cells to process. For this we use the k variable.

    /**
     * Given an m x n matrix, return all elements of the matrix in spiral order.
     * O(n) where n == # elements in matrix.
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 36.8 MB, less than 95.05% of Java online submissions.
     */
    static List<Integer> spiralOrder1(int[][] matrix) {

        // **** sanity check(s)****
        if (matrix == null || matrix.length == 0) 
            return null;

        // **** initilaization ****
        int top     = 0;
        int bottom  = matrix.length - 1;
        int left    = 0;
        int right   = matrix[0].length - 1;

        // **** initialization ****
        List<Integer> lst   = new LinkedList<Integer>();
        int size            = matrix.length * matrix[0].length;

        // ***** loop until all cells have been visited in spiral order ****
        while (size > 0) {

            // **** go right ****
            for (int c = left; c <= right; c++) {
                lst.add(matrix[top]);
                size--;
            }

            // **** check if done ****
            if (size == 0)
                return lst;

            // **** go down ****
            for (int r = top + 1; r <= bottom; r++) {
                lst.add(matrix[r][right]);
                size--;
            }

            // **** check if done ****
            if (size == 0)
                return lst;

            // **** go left ****
            for (int c = right - 1; c >= left; c--) {
                lst.add(matrix[bottom]);
                size--;
            }

            // **** check if done ****
            if (size == 0)
                return lst;

            // **** go up ****
            for (int r = bottom - 1; r > top; r--) {
                lst.add(matrix[r][left]);
                size--;
            }

            // **** check if done ****
            if (size == 0)
                return lst;

            // **** update limits for next next cycle ****
            top++;
            bottom--;
            left++;
            right--;
        }

        // **** return list of values ****
        return lst;    
    }

Same concept as before but we decided to eliminate the use of the visited matrix. We can achieve the same results without it by tracking the limits of each spiral loop. We do so with the right, bottom, left and top variables. We decided to keep track of the elements we need to process instead of the elements in the linked list. The results are the same.=

Note that we traverse in the same directions and use the four limits we generated in the initialization. In addition we check if we are done after traversing each direction. If so we just return the list. By altering the shape our algorithm may end after the different loops.

After completing a cycle, we need to update the four limits. We do so and proceed into the next loop.

   /**
     * Given an m x n matrix, return all elements of the matrix in spiral order.
     * O(n) where n == # elements in matrix.
     *
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 37.3 MB, less than 44.52% of Java online submission.
     */
    static List<Integer> spiralOrder2(int[][] matrix) {

        // **** sanity check(s)****
        if (matrix == null || matrix.length == 0) 
            return null;

        // **** initilaization ****
        int top     = 0;
        int bottom  = matrix.length - 1;
        int left    = 0;
        int right   = matrix[0].length - 1;

        // **** initialization ****
        List<Integer> lst   = new LinkedList<Integer>();
        int size            = matrix.length * matrix[0].length;

        // ***** loop until all cells have been visited in spiral order ****
        while (lst.size() < size) {

            // **** go right ****
            for (int c = left; c <= right && lst.size() < size; c++)
                lst.add(matrix[top]);

            // **** go down ****
            for (int r = top + 1; r <= bottom && lst.size() < size; r++)
                lst.add(matrix[r][right]);

            // **** go left ****
            for (int c = right - 1; c >= left && lst.size() < size; c--)
                lst.add(matrix[bottom]);

            // **** go up ****
            for (int r = bottom - 1; r > top && lst.size() < size; r--)
                lst.add(matrix[r][left]);

            // **** update limits for next next cycle ****
            if (lst.size() < size) {
                top++;
                bottom--;
                left++;
                right--;
            }
        }

        // **** return list of values ****
        return lst;    
    }

This pass is pure cosmetics. It seems we condensed the code.

Note that in all three attempts the execution time was about the same. What changes is the readability and by default the time it would take if the code needs to be updated / maintained in the future.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 5,175 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.