Python memory – The memory limit exceeded for Python code

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.

Leave a Reply

Your email address will not be published. Required fields are marked *