Why would this give TLE? O(1) move, O(m*n) initialization


  • 0
    L

    Technically a snake can grow as big as m*n, and since we're calling move many times, wouldn't you want to optimize the initialization? Had I replaced my [i,j]!=self.snake[0] and self.s[i][j]) with [i,j]!=self.snake[0] and [i,j] in self.snake and removed my matrix self.s, the solution gets accepted. Could this be a case of bad test cases that don't consider a very large snake?

    class SnakeGame(object):
    
        def __init__(self, width,height,food):
            """
            Initialize your data structure here.
            @param width - screen width
            @param height - screen height 
            @param food - A list of food positions
            E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
            :type width: int
            :type height: int
            :type food: List[List[int]]
            """
            self.snake=collections.deque([[0,0]])
            self.s=[[0]*width for _ in xrange(height)]
            self.s[0][0]=1
            self.food=food[::-1]
            self.w=width
            self.h=height
            self.d={'U':[-1,0],'L':[0,-1],'R':[0,1],'D':[1,0]}
            
    
        def move(self, direction):
            """
            Moves the snake.
            @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
            @return The game's score after the move. Return -1 if game over. 
            Game over when snake crosses the screen boundary or bites its body.
            :type direction: str
            :rtype: int
            """
        
            i,j=self.snake[-1][0]+self.d[direction][0],self.snake[-1][1]+self.d[direction][1]
            if i<0 or i>=self.h or j<0 or j>=self.w or ([i,j]!=self.snake[0] and self.s[i][j]): return -1
            taili,tailj=self.snake[0]
            if self.food and [i,j]==self.food[-1]:
                self.food.pop()
            else:
                self.s[taili][tailj],self.s[i][j]=0,1
                self.snake.popleft()
            self.snake.append([i,j])
            self.s[i][j]=1
            
            return len(self.snake)-1

Log in to reply
 

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