Algorithm(10) Simulation

Several questions about the simulation, the typical one is to follow specific rules to go through each element of the matrix.

There are several imporant concepts, lets using 885 as an example.

• boundry position, the boundry position can change dynamically during the simulation for each iteration, it labels the min and max value the i and j can be. One simple protocol to change the boundy is that for example, when we use the right boundry, such as move j till the maxC, then after this operation, we then shink the right bounudry. Then we can do similar operations for other boundries. The only difference is that we put the updating of minR bounudy at the beginning of the while iteration, since we input the first element out of the while loop, we execute it one more time.

• Wall, the wall position is the outter layer of the grid, be careful about it, when the grid is fixed, the wall is fixed, the boundy can be overlap with the wall. In this case, we might need some special operations, such as not inserting the element into the path.

• Do not mix the wall and boundry, they are two different concepts, the wall is fixed and the boundry can change dynamically according to the requirments from of the question.

• 2d vector for iterating the 4 direaction. In order to make the code simple, the good practice is to maintain a 2d vector to control how the x and y move, this is an exmaple, we just need to go through these 2d vector gradually to control the movement of the current element.

• Double check the position of (0,0). In most of the case, we set the upper left position as 0,0 which match with our habit to write a matrix in math, we set the first row as 0, and if we have second row, it is 1. Be careful when we output associated reuslts for visualization, in that case, or in the commonly used coordinates system, the left bottom corner is usualy set as 0,0. Which is a common practice when we set coordinates. So be careful about it when we want to visualize sth. In that case, the first row in the output data might be actually the last row in the original data!!! Be careful about this difference.

Some of these questions can also be considered from perspective of the two pointers. Since x and y are ensentially two index of iterating. Instead of going through every combination of x and y, we just select proper combination of x and y and choose suitable elements.

• Another tip is that be careful to decide when to break the loop, we need to check weather go out of the loop after move right or move down. If we do not move down, there is logic error when we move from right to left, this might cause that we insert a repeated element.

int dirs[][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; 

• Another small but tricky techniques is to consider the sequence of move and record and how to use loop to divide it. We might need to consider first or last element separately. Considering this loop while (i<maxC) {record i; i++} the second loop is while (i<maxC) {i++; record i}. The difference is that for first element, in the while loop, the case of i==maxC will not be recorded, we might need to consider last element separately. For the second case, the i==maxC will be recorded, we might need to process first element separately before the while loop. Or we need to update the loop condition for the second case, to let the i<=maxC

54 Spiral Matrix

There is a workable solution, but not good, a little bit messy, the special case contains one row and one column.

The core issue is that for some cases, we did not execute all 4 move before exiting

This is the code that consider the move in firstly and then insert, we need to consider some cases before the for loop

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> path;
        int rows = matrix.size();
        if (rows==0){
            return path;
        }
        int cols = matrix[0].size();
        //no wal
        //list bounds
        int minC=0;
        int maxC=cols-1;
        int minR=0;
        int maxR=rows-1;
        
        //start position
        int i=0,j=0;
        path.push_back(matrix[i][j]);

        //go through matrix
        //do not contain last one
        while(path.size()<(rows*cols)){
            //printf("---Iteration start\n");
            
            //minR change at the beginning
            //execute it one more time at fitst iterstion
            //printf("minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);
            if(maxR>minR) {minR=minR+1;}
            //printf("AC minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);
            //left to right
            //we might miss to push
            //the element at the boundry in this case
            //printf("lr\n");
            while(j<maxC){
                j++;
                //printf("i j %d %d v %d\n",i,j,matrix[i][j]);
                //boundy position will also be added into path
                path.push_back(matrix[i][j]);
            }
            
            //for example (0,4) is not push in previous
            //the j is at boundy pos now
            if(path.size()==(rows*cols)) {break;}
            //printf("minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);
            if(maxC>minC) {maxC=maxC-1;}
            //printf("AC minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);
            //printf("ud\n");
            //up to down
            while(i<maxR){
                i++;
                //printf("i j %d %d v %d\n",i,j,matrix[i][j]);
                path.push_back(matrix[i][j]);
            }

            //trim one column case
            if(path.size()==(rows*cols)) {break;}

            // for example i is 2 in first itertaion, (2,3) not push
            //printf("minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);            
            if(maxR>minR) {maxR=maxR-1;}
            //printf("AC minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);
            //printf("rl\n");
            
            //if the up to down does not move back
            //then this one should not be execute
            //this is one line operation
            //right to left
            while(j>minC){
                j--;
                //printf("i j %d %d v %d\n",i,j,matrix[i][j]);
                path.push_back(matrix[i][j]);
            }
            //for example, when j=0, the (2,0) is not pushed now
            //shrink
            //printf("minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR); 
            if(maxC>minC) {minC=minC+1;}
            //printf("AC minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);

            //printf("du\n");
            //printf("minC maxC %d %d minR maxR %d %d\n",minC,maxC,minR,maxR);            
            //down to up
            while(i>minR){
                i--;  
                //printf("i j %d %d v %d\n",i,j,matrix[i][j]);
                path.push_back(matrix[i][j]);
            }
        }
        //push last
        
        //this is for the case when we insert element firstly
        //then consider the boundry, we need to consider last element separately
        //if(path.size()==(rows*cols-1)){
        //    path.push_back(matrix[i][j]);
        //}
        
        return path;
    }   
};

59 Spiral Matrix II

After getting familir with all tips and concepts discussed in this blog, we can solve the code and write workable code really quickly

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
 
        //reserve matrix
        vector<vector<int>> output (n,vector<int>(n));

        //fill in the matrix
        output[0][0]=1;
        int v = 1;

        //move then record
        int minC=0;
        int maxC=n-1;
        int minR=0;
        int maxR=n-1;
        
        int i=0,j=0;
        while(v<=n*n){
            //minR +1
            if(maxR>minR) {minR++;}
            //move lr
            while(j<maxC){
                j++;
                v++;
                output[i][j]=v;
            }
            if(v==n*n) {break;}

            //maxC -1
            if(maxC>minC){maxC--;}
            //move u to d
            while(i<maxR){
                i++;
                v++;
                output[i][j]=v;
            }

            if(v==n*n) {break;}
            //maxR -1
            if(maxR>minR){maxR--;}
            
            //move right to left
            while(j>minC){
                j--;
                v++;
                output[i][j]=v;
            }
            //minC++
            if(maxC>minC){minC++;}

            while(i>minR){
                i--;
                v++;
                output[i][j]=v;
            }

        }

        return output;
    }
};

885 Spiral Matrix III

This question is a little bit tricky for the boundry case, the key point is to decide wheather the right up conner belongs to the horizental line or vertical line.

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> path;
        int i=rStart;
        int j=cStart;
        //maintain the bounds
        int minR=i,maxR=i;
        int minC=j,maxC=j;
        // wall is C=-1 C=cols
        // wall is R=-1 R=rows
        //push current
        path.push_back({i,j});
        while(path.size()<rows*cols){
            //move right bounds before moving from left to right
            if(maxC<cols){
                maxC = maxC + 1;
            }
            while(j < maxC){
                j++;
                //when move to the wall (bounds overlap with wall), do not push
                if(j!=cols && i!=-1){path.push_back({i,j});}
            }
            //when this while loop completes, the j goes to the maxC's position

            //expand bound before moving down
            if(maxR<rows){
                maxR=maxR+1;
            }

            //from right up to right down
            while(i<maxR){
                //move step
                i++;
                if(i!=rows && j!=cols){ path.push_back({i,j});}
            }

            //move left bounds before moving from right to left
            if(minC>=0){
                minC=minC-1;
            }

            //from down element to most left
            while(j>minC){
                j--;
                if(j!=-1 && i!=rows) {path.push_back({i,j});}
            }

            //move left bounds after left to right move
            //Similarly, the boundry can expand till the wall's position
            if(minR>=0){
                minR=minR-1;
            }

            while(i>minR){
                i--;
                if(i!=-1 && j!=-1){path.push_back({i,j});}
            }
        }
        return path;
        
    }
};

Another solution is to update metadata firstly and then move, it assumes that the element at the right up corner is the one that need to be pushed through vertival line. Maybe I am more comfortable with this type of coding style. Becareful to only push the element into the path when it is not at the wall. We basically put an ghost region among the matrix. When maxC/maxR and minC/minR go to the ghost region, it does not change further. When pointer goes to the ghost region, it will not be pushed into the path.

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> path;
        int i=rStart;
        int j=cStart;
        //maintain the bounds
        int minR=i,maxR=i;
        int minC=j,maxC=j;
        // wall is C=-1 C=cols
        // wall is R=-1 R=rows
        while(path.size()<rows*cols){
            //move right bounds before moving from left to right
            //maxC can overlap with the wall at last iteration
            //left to right
            if(maxC<cols){
                maxC = maxC + 1;
            }
            while(j < maxC){
                //when move to the wall (bounds overlap with wall), do not push
                if(j!=cols && j!=-1 && i!=-1){path.push_back({i,j});}
                //move when less than bound
                j++;
            }
            //when out of while loop, pointer is at right up corner
            //right up element is not in path
            if(path.size()==rows*cols){break;}
            //up to down
            //expand bound before moving down
            if(maxR<rows){
                maxR=maxR+1;
            }
            //from right up to right down
            while(i<maxR){
                //move step
                if(i!=rows && i!=-1 && j!=cols){ path.push_back({i,j});}
                //when i < maxR < row, can ++
                i++;
            }
            if(path.size()==rows*cols){break;}
            //right to left
            if(minC>=0){
                minC=minC-1;
            }
            //from down element to most left
            while(j>minC){
                if(j!=cols && j!=-1 && i!=rows) {path.push_back({i,j});}
                j--;
            }
            //bottom to up
            //move left bounds after left to right move
            //Similarly, the boundry can expand till the wall's position
            if(minR>=0){
                minR=minR-1;
            }
            while(i>minR){
                if(i!=-1 && i!= rows && j!=-1){path.push_back({i,j});}
                i--;
            }
        }
        return path;
    }
};

2326 Spiral Matrix IV

This can be solved quickly based on previous one, just following the same method and adding a small trick for getting values from the nodelist

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int getValue(ListNode*& head){
        if(head==nullptr){
            return -1;
        }
        int v = head->val;
        //only move to next element
        //when the current is not empty
        head=head->next;
        return v;
    }
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {

        //specify bounds
        //m row n col
        int minR=0;
        int maxR=m-1;

        int minC=0;
        int maxC=n-1;
        
        //reserve matrix
        vector<vector<int>> output (m,vector<int>(n));
        int i=0,j=0;

        //insert first
        output[0][0]=getValue(head);

        //number of inserted elements
        int c = 1;
        
        //go through each element of matrix
        while(c<=m*n){
            //move minR
            if(maxR>minR) {minR++;}
            
            //move l ro r
            while(j<maxC){
                j++;
                c++;
                output[i][j]=getValue(head);
            }
            if(maxC>minC) {maxC--;}
            if(c==m*n){break;}

            //move up to bottom
            while(i<maxR){
                i++;
                c++;
                output[i][j]=getValue(head);
            }
            if(maxR>minR) {maxR--;}
            if(c==m*n){break;}

            //move right to left
            while(j>minC){
                j--;
                c++;
                output[i][j]=getValue(head);
            }
            if(maxC>minC) {minC++;}

            //move bottom to up
            while(i>minR){
                i--;
                c++;
                output[i][j]=getValue(head);
            }
        }
        return output;
    }
};