Student Attendance Record II

How it works

This is an alternative space-optimized formulation that iterates forward from the empty state. We maintain a 2x3 DP array and update it in place, swapping between current and next arrays each iteration.

Steps

1. Initialize dp[0][0] = 1 (empty record with no absences and no consecutive lates).
2. For each position from 1 to n:
   • Create a fresh next state array.
   • For each (cntA, cntL) combination, compute transitions:
     • 'P': adds to state (cntA, 0) from any (cntA, cntL).
     • 'A': adds to state (cntA, 0) from (cntA - 1, cntL) if cntA > 0.
     • 'L': adds to state (cntA, cntL) from (cntA, cntL - 1) if cntL > 0.
   • Swap arrays and continue.
3. Sum all six states at the end for the final count.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting to Reset Consecutive Late Count

When placing a 'P' (present) or 'A' (absent), the consecutive late count resets to 0. A common mistake is to carry forward the late count, which leads to undercounting valid sequences. Only placing 'L' increments the late counter; all other characters reset it.

Allowing More Than One Absence

The problem states that a valid record has fewer than 2 absences, meaning at most 1 absence is allowed. Tracking the absence count incorrectly or allowing transitions that would result in 2 or more absences will produce an inflated count.

Integer Overflow Without Modular Arithmetic

The number of valid records grows exponentially with n, and the problem requires the result modulo 10^9 + 7. Failing to apply the modulo operation after each addition can cause integer overflow, especially in languages with fixed-size integers like Java or C++.

Incorrect State Transitions for Late Count

The late count can only be 0, 1, or 2. When adding 'L', you transition from late count k to k+1, but only if k < 2. Allowing a transition to late count 3 or mishandling the boundary condition will break the constraint of no more than 2 consecutive lates.

Misunderstanding the State Space

The DP state requires tracking both the absence count (0 or 1) and the consecutive late count (0, 1, or 2), giving 6 total states per position. Collapsing these into fewer states or incorrectly indexing the state array leads to wrong answers.

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 1000000007
        dp = [[0] * 3 for _ in range(2)]

        dp[0][0] = 1  # Base case

        for i in range(1, n + 1):
            next_dp = [[0] * 3 for _ in range(2)]

            for cntA in range(2):
                for cntL in range(3):
                    # Choose P
                    next_dp[cntA][0] = (next_dp[cntA][0] + dp[cntA][cntL]) % MOD

                    # Choose A
                    if cntA > 0:
                        next_dp[cntA][0] = (next_dp[cntA][0] + dp[cntA - 1][cntL]) % MOD

                    # Choose L
                    if cntL > 0:
                        next_dp[cntA][cntL] = (next_dp[cntA][cntL] + dp[cntA][cntL - 1]) % MOD

            dp = next_dp

        return sum(dp[cntA][cntL] for cntA in range(2) for cntL in range(3)) % MOD

class Solution {
public:
    int checkRecord(int n) {
        const int MOD = 1000000007;
        vector<vector<int>> dp(2, vector<int>(3, 0));

        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            vector<vector<int>> nextDp(2, vector<int>(3, 0));

            for (int cntA = 0; cntA < 2; cntA++) {
                for (int cntL = 0; cntL < 3; cntL++) {
                    // Choose P
                    nextDp[cntA][0] = (nextDp[cntA][0] + dp[cntA][cntL]) % MOD;

                    // Choose A
                    if (cntA > 0) {
                        nextDp[cntA][0] = (nextDp[cntA][0] + dp[cntA - 1][cntL]) % MOD;
                    }

                    // Choose L
                    if (cntL > 0) {
                        nextDp[cntA][cntL] = (nextDp[cntA][cntL] + dp[cntA][cntL - 1]) % MOD;
                    }
                }
            }

            dp = nextDp;
        }

        int result = 0;
        for (int cntA = 0; cntA < 2; cntA++) {
            for (int cntL = 0; cntL < 3; cntL++) {
                result = (result + dp[cntA][cntL]) % MOD;
            }
        }

        return result;
    }
};