Leetcode 957. Prison Cells After N Days
The important part
They want something below O(n). Using map is a good idea but actually you should find the cycles and return the right position on the cycle instead of computing line by line.
Spoiler (possible solution)
Change:
            if tuple(cells) in step_map:
                return  step_map[tuple(cells)]

to:
            if tuple(cells) in step_map:
                cycle = list()
                head = tuple(cells)
                cycle.append(head)
                previous = head
                while True:
                    next_node = tuple(step_map[previous])
                    if next_node == head:
                        return list(cycle[(N - k) % len(cycle)])
                    cycle.append(next_node)
                    previous = next_node


Old edit - Some small improvements
There are some O(m) operations multiple times...
For example:
 tmp = [0] + tmp + [0]

Python operation for that is O(m). Therefore, your solution is O(nm).
step_map[tuple(cells)] = tmp

this is also O(m).