Not the fastest but straight forward c++ solution using state


  • 0
    K

    This can definitely be optimized but it seems straightforward on my first go. Basically, keep a state of the direction you are traveling in the matrix and when you reach the end, switch the state and start traveling in that direction. Whenever you reach the end, increment the row or column end so you don't have duplicates, and whenever you come back to the beginning increment the row or column beginning for the same reason. Row beginning starts at 1 because its the first direction traveled. Algorithm stops when all of the elements have been counted for.

    class Solution {
    public:
        enum state {RIGHT, DOWN, LEFT, UP};
        
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int> res;
            if (matrix.size() == 0)
                return res;
    	int m = matrix[0].size(), j = 0;
    	int n = matrix.size(), i = 0;
    	int count = 0;
    	int numElements = m*n;
    	state s = RIGHT;
    	int rowBegin = 1, colBegin = 0, rowEnd = 0, colEnd = 0;
    
    	while (count < numElements) {
    		switch (s) {
    		case RIGHT:
    			if (j == m - colEnd - 1)
    			{
    				s = DOWN;
    				colEnd++;
    				res.push_back(matrix[i++][j]);
    			}
    			else
    			{
    				res.push_back(matrix[i][j++]);
    			}
    			break;
    		case DOWN:
    			if (i == n - rowEnd - 1)
    			{
    				s = LEFT;
    				rowEnd++;
    				res.push_back(matrix[i][j--]);
    			}
    			else
    			{
    				res.push_back(matrix[i++][j]);
    			}
    			break;
    		case LEFT:
    			if (j == colBegin)
    			{
    				s = UP;
    				colBegin++;
    				res.push_back(matrix[i--][j]);
    			}
    			else
    			{
    				res.push_back(matrix[i][j--]);
    			}
    			break;
    		case UP:
    			if (i == rowBegin)
    			{
    				s = RIGHT;
    				rowBegin++;
    				res.push_back(matrix[i][j++]);
    			}
    			else
    				res.push_back(matrix[i--][j]);
    			break;
    		}
    		count++;
    	}
    	return res;
       }
    };
    

Log in to reply
 

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