My Super Simple Solution. Can be used for both Spiral Matrix I and II


  • 66
    Q

    This is my solution for Spiral Matrix I, https://oj.leetcode.com/discuss/12228/super-simple-and-easy-to-understand-solution. If you can understand that, this one is a no brainer :)

    Guess what? I just made several lines of change (with comment "//change") from that and I have the following AC code:

    public class Solution {
        public int[][] generateMatrix(int n) {
            // Declaration
            int[][] matrix = new int[n][n];
            
            // Edge Case
            if (n == 0) {
                return matrix;
            }
            
            // Normal Case
            int rowStart = 0;
            int rowEnd = n-1;
            int colStart = 0;
            int colEnd = n-1;
            int num = 1; //change
            
            while (rowStart <= rowEnd && colStart <= colEnd) {
                for (int i = colStart; i <= colEnd; i ++) {
                    matrix[rowStart][i] = num ++; //change
                }
                rowStart ++;
                
                for (int i = rowStart; i <= rowEnd; i ++) {
                    matrix[i][colEnd] = num ++; //change
                }
                colEnd --;
                
                for (int i = colEnd; i >= colStart; i --) {
                    if (rowStart <= rowEnd)
                        matrix[rowEnd][i] = num ++; //change
                }
                rowEnd --;
                
                for (int i = rowEnd; i >= rowStart; i --) {
                    if (colStart <= colEnd)
                        matrix[i][colStart] = num ++; //change
                }
                colStart ++;
            }
            
            return matrix;
        }
    }
    

    Obviously, you could merge colStart and colEnd into rowStart and rowEnd because it is a square matrix. But this is easily extensible to matrices that are m*n.

    Hope this helps :)


  • 1
    S

    Why do you put this test inside each loop ?
    if (rowStart <= rowEnd)


  • 21
    L
      public int[][] generateMatrix(int n) {
            int[][] res = new int[n][n];
        
            int cur = 1;
            int rowBegin = 0;
            int rowEnd = n - 1;
            int colBegin = 0;
            int colEnd = n - 1;
            
            while(cur <= n * n) {
                    int i = rowBegin;
                    int j = colBegin;
                    //left to right
                    for(j = colBegin ; j <= colEnd; j++){
                        res[rowBegin][j] = cur++;
                    }
                    rowBegin++;
                    //top to bot
                    for(i = rowBegin ; i <= rowEnd; i++){
                        res[i][colEnd] = cur++;
                    }
                    colEnd--;
                    //right to left
                    for(j = colEnd ; j >= colBegin; j--){
                        res[rowEnd][j] = cur++;
                    }
                    rowEnd--;
                    //bot to top
                    for(i = rowEnd; i >= rowBegin; i--){
                        res[i][colBegin] = cur++;
                    }
                    colBegin++;
            }
            return res;
        }
    

    Actually you don't need "if condition", because it's n*n matrix.


  • 0
    Z
    This post is deleted!

  • 0
    Z

    Basically, you are walking through spiral. You use four parameters ( (row,col)*(start,end)) instead of one. That is really clean.


  • 0
    D

    Love your solution. Perfect


  • 1
    X

    For the condition of the outer while loop, '''while (num <= m * n)''' also works fine. Just FYI:)


  • 1
    C

    @qwl5004
    It would be better to put if condition outside of the for loops in both the places to prevent checking it multiple times.


  • 2

    I love solutions like yours. Very intuitive and straightforward. No magic or brainteaser but very clean. Here is a little shorter version derived from yours for anyone's reference. Thanks for sharing!

        public int[][] generateMatrix(int n) {
            int[][] matrix = new int[n][n];
            if (n <= 0) return matrix;
            
            int num = 1, rowbegin = 0, rowend = n - 1, colbegin = 0, colend = n - 1;
            while (rowbegin <= rowend && colbegin <= colend) {
                for (int i = colbegin; i <= colend; i++) matrix[rowbegin][i] = num++;
                rowbegin++;
                
                for (int i = rowbegin; i <= rowend; i++) matrix[i][colend] = num++;
                colend--;
                
                for (int i = colend; i >= colbegin; i--) matrix[rowend][i] = num++;
                rowend--;
                
                for (int i = rowend; i >= rowbegin; i--) matrix[i][colbegin] = num++;
                colbegin++;
            }
            return matrix;
        }
    

  • 0
    L

    @lovesly said in My Super Simple Solution. Can be used for both Spiral Matrix I and II:

    colBegin

    this solution shows "Time Limit Exceeded"


  • 0
    M

    @qwl5004 This must be upvoted!


  • 1
    Y

    @sebastien2
    As for Spiral Matrix II, it is not necessary to include this test. But it is indeed a must in Spiral Matrix I. The main difference lies in the fact that matrix is n * n in Spiral Matrix II, but m * n in Spiral Matrix I.

    For example, m = 3, n = 1, matrix = [[1],[2],[3]]
    If there is not test if (colStart <= colEnd), then matrix[1][0] will print out again.

    At last, one minor improvement of your code, @qwl5004
    Instead of

                for (int i = colEnd; i >= colStart; i --) {
                    if (rowStart <= rowEnd)
                        matrix[rowEnd][i] = num ++; //  change
                }
                rowEnd --;
    

    What about this?

                if (rowStart <= rowEnd) {
                   for (int i = colEnd; i >= colStart; i --) {
                       matrix[rowEnd][i] = num ++; // manipulation of matrix element
                   }
                }
                rowEnd --;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.