552. Student Attendance Record II


Problem Description

The problem asks us to determine the number of possible attendance records of length n that allows a student to be eligible for an attendance award. A record is represented by a string consisting of the characters 'A' for absent, 'L' for late, and 'P' for present. A student qualifies for an award if they satisfy two conditions:

  1. They are absent for fewer than 2 days in total.
  2. They are not late for 3 or more consecutive days.

We must return the count of such attendance records modulo 10^9 + 7, as this number could be very large.

Intuition

To arrive at the solution, we can use Dynamic Programming (DP). Since we need to keep track of absent and late counts, we can use a 3-dimensional DP array, where dp[i][j][k] represents the number of permutations of attendance records ending at day 'i', with 'j' representing whether the student has been absent 0 or 1 times, and 'k' representing the count of the latest consecutive late days (0, 1, or 2).

Thinking through the possible cases:

  • The student can be present (P) on any given day, which doesn't affect their absences or increase the count of consecutive late days.
  • They can be late (L), which resets the consecutive present day count but has to be carefully added so as not to surpass two consecutive late days.
  • They can be absent (A), which increases the count of absences unless they have already been absent once.

The base case for the first day (i = 0) needs to be initialized to show that they can be present, late, or absent, but still be eligible for the award.

By iterating through the days and for each day computing the possible ending in 'P', 'L', or 'A', while adhering to the rules, we can incrementally construct our DP table up to day 'n'.

Finally, the sum of all possible records up to day 'n - 1' considering both absentee scenarios, and not exceeding two consecutive 'L's gives us the total count modulo 10^9 + 7.

Solution Approach

The solution uses a dynamic programming approach to keep track of eligible attendance records by constructing a 3D DP array dp with dimensions n, 2, and 3; where n is the number of days, 2 represents being absent for either 0 or 1 day (j index), and 3 represents the number of consecutive late days (k index).

Here are the detailed steps of the algorithm:

  1. Initialization: The index [i][j][k] in dp corresponds to the day i, absent status j, and consecutive late status k.

    • Day i = 0: Initialize dp[0][0][0], dp[0][0][1], and dp[0][1][0] to 1. This covers the cases where the student is present, late, or absent for the first day.
  2. Filling the DP table: Iterate over days i from 1 to n - 1:

    • For a Present (P) day: Update dp[i][0][0] and dp[i][1][0] to include all records from previous days where the student was present, late, or absent, ensuring that they are still eligible.

    • For a Late (L) day: The late status k is incremented by 1, but cannot exceed 2, which represents being late for 3 or more consecutive days. Set dp[i][0][1] to dp[i - 1][0][0], dp[i][0][2] to dp[i - 1][0][1], dp[i][1][1] to dp[i - 1][1][0], and dp[i][1][2] to dp[i - 1][1][1].

    • For an Absent (A) day: Only include records from the previous day where the student hasn't been absent before (j=0). Set dp[i][1][0] by summing up dp[i - 1][0][0], dp[i - 1][0][1], and dp[i - 1][0][2].

    At each step, we take the result modulo 10^9 + 7 to avoid integer overflow due to large values.

  3. Computing the answer: Sum up all the elements dp[n - 1][j][k], where j can be 0 or 1, and k can be 0, 1, or 2, since we want to consider all possible eligible sequences. This sum gives the total number of attendance records of length n that allow a student to be eligible for an attendance award, modulo 10^9 + 7.

Throughout the implementation, we're using the modulo operation due to the constraints that the answer may be very large and must be returned modulo 10^9 + 7 to fit within the integer range.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through an example using the provided solution approach to calculate the number of valid attendance records for n = 3.

  1. Initialization:

    • We start with day i = 0 and initialize our dp array such that dp[0][0][0] = 1 (student was present), dp[0][0][1] = 1 (student was late), and dp[0][1][0] = 1 (student was absent).
  2. Filling the DP table:

    • For day i = 1, we have:

      • Present (P) case: Since the student can be present after any attendance status of the previous day without restrictions, we set dp[1][0][0] = sum(dp[0][0]) = 2 (from being P or L on the first day), and dp[1][1][0] = sum(dp[0][1]) + sum(dp[0][0]) = 3 (from being P on the first day and A on the second, L on the first and P on the second, or A on the first and P on the second).
      • Late (L) case: The student can only be late for a maximum of two consecutive days, so we update dp[1][0][1] (was P now L) and dp[1][1][1] (was A now L), dp[1][0][1] = dp[0][0][0] = 1 and dp[1][1][1] = dp[0][1][0] = 1.
      • Absent (A) case: The student can be absent for at most once, so dp[1][1][0] (was P now A) is already covered in Present case, no update needed for this case.
    • For day i = 2, we repeat the process:

      • Present (P) case: dp[2][0][0] = sum(dp[1][0]) = 3 (from all P and L scenarios of the previous day where the student wasn’t absent), and dp[2][1][0] = sum(dp[1][1]) + sum(dp[1][0]) = 4 (from all P and L scenarios of the previous day and adding A scenarios where the student wasn't absent on previous days).
      • Late (L) case: Update the dp array considering the consecutive L scenarios, dp[2][0][1] = dp[1][0][0] = 3 and dp[2][0][2] = dp[1][0][1] = 1; similarly for j=1, dp[2][1][1] = dp[1][1][0] = 3 and dp[2][1][2] = dp[1][1][1] = 1.
      • Absent (A) case: dp[2][1][0] = sum(dp[1][0]) = 3 (from all non-absent previous day records).
  3. Computing the answer:

    • After filling in the dp table, we sum up all the possibilities on the last day i = 2 considering both j (absent count) and k (consecutive late count), resulting in the final count: dp[2][0][0] + dp[2][0][1] + dp[2][0][2] + dp[2][1][0] + dp[2][1][1] + dp[2][1][2] = 3 + 3 + 1 + 3 + 3 + 1 = 14.

So, for n = 3, there are 14 valid attendance records that meet the criteria for an awards eligibility, and the final answer modulo 10^9 + 7 would be 14 (since 14 is already less than 10^9 + 7).

Python Solution

1class Solution:
2    def checkRecord(self, n: int) -> int:
3        MOD = 10**9 + 7  # Define the modulus for the problem, to prevent overflow.
4        # Initialize a 3D DP array where:
5        # 1st dimention is the day,
6        # 2nd dimention is the absence count (0 or 1, because more than 1 is not allowed),
7        # 3rd dimention is the late count (0, 1, or 2, because more than 2 in a row is not allowed).
8        dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n)]
9
10        # Base cases: there is one way to have a sequence end in either 'P', 'L', or 'A' on the first day
11        dp[0][0][0] = 1  # Present
12        dp[0][0][1] = 1  # Late
13        dp[0][1][0] = 1  # Absent
14
15        # Iterate over each day starting from the second one.
16        for i in range(1, n):
17            # If the day ends in 'A' (Absent), the sequence must not have any 'A's before.
18            # We can have 0, 1, or 2 'L's (Late) before this 'A'.
19            dp[i][1][0] = sum(dp[i - 1][0][l] for l in range(3)) % MOD
20
21            # If the day ends in 'L' (Late), the previous day can have 0 or 1 'L' or be 'P' (Present).
22            dp[i][0][1] = dp[i - 1][0][0]  # One possible 'L' before current day
23            dp[i][0][2] = dp[i - 1][0][1]  # Two possible 'L's before current day
24            dp[i][1][1] = dp[i - 1][1][0]  # One 'L', with an 'A' at some point before
25            dp[i][1][2] = dp[i - 1][1][1]  # Two 'L's, with an 'A' before
26
27            # If the day ends in 'P' (Present), there are no constraints for this particular day.
28            for j in range(2):  # j=0: no 'A' yet, j=1: there has been an 'A'
29                dp[i][j][0] = sum(dp[i - 1][j][l] for l in range(3)) % MOD
30
31        # Calculate the total number of valid attendance record combinations
32        # by summing over all possibilities on the last day.
33        total = 0
34        for j in range(2):
35            for k in range(3):
36                total = (total + dp[n - 1][j][k]) % MOD
37        return total  # Return the total number of valid combinations.
38

Java Solution

1class Solution {
2    private static final int MOD = 1000000007;
3
4    public int checkRecord(int n) {
5        // dp[i][j][k]: number of valid sequences of length i, with j 'A's and a trailing 'L's of length k.
6        long[][][] dp = new long[n][2][3];
7
8        // Base cases
9        dp[0][0][0] = 1; // P
10        dp[0][0][1] = 1; // L
11        dp[0][1][0] = 1; // A
12
13        // Building the DP table for subsequences of length i
14        for (int i = 1; i < n; i++) {
15            // Adding 'A' to the sequence ending without 'A's and less than 2 'L's
16            dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
17
18            // Adding 'L' to the sequence, considering previous 'L's and 'A's
19            dp[i][0][1] = dp[i - 1][0][0];                 // Previous has no trailing 'L'
20            dp[i][0][2] = dp[i - 1][0][1];                 // Previous has 1 trailing 'L'
21            dp[i][1][1] = dp[i - 1][1][0];                 // Previous has an 'A' and no trailing 'L'
22            dp[i][1][2] = dp[i - 1][1][1];                 // Previous has an 'A' and 1 trailing 'L'
23
24            // Adding 'P' to the sequence, considering previous 'A's and 'L's
25            dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
26            dp[i][1][0] = (dp[i][1][0] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD;
27        }
28
29        // Sum up all valid sequences
30        long ans = 0;
31        for (int j = 0; j < 2; j++) {     // 0 or 1 'A's
32            for (int k = 0; k < 3; k++) { // 0 to 2 trailing 'L's
33                ans = (ans + dp[n - 1][j][k]) % MOD; // Aggregate counts
34            }
35        }
36        return (int) ans; // Final answer
37    }
38}
39

C++ Solution

1constexpr int MOD = 1e9 + 7;
2
3class Solution {
4public:
5    int checkRecord(int n) {
6        // Define 'll' as shorthand for 'long long' type
7        using ll = long long;
8        // Create a 3D vector to hold the state information
9        // dp[i][j][k] represents the number of valid sequences of length i
10        // where j tracks the absence count (0 for no A, 1 for one A)
11        // and k tracks the late count (0, 1, or 2 consecutive L's)
12        vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(2, vector<ll>(3)));
13
14        // base cases for first day
15        dp[0][0][0] = 1; // P
16        dp[0][0][1] = 1; // L
17        dp[0][1][0] = 1; // A
18
19        for (int i = 1; i < n; ++i) {
20            // For A: append A after sequences that do not contain A ('j' == 0)
21            dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
22
23            // For L: append L after sequences ending in no L or 1 L
24            dp[i][0][1] = dp[i - 1][0][0]; // no L followed by L
25            dp[i][0][2] = dp[i - 1][0][1]; // 1 L followed by another L
26            dp[i][1][1] = dp[i - 1][1][0]; // no L followed by L, already contains A
27            dp[i][1][2] = dp[i - 1][1][1]; // 1 L followed by another L, already contains A
28
29            // For P: append P after any sequence
30            dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
31            // for sequences that already contain A, append P
32            dp[i][1][0] = (dp[i][1][0] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD;
33        }
34
35        // Calculate the final result by summing up all possible sequences of length 'n'
36        ll result = 0;
37        for (int absence = 0; absence < 2; ++absence) {
38            for (int late = 0; late < 3; ++late) {
39                result = (result + dp[n - 1][absence][late]) % MOD;
40            }
41        }
42        return result;
43    }
44};
45

Typescript Solution

1// MOD constant for modulo operation to prevent overflow
2const MOD: number = 1e9 + 7;
3
4// A function to check the number of valid sequences of attendance records of length n
5function checkRecord(n: number): number {
6    // Define 'll' as alias for 'number' type since TypeScript doesn't have 'long long' type
7    type ll = number;
8
9    // Create a 3D array to hold the state information
10    // dp[i][j][k] represents the number of valid sequences of length i
11    // where j tracks the absence count (0 for no A, 1 for one A)
12    // and k tracks the late count (0, 1, or 2 consecutive L's)
13    let dp: ll[][][] = Array.from({ length: n }, () =>
14        Array.from({ length: 2 }, () => Array(3).fill(0))
15    );
16
17    // Base cases for the first day
18    dp[0][0][0] = 1; // P present
19    dp[0][0][1] = 1; // L late
20    dp[0][1][0] = 1; // A absent
21
22    for (let i = 1; i < n; ++i) {
23        // For A: append A after sequences that do not contain A ('j' == 0)
24        dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
25
26        // For L: append L after sequences ending in no L or 1 L
27        dp[i][0][1] = dp[i - 1][0][0]; // No L followed by L
28        dp[i][0][2] = dp[i - 1][0][1]; // 1 L followed by another L
29        dp[i][1][1] = dp[i - 1][1][0]; // No L followed by L, already contains A
30        dp[i][1][2] = dp[i - 1][1][1]; // 1 L followed by another L, already contains A
31
32        // For P: append P after any sequence
33        dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
34        // For sequences that already contain A, append P
35        dp[i][1][0] = (dp[i][1][0] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD;
36    }
37
38    // Calculate the final result by summing up all possible sequences of length 'n'
39    let result: ll = 0;
40    for (let absence = 0; absence < 2; ++absence) {
41        for (let late = 0; late < 3; ++late) {
42            result = (result + dp[n - 1][absence][late]) % MOD;
43        }
44    }
45    return result;
46}
47

Time and Space Complexity

Time Complexity

The algorithm uses a dynamic programming approach to calculate the number of ways a student can attend classes over n days without being absent for consecutive 3 days and without being absent for 2 days in total. The time complexity is determined by the triple-nested loops:

  • The outer loop runs n times, which represents each day.
  • For each day, there are 2 states of absence (either the student has been absent once or not at all), and 3 states for tardiness (the student has not been late, has been late once, or has been late twice).

Hence, the time complexity of the algorithm is O(2 * 3 * n), which simplifies to O(n) because the constants can be removed in Big O notation.

Space Complexity

The space complexity is determined by the space required to store the dynamic programming states. The dp array is a two-dimensional array where the first dimension is n, and the second dimension is a 2x3 matrix to store all different states for absences and lates.

Therefore, the space complexity is O(2 * 3 * n), which simplifies to O(n) as the constants can be disregarded.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫