I got this problem while I was solving a problem of self crossing. It’s like the snake game.

Given x = [2, 1, 1, 2], we start from 0, and then we go up for 2, go left for 1, go right for 1 and go down for 2. The goal is to calculate if it will self cross or not. As the given steps are always integers, I thought about using a matrix and every time when it get through a point, I set the point to 1. Like this I could check if the point has been visited or not.

I think in this way, all the memory that Python will make is just the assignment of the matrix. That’s why I don’t understand when the input x is huge, and why it says *“memory out of limit”*. For me, I think the memory is the same as the matrix has been initiated before.

How can I fix this?

class Solution(object): def isSelfCrossing(self, x): """ :type x: List[int] :rtype: bool """ m = [[0 for j in xrange(1000)] for j in xrange(1000)] m[0][0] = 1 a, b = 0, 0 flag = 0 for i in x: flag = (flag + 1) % 4 if flag == 1: for temp in xrange(1, i+1): b += 1 if m[a][b] != 0: return True else: m[a][b] = 1 elif flag == 2: for temp in xrange(1, i+1): a -= 1 if m[a][b] != 0: return True else: m[a][b] = 1 elif flag == 3: for temp in xrange(1, i+1): b -= 1 if m[a][b] != 0: return True else: m[a][b] = 1 else: for temp in xrange(1, i+1): a += 1 if m[a][b] != 0: return True else: m[a][b] = 1 return False

## Answer

Using lists for a boolean matrix in Python rarely makes sense. Try storing pairs of integers in a `set`

and replace

m = ... # with m = set() m[a][b] != 0 # with (a, b) in m m[a][b] = 1 # with m.add((a, b))

Alternatively, you can create a flat `bytearray`

with the same number of elements as `m`

and index it as `a * 1000 + b`

. This, however, might lead to subtle indexing bugs, so I strongly suggest to give `set`

a try first.