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

• 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

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