Student Attendance Record II
HardPrompt
An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:
'A': Absent.'L': Late.'P': Present.
Any student is eligible for an attendance award if they meet both of the following criteria:
- The student was absent (
'A') for strictly fewer than 2 days total. - The student was never late (
'L') for 3 or more consecutive days.
Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.
Example 1:
Input: n = 2
Output: 8
Explanation: There are 8 records with length 2 that are eligible for an award:
"PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).Example 2:
Input: n = 1
Output: 3Example 3:
Input: n = 10101
Output: 183236316
Constraints:
1 <= n <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion with memoization, a technique also known as top-down dynamic programming. We define a function that calculates the number of valid attendance records for a given number of remaining days n, the current count of absences, and the current count of consecutive lates. To avoid recomputing the same state multiple times, we store the result of each unique state (n, absences, lates) in a memoization table (a 3D array).
Algorithm
- Define a recursive function
solve(n, totalAbsences, consecutiveLates)which returns the number of valid attendance records of lengthngiven the current state. - The state is defined by three parameters:
n: the remaining number of days to consider.totalAbsences: the count of 'A's used so far.consecutiveLates: the count of consecutive 'L's at the end of the record built so far.
- Base Cases:
- If
totalAbsences >= 2orconsecutiveLates >= 3, the record is invalid. Return 0. - If
n == 0, we have successfully built a valid record of the required length. Return 1.
- If
- Memoization:
- Use a 3D array
memo[n+1][2][3]to store the results of subproblems. Initialize it with a sentinel value (e.g., -1). - Before computing, check if
memo[n][totalAbsences][consecutiveLates]already has a stored result. If so, return it.
- Use a 3D array
- Recursive Step:
- Calculate the number of ways by considering the three possibilities for the current day:
- Add 'P' (Present): The number of absences remains the same, and consecutive lates reset to 0. Recursively call
solve(n - 1, totalAbsences, 0). - Add 'A' (Absent): The number of absences increases by one, and consecutive lates reset to 0. Recursively call
solve(n - 1, totalAbsences + 1, 0). - Add 'L' (Late): The number of absences remains the same, and consecutive lates increase by one. Recursively call
solve(n - 1, totalAbsences, consecutiveLates + 1).
- Add 'P' (Present): The number of absences remains the same, and consecutive lates reset to 0. Recursively call
- Sum the results from these three calls (modulo
10^9 + 7).
- Calculate the number of ways by considering the three possibilities for the current day:
- Store the computed result in the memoization table before returning.
- The initial call to the function will be
solve(n, 0, 0).
Walkthrough
The core idea is to build the attendance record day by day, keeping track of the state necessary to check the validity rules. The state consists of the remaining length of the record to be generated, the total number of absences so far, and the number of consecutive lates at the very end of the partially built record.
When the function is called for a state, it first checks for base cases: if the state is already invalid (too many absences or lates), it returns 0. If the desired length is reached (n=0), it returns 1, signifying one valid record. If the result for the current state is already in our memoization table, we return it directly. Otherwise, we compute the result by recursively calling the function for the three possible next characters ('P', 'A', 'L'), updating the state accordingly, and summing up their results. The computed value is then stored in the memoization table to prevent redundant calculations in the future.
class Solution { int MOD = 1_000_000_007; int[][][] memo; public int checkRecord(int n) { memo = new int[n + 1][2][3]; for (int[][] arr2D : memo) { for (int[] arr1D : arr2D) { java.util.Arrays.fill(arr1D, -1); } } return solve(n, 0, 0); } private int solve(int n, int totalAbsences, int consecutiveLates) { if (totalAbsences >= 2 || consecutiveLates >= 3) { return 0; } if (n == 0) { return 1; } if (memo[n][totalAbsences][consecutiveLates] != -1) { return memo[n][totalAbsences][consecutiveLates]; } // Case 'P': Present long count = solve(n - 1, totalAbsences, 0); // Case 'A': Absent count = (count + solve(n - 1, totalAbsences + 1, 0)) % MOD; // Case 'L': Late count = (count + solve(n - 1, totalAbsences, consecutiveLates + 1)) % MOD; return memo[n][totalAbsences][consecutiveLates] = (int) count; }}Complexity
Time
O(n). The number of states is `n * 2 * 3`. Each state is computed only once, and each computation takes constant time.
Space
O(n). The space is dominated by the memoization table of size `n * 2 * 3`. The recursion stack depth also contributes O(n) space.
Trade-offs
Pros
Relatively intuitive to formulate, as it directly translates the problem's recursive structure.
Correctly solves the problem within the time limits.
Cons
Can cause a
StackOverflowErrorfor very largenif the recursion depth limit is exceeded.Slightly higher constant factor overhead compared to the iterative bottom-up approach due to function calls.
This approach uses bottom-up dynamic programming. Instead of starting from n and going down, we build the solution from the ground up. We compute the number of valid records for length 1, then use that to compute for length 2, and so on, up to n. The state is defined by (length, total_absences, consecutive_lates). A key observation is that to compute the states for length i, we only need the results from length i-1. This allows for a significant space optimization, reducing the space complexity from O(n) to O(1).
Algorithm
- Define a DP table
dp[i][j][k]to store the number of valid attendance records of lengthi, with a total ofjabsences, and ending withkconsecutive lates. - The dimensions of the state are:
i: length of the record (from 0 ton).j: total absences (0 or 1).k: consecutive lates at the end (0, 1, or 2).
- Initialization: Set
dp[0][0][0] = 1, representing a single empty string of length 0 with no absences or lates. All other initial DP values are 0. - Iteration: Loop from
i = 1ton. In each iteration, calculate the values fordp[i]based on the values fromdp[i-1]. - Transitions: For each state
(i-1, a, l), consider appending 'P', 'A', or 'L':- Append 'P': A record of length
i-1withaabsences andllates becomes a record of lengthiwithaabsences and 0 lates. Adddp[i-1][a][l]todp[i][a][0]. - Append 'A': If
a < 1, this is a valid move. The new record has lengthi,a+1absences, and 0 lates. Adddp[i-1][a][l]todp[i][a+1][0]. - Append 'L': If
l < 2, this is a valid move. The new record has lengthi,aabsences, andl+1lates. Adddp[i-1][a][l]todp[i][a][l+1].
- Append 'P': A record of length
- Space Optimization: Notice that
dp[i]only depends ondp[i-1]. We can optimize space to O(1) by using only two 2D arrays, one for the previous state (dp_prev) and one for the current state (dp_curr). After each iterationi,dp_previs updated todp_curr. - Final Result: After the loop finishes, the total number of valid records of length
nis the sum of all values indp[n](or the finaldp_currarray in the optimized version).
Walkthrough
We maintain a DP table that tracks the counts of valid sequences. A full DP table would be dp[n+1][2][3], but we can optimize it to just dp[2][3] since we only need the previous day's counts to calculate the current day's counts.
We initialize the state for a 0-length string: dp[0][0] = 1 (one way, the empty string). Then, we iterate from day 1 to n. In each iteration, we compute a new DP table next_dp based on the current dp table. For each state (absences, lates) in the current dp table, we see how adding 'P', 'A', or 'L' transitions it to a new state in next_dp. After calculating all transitions for the day, we replace the dp table with next_dp and proceed to the next day. Finally, we sum up all the counts in the final dp table to get the total number of valid records.
class Solution { public int checkRecord(int n) { int MOD = 1_000_000_007; // dp[absences][consecutive_lates] long[][] dp = new long[2][3]; dp[0][0] = 1; // Base case: one empty string for (int i = 0; i < n; i++) { long[][] nextDp = new long[2][3]; for (int a = 0; a < 2; a++) { for (int l = 0; l < 3; l++) { if (dp[a][l] == 0) continue; // Add 'P' nextDp[a][0] = (nextDp[a][0] + dp[a][l]) % MOD; // Add 'A' if (a + 1 < 2) { nextDp[a + 1][0] = (nextDp[a + 1][0] + dp[a][l]) % MOD; } // Add 'L' if (l + 1 < 3) { nextDp[a][l + 1] = (nextDp[a][l + 1] + dp[a][l]) % MOD; } } } dp = nextDp; } long total = 0; for (int a = 0; a < 2; a++) { for (int l = 0; l < 3; l++) { total = (total + dp[a][l]) % MOD; } } return (int) total; }}Complexity
Time
O(n). We iterate `n` times, and inside the loop, we perform a constant number of operations (iterating over the `2 * 3` states).
Space
O(1). We only need to store the DP states for the current and next day. The size of the DP table is `2 * 3`, which is constant.
Trade-offs
Pros
Highly efficient in terms of space (O(1)).
Avoids recursion, thus preventing potential stack overflow issues.
Generally faster than the memoized recursion due to lower overhead.
Cons
The logic for transitions might be slightly less intuitive to formulate compared to the recursive approach for some developers.
This approach leverages the fact that the DP transitions form a system of linear recurrence relations. Such a system can be represented by a matrix transformation. We can define a state vector that holds the counts for all possible combinations of (absences, lates), and a transition matrix that describes how these counts change from one day to the next. To find the counts for day n, we can raise this transition matrix to the power of n and apply it to the initial state vector. The matrix power can be calculated very efficiently using binary exponentiation, leading to a logarithmic time complexity.
Algorithm
- Represent State as a Vector: The DP state
(total_absences, consecutive_lates)can be flattened into a single state vector. There are2 * 3 = 6possible states. Let's map them:- State 0: (A=0, L=0)
- State 1: (A=0, L=1)
- State 2: (A=0, L=2)
- State 3: (A=1, L=0)
- State 4: (A=1, L=1)
- State 5: (A=1, L=2)
Let
S_ibe a column vector whereS_i[j]is the count of records of lengthiending in statej.
- Formulate Transition Matrix: The DP transitions are linear. We can find a 6x6 matrix
Tthat transforms the state vector from dayito dayi+1:S_{i+1} = T * S_i. - Derive the Matrix: The entry
T[j][k]is 1 if a record in statekcan transition to statejby adding one character, and 0 otherwise. For example, adding 'P' to states 0, 1, or 2 (A=0) results in state 0 (A=0, L=0). So,T[0][0],T[0][1], andT[0][2]are 1. The full matrix is:[[1, 1, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0]] - Use Matrix Exponentiation: The state vector for day
nisS_n = T^n * S_0. The initial state vectorS_0(for a 0-length string) is[1, 0, 0, 0, 0, 0]^T. - We can compute
T^nefficiently using the binary exponentiation (or exponentiation by squaring) algorithm in O(k^3 log n) time, wherek=6is the matrix dimension. - Calculate Final Result: After computing
T^n, the final state vectorS_nis simply the first column ofT^n(sinceS_0has a 1 only in the first position). The total number of valid records is the sum of all elements inS_n.
Walkthrough
The problem can be modeled as finding the number of paths of length n in a state graph. The nodes of the graph are the 6 possible states (absences, lates), and the edges represent the transitions ('P', 'A', 'L'). The number of paths of length n from a starting node can be found by taking the n-th power of the graph's adjacency matrix.
Our transition matrix T acts as this adjacency matrix. We start with a single valid record of length 0 (the empty string), which corresponds to the state (A=0, L=0). Our initial state vector S_0 is [1, 0, 0, 0, 0, 0]^T. The state vector after n days is S_n = T^n * S_0. We implement a matrixPower function that computes T^n in O(log n) time. The final answer is the sum of all elements in the resulting S_n vector.
class Solution { long MOD = 1_000_000_007; public int checkRecord(int n) { long[][] T = { {1, 1, 1, 0, 0, 0}, // P(A=0), L(A=0), LL(A=0) -> P(A=0) {1, 0, 0, 0, 0, 0}, // P(A=0) -> L(A=0) {0, 1, 0, 0, 0, 0}, // L(A=0) -> LL(A=0) {1, 1, 1, 1, 1, 1}, // Any state + A -> P(A=1); Any A=1 state + P -> P(A=1) {0, 0, 0, 1, 0, 0}, // P(A=1) -> L(A=1) {0, 0, 0, 0, 1, 0} // L(A=1) -> LL(A=1) }; if (n == 0) return 1; long[][] Tn = matrixPower(T, n); // S_n = Tn * S_0, where S_0 = [1, 0, 0, 0, 0, 0]^T // The result is the sum of all entries in the first column of Tn long result = 0; for(int i = 0; i < 6; i++) { result = (result + Tn[i][0]) % MOD; } return (int) result; } private long[][] matrixPower(long[][] base, int exp) { long[][] result = new long[6][6]; for (int i = 0; i < 6; i++) result[i][i] = 1; // Identity matrix while (exp > 0) { if (exp % 2 == 1) result = multiply(result, base); base = multiply(base, base); exp /= 2; } return result; } private long[][] multiply(long[][] A, long[][] B) { long[][] C = new long[6][6]; for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { for (int k = 0; k < 6; k++) { C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; }}Complexity
Time
O(log n). The time is dominated by the matrix exponentiation algorithm, which performs O(log n) matrix multiplications. Each multiplication of two 6x6 matrices takes constant time (6^3 operations).
Space
O(1). The space required is for a few constant-size (6x6) matrices, regardless of the value of `n`.
Trade-offs
Pros
Asymptotically the fastest approach, especially for very large
n.Constant space complexity.
Cons
Significantly more complex to conceptualize and implement compared to standard DP approaches.
The constant factor from matrix multiplication (
k^3) can make it slower than the O(n) DP for smaller values ofn.
Solutions
Solution
class Solution {private static final int MOD = 1000000007;public int checkRecord(int n) { long[][][] dp = new long[n][2][3];constexpr int MOD = 1e9 + 7 ; class Solution { public: int checkRecord ( int n ) { using ll = long long ; vector < vector < vector < ll >>> dp ( n , vector < vector < ll >> ( 2 , vector < ll > ( 3 ))); // base case dp [ 0 ][ 0 ][ 0 ] = dp [ 0 ][ 0 ][ 1 ] = dp [ 0 ][ 1 ][ 0 ] = 1 ; for ( int i = 1 ; i < n ; ++ i ) { // A dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % MOD ; // L dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ]; dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ]; dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ]; dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ]; // P dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % MOD ; dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ]) % MOD ; } ll ans = 0 ; for ( int j = 0 ; j < 2 ; ++ j ) { for ( int k = 0 ; k < 3 ; ++ k ) { ans = ( ans + dp [ n - 1 ][ j ][ k ]) % MOD ; } } return ans ; } };class Solution: # base case dp [ 0 ][ 0 ][ 0 ] = dp [ 0 ][ 0 ][ 1 ] = dp [ 0 ][ 1 ][ 0 ] = 1 for i in range ( 1 , n ): # A dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % mod # L dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ] dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ] dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ] dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ] # P dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % mod dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ] ) % mod ans = 0 for j in range ( 2 ): for k in range ( 3 ): ans = ( ans + dp [ n - 1 ][ j ][ k ]) % mod return ans def checkRecord(self, n: int) -> int: mod = int(1e9 + 7) dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n)]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.