54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

def spiralOrder(self, matrix: List[List[int]]):
    result = []
    rows, columns = len(matrix), len(matrix[0])
    up = left = 0
    right = columns - 1
    down = rows - 1

    while len(result) < rows * columns:       
        for col in range(left, right + 1): # Traverse from left to right.
            result.append(matrix[up][col])

        for row in range(up + 1, down + 1): # Traverse downwards.
            result.append(matrix[row][right])

    
        if up != down:   # Make sure we are now on a different row.
            for col in range(right - 1, left - 1, -1): # right to left.
                result.append(matrix[down][col])

        if left != right:  # Make sure we are now on a different column.
            for row in range(down - 1, up, -1): # Traverse upwards.
                result.append(matrix[row][left])

        left += 1
        right -= 1
        up += 1
        down -= 1

    return result




def spiralOrder(self, matrix: List[List[int]]):
    #dirs = ['R', 'D', 'L', 'U']
    curDir, r, c = 0, 0, 0
    R, C = len(matrix), len(matrix[0])
    width, height = C, R
    first = True  output = []
    w, h  = 1, 1
   
    while True:
        output.append(matrix[r][c])
       
        if curDir == 0 or curDir == 2:
            if w == width:
                curDir = (curDir+1)%4
                if not first:
                    width -= 1
                first = False
                w = 1
                if h == height:
                    break                                           
        else:
            if h == height:
                curDir = (curDir+1)%4
                height -= 1
                h = 1
                if w == width:
                    break
           
        if curDir == 0:
            c += 1                        
            w = 1 if w == width else w + 1
        elif curDir == 2:
            c -= 1
            w = 1 if w == width else w + 1
        elif curDir == 1:
            r += 1
            h = 1 if h == height else h+1
        else:
            r -= 1
            h = 1 if h == height else h+1
    return output

Comments

Post a Comment

Popular posts from this blog

849. Maximize Distance to Closest Person

You are given an array representing a row of  seats  where  seats[i] = 1  represents a person sitting in the  i th  seat, and  seats[i] = 0  represents that the  i th  seat is empty  (0-indexed) . There is at least one empty seat, and at least one person sitting. Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.  Return  that maximum distance to the closest person . def maxDistToClosest ( self , seats : List [ int ]):                     taken = []         for i , occupied in enumerate ( seats ):         if occupied :             taken . append ( i )         S = len ( seats )     T = len ( taken )                 maxDist = max ( taken [ 0 ], S - taken [- 1 ] - 1 ) ...
Read more

347. Top K Frequent Elements

Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] def topKFrequent ( self , nums : List [ int ], k : int ):             freq = Counter ( nums )         return heapq . nlargest ( k , freq . keys (), key = freq . get )    
Read more

139. Word Break

Given a string  s  and a dictionary of strings  wordDict , return  true  if  s  can be segmented into a space-separated sequence of one or more dictionary words. Note  that the same word in the dictionary may be reused multiple times in the segmentation.   Example: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".   def wordBreak ( s : str , wordDict : List [ str ]):             word_set = set ( wordDict )     dp = [ False ] * ( len ( s ) + 1 )     dp [ 0 ] = True     for i in range ( 1 , len ( s ) + 1 ):         for j in range ( i ):             if dp [ j ] and s [ j : i ] in word_set :                 dp [ i ] = True                 break   ...
Read more