Student Attendance Record II

I'm currently working on the Student Attendance Record II problem:


Given a positive integer \$n\$, return the number of all possible
attendance records with length \$n\$, which will be regarded as
rewardable. The answer may be very large, return it after mod 109 + 7.


A student attendance record is a string that only contains the
following three characters:

'A' : Absent.
'L' : Late.
'P' : Present.

A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

The idea is to use Dynamic Programming to use the results for smaller n to calculate the results of bigger n. I'm currently keeping two lists - one to track L and P and the other - to track A:

MODULO = 10 ** 9 + 7

class Solution(object):
    def checkRecord(self, n):
        lates = [[0, 0, 0], [1, 1, 0]] + [[0, 0, 0] for _ in xrange(2, n + 1)]
        absences = [[0, 0, 0], [1, 0, 0]] + [[0, 0, 0] for _ in xrange(2, n + 1)]

        for i in xrange(2, n + 1):
            last_late_row = lates[i - 1]
            last_late_row_sum = last_late_row[0] + last_late_row[1] + last_late_row[2]

            last_absence_row = absences[i - 1]
            last_absence_row_sum = last_absence_row[0] + last_absence_row[1] + last_absence_row[2]

            lates[i] = last_late_row_sum % MODULO, last_late_row[0], last_late_row[1]
            absences[i] = ((last_late_row_sum + last_absence_row_sum) % MODULO, last_absence_row[0], last_absence_row[1])

        return (sum(lates[n]) + sum(absences[n])) % MODULO

The code works, but it does not pass the Time Limit requirements for big n. Even though, for n = 100000 LeetCode OJ runs it for only ~220ms.

How would you recommend to improve on running time?

It's often helpful to explain the problem to someone else just to see things clearer and come up with a possible solution. Here is what I've just realized.

We don't actually need to keep the complete list during our calculations and only need a single row at a time. Let's reuse it and recalculate the cell values in the loop:

MODULO = 10 ** 9 + 7

class Solution(object):
    def checkRecord(self, n):
        lates = [1, 1, 0]
        absences = [1, 0, 0]

        for i in xrange(2, n + 1):
            sum_lates = sum(lates)
            lates = sum_lates % MODULO, lates[0], lates[1]
            absences = (sum_lates + sum(absences) % MODULO, absences[0], absences[1])

        return (sum(lates) + sum(absences)) % MODULO

I think I've seen this technique before and, if I remember correctly, it is called "Rolling Array".

StackExchange Code Review Q#160887, answer score: 4