Spiral matrix iii

Check out the problem description here.

Spiral Matrix III - LeetCode

Approach 1:

We keep a variable for horizontal direction , to keep track of number of steps to be taken in horizontal direction. And similarly for vertical direction. Each of them is incremented by 1 ,after moving in the respective direction by number of steps stored in that variable. Also while moving if the current position is inside the matrix , then the position added to the result list. Else if it is out of bounds , then it is not added to the result list. Finally, the result returned.

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int):
        total=rows*cols
        r0,c0=rStart,cStart
        h_unit,v_unit=1,1
        result=[]
        result.append([r0,c0])
        #print(result)
        while(len(result)<total):
            count=1
            while(count<=h_unit):
                c0+=1
                if(self.check_inside(r0,c0,rows,cols)):
                    result.append([r0,c0])
                count+=1
            h_unit+=1
            count=1
            while(count<=v_unit):
                r0+=1
                if(self.check_inside(r0,c0,rows,cols)):
                    result.append([r0,c0])
                count+=1
            count=1
            v_unit+=1
            while(count<=h_unit):
                c0-=1
                if(self.check_inside(r0,c0,rows,cols)):
                    result.append([r0,c0])
                count+=1
            count=1
            h_unit+=1
            while(count<=v_unit):
                r0-=1
                if(self.check_inside(r0,c0,rows,cols)):
                    result.append([r0,c0])
                count+=1
            v_unit+=1
        return(result)           
    def check_inside(self,r0,c0,rows,cols):
        if((0<=r0 and r0<rows) and (0<=c0 and c0<cols) ):
            return True 
        return False

Time :O((MAX(rows,cols))²)

Space:O(rows*cols)

Approach 2:

The same can be done in other way, using list that represent the direction to be moved.

East -> (0,1)

South->(1,0)

West->(0,-1)

North->(-1,0)

For this we create a direction array on which we iterate in a circular fashion

Also one point to not is length of path increase while in east and west direction, that is why the len_ is increased .

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int):
        total=rows*cols
        r0,c0=rStart,cStart
        direction=[0,1,0,-1,0]
        result=[[r0,c0]]
        len_,curr_direction=0,0
        while(len(result)<total):
            if(curr_direction==0 or curr_direction==2 ):
                len_+=1
            for k in range(0,len_):
                r0+=direction[curr_direction]
                c0+=direction[curr_direction+1]
                if(self.check_inside(r0,c0,rows,cols)):
                    result.append([r0,c0])
            curr_direction+=1
            curr_direction%=4
        return(result)           
    def check_inside(self,r0,c0,rows,cols):
        if((0<=r0 and r0<rows) and (0<=c0 and c0<cols) ):
            return True 
        return False

Time :O((MAX(rows,cols))²)

Space:O(rows*cols)