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:
- They are absent for fewer than 2 days in total.
- 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
.
Learn more about Dynamic Programming patterns.
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:
-
Initialization: The index
[i][j][k]
indp
corresponds to the dayi
, absent statusj
, and consecutive late statusk
.- Day
i = 0
: Initializedp[0][0][0]
,dp[0][0][1]
, anddp[0][1][0]
to1
. This covers the cases where the student is present, late, or absent for the first day.
- Day
-
Filling the DP table: Iterate over days
i
from1
ton - 1
:-
For a Present (P) day: Update
dp[i][0][0]
anddp[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. Setdp[i][0][1]
todp[i - 1][0][0]
,dp[i][0][2]
todp[i - 1][0][1]
,dp[i][1][1]
todp[i - 1][1][0]
, anddp[i][1][2]
todp[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
). Setdp[i][1][0]
by summing updp[i - 1][0][0]
,dp[i - 1][0][1]
, anddp[i - 1][0][2]
.
At each step, we take the result modulo
10^9 + 7
to avoid integer overflow due to large values. -
-
Computing the answer: Sum up all the elements
dp[n - 1][j][k]
, wherej
can be0
or1
, andk
can be0
,1
, or2
, since we want to consider all possible eligible sequences. This sum gives the total number of attendance records of lengthn
that allow a student to be eligible for an attendance award, modulo10^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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example using the provided solution approach to calculate the number of valid attendance records for n = 3
.
-
Initialization:
- We start with day
i = 0
and initialize ourdp
array such thatdp[0][0][0] = 1
(student was present),dp[0][0][1] = 1
(student was late), anddp[0][1][0] = 1
(student was absent).
- We start with day
-
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), anddp[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) anddp[1][1][1]
(was A now L),dp[1][0][1] = dp[0][0][0] = 1
anddp[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.
- Present (P) case: Since the student can be present after any attendance status of the previous day without restrictions, we set
-
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), anddp[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
anddp[2][0][2] = dp[1][0][1] = 1
; similarly forj=1
,dp[2][1][1] = dp[1][1][0] = 3
anddp[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).
- Present (P) case:
-
-
Computing the answer:
- After filling in the
dp
table, we sum up all the possibilities on the last dayi = 2
considering bothj
(absent count) andk
(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
.
- After filling in the
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
).
Solution Implementation
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
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
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
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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!