Layered Approach (Clockwise)


  • 0
    N

    Approach #1 Layered (Clockwise)

    Intuition

    Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

    Algorithm

    We define 4 variables to move in the clockwise path. 2 corresponds to Row & rest 2 corresponds to Column. Both have starting index as 0 and end index as n-1.
    Now we traverse first on Top row (in Left-Right manner). After computation increase the starting row index (let's say initially a = 0 ==> a += 1).
    Then we move in right most column (top-bottom approach). Let's say c & d are starting & ending indexes for columns respectively. After this operation, d -= 1.
    Similarly in 3rd step we move from right-left manner in bottom row. let's say ending index of rows is b i.e b -= 1 after this operation.
    In last step, c++ after traversing from bottom to top approach in first column.

    Here first and last (both column and row) number will change after each step stated above.

    C++

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> result;
            result.resize(n);
            
            for(int i = 1;i <= n;i++) {
               result[i-1].resize(n); 
            }
            int a = 0;
            int b = n-1;
            int c = 0;
            int d = n-1;
            int cnt = 1;
            
            while(a <= b || c <= d) {
                
                if(a <= b) {
                    for(int i = c;i <= d;i++) {
                        result[a][i] = cnt++;
                    }
                    a++;
                }
                if(c <= d) {
                    for(int i = a;i <= b;i++) {
                        result[i][d] = cnt++;
                    }
                    d--;
                }
                if(c <= d) {
                    for(int i = d;i >= c;i--) {
                        result[b][i] = cnt++;
                    }
                    b--;
                }
                if(a <= b) {
                    for(int i = b;i >= a;i--) {
                        result[i][c] = cnt++;
                    }
                    c++;
                }
                
            }
            return result;
        }
    };
    

    Complexity Analysis

    • Time complexity : O(n^2), Where N is the given no. of rows/columns in a Square Matrix.
    • Space complexity : O(n^2), We need 2D vector/Array to store the values.

Log in to reply
 

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