# 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 + last_late_row + last_late_row

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

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

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?

• Hey. Can you explain your algorithm? – Raghuram Vadapalli Sep 12 '17 at 17:37

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, lates
absences = (sum_lates + sum(absences) % MODULO, absences, absences)

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


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