4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Hey. Can you explain your algorithm? \$\endgroup\$ – Raghuram Vadapalli Sep 12 '17 at 17:37
4
\$\begingroup\$

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".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.