Student Attendance Record II solution and explanation
Google
9 more videos on this problem
Student Attendance Record II - Leetcode 552 - PythonNeetCodeIO · 27:10 · 11K views
Student Attendance Record II | Recursion | Memoization | Bottom Up | Leetcode 552 | codestorywithMIKcodestorywithMIK · 40:54 · 8K views
Student Attendance Record II: Leetcode 552Tony Teaches · 19:55 · 7K views
552. Student Attendance Record II | Top-Down DP | Bottom Up Optimized DPAryan Mittal · 21:25 · 4K views
[English] LeetCode 552. Student Attendance Record IIhappygirlzt · 11:18 · 3K views
552. Student Attendance Record II (Leetcode Hard)Programming Live with Larry · 34:29 · 1K views
Daily Leetcode #1517: May 26, 2024 - 552. Student Attendance Record IIProgramming Live with Larry · 11:35 · 1K views
Leetcode 552 Student Attendance Record II (Java)TheAnalyticGuy · 17:45 · 1K views
Leet Code 552 | Student Attendance Record II | Detailed Explanation & Solution | LVS LogicsLVS Logics · 18:21 · 472 views
Student Attendance Record II (LeetCode 552) (Hard) (DP)CodeWithARB · 25:18 · 416 views
The problem
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: 3
Example 3:
Input: n = 10101 Output: 183236316
Constraints:
1 <= n <= 105
Approach overview
Problem Overview: Count the number of valid attendance strings of length n using characters 'A' (Absent), 'L' (Late), and 'P' (Present). A record is valid if it contains fewer than two 'A' characters and never has three consecutive 'L'. Return the total count modulo 1e9+7.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
Model the constraints directly with DP states. Track three pieces of information while building the string: the current length i, how many absences have been used (0 or 1), and the number of trailing 'L' characters (0–2). For each state, append 'P', 'A', or 'L' if the constraints allow it. The transitions update the absence count and reset or extend the late streak. This produces at most n * 2 * 3 states, so the runtime is O(n) with O(n) memory (or O(1) using rolling arrays). This approach clearly expresses the constraints and is the most common solution using dynamic programming.
Approach 2: Mathematical Matrix Exponentiation (O(log n) time, O(1) space)
The DP transitions form a linear recurrence between states. Instead of iterating day by day, represent the transitions between the six possible states (A ∈ {0,1} and L ∈ {0,1,2}) as a transition matrix. Multiplying this matrix advances the state by one day. Raising the matrix to the power n using fast exponentiation computes the result in O(log n) time. This converts the iterative DP into a mathematical recurrence solved with matrix exponentiation. Space stays O(1) because the matrix size is constant.
Recommended for interviews: The dynamic programming solution is what most interviewers expect. It demonstrates that you can translate constraints into states and transitions. The matrix exponentiation optimization is valuable for very large n and shows deeper knowledge of recurrence relations and DP optimization techniques.
Approach 1: Dynamic Programming Approach
This approach leverages dynamic programming to count eligible attendance records. We define a function dp[i][a][l], which represents the number of valid sequences of length i with a absences and l consecutive lates. The transitions will account for adding 'P', 'A', or 'L' to existing records, ensuring we respect the problem's constraints.
def checkRecord(n):
MOD = 10**9 + 7
dp = [[[0 for _ in range(3)] for _ in range(n + 1)] for _ in range(2)]
dp[0][0][0] = 1
for i in range(n):
for a in range(2):
for l in range(3):
dp[a][i + 1][0] = (dp[a][i + 1][0] + dp[a][i][l]) % MOD
if a == 0:
dp[1][i + 1][0] = (dp[1][i + 1][0] + dp[a][i][l]) % MOD
if l < 2:
dp[a][i + 1][l + 1] = (dp[a][i + 1][l + 1] + dp[a][i][l]) % MOD
return sum(dp[a][n][l] for a in range(2) for l in range(3)) % MOD
n = 2
print(checkRecord(n))public class AttendanceRecord {
public int checkRecord(int n) {
final int MOD = 1000000007;
int[][][] dp = new int[2][n][3];
dp[0][0][0] = 1;
for (int i = 0; i < n - 1; i++) {
for (int a = 0; a <= 1; a++) {
for (int l = 0; l < 3; l++) {
dp[a][i + 1][0] = (dp[a][i + 1][0] + dp[a][i][l]) % MOD;
if (a == 0) {
dp[1][i + 1][0] = (dp[1][i + 1][0] + dp[a][i][l]) % MOD;
}
if (l < 2) {
dp[a][i + 1][l + 1] = (dp[a][i + 1][l + 1] + dp[a][i][l]) % MOD;
}
}
}
}
int total = 0;
for (int a = 0; a <= 1; a++) {
for (int l = 0; l < 3; l++) {
total = (total + dp[a][n - 1][l]) % MOD;
}
}
return total;
}
public static void main(String[] args) {
AttendanceRecord ar = new AttendanceRecord();
int n = 2;
System.out.println(ar.checkRecord(n));
}
}#include <iostream>
#include <vector>
#define MOD 1000000007
int checkRecord(int n) {
std::vector<std::vector<std::vector<int>>> dp(2, std::vector<std::vector<int>>(n, std::vector<int>(3, 0)));
dp[0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int a = 0; a <= 1; a++) {
for (int l = 0; l < 3; l++) {
if (i < n - 1) {
dp[a][i + 1][0] = (dp[a][i + 1][0] + dp[a][i][l]) % MOD;
if (a == 0)
dp[1][i + 1][0] = (dp[1][i + 1][0] + dp[a][i][l]) % MOD;
if (l < 2)
dp[a][i + 1][l + 1] = (dp[a][i + 1][l + 1] + dp[a][i][l]) % MOD;
}
}
}
}
int res = 0;
for (int a = 0; a <= 1; a++) {
for (int l = 0; l < 3; l++) {
res = (res + dp[a][n - 1][l]) % MOD;
}
}
return res;
}
int main() {
int n = 2;
std::cout << checkRecord(n) << std::endl;
return 0;
}function checkRecord(n) {
const MOD = 1000000007;
let dp = Array.from({ length: 2 }, () =>
Array.from({ length: n + 1 }, () => Array(3).fill(0))
);
dp[0][0][0] = 1;
for (let i = 0; i < n; i++) {
for (let a = 0; a <= 1; a++) {
for (let l = 0; l < 3; l++) {
dp[a][i + 1][0] = (dp[a][i + 1][0] + dp[a][i][l]) % MOD;
if (a === 0) {
dp[1][i + 1][0] = (dp[1][i + 1][0] + dp[a][i][l]) % MOD;
}
if (l < 2) {
dp[a][i + 1][l + 1] = (dp[a][i + 1][l + 1] + dp[a][i][l]) % MOD;
}
}
}
}
let total = 0;
for (let a = 0; a <= 1; a++) {
for (let l = 0; l < 3; l++) {
total = (total + dp[a][n][l]) % MOD;
}
}
return total;
}
console.log(checkRecord(2));#include <stdio.h>
#define MOD 1000000007
int checkRecord(int n) {
int p_dp, a_dp, l_dp[3][3] = {{1}}, i, p_dpOld, a_dpOld;
p_dp = 1, a_dp = 0;
for (i = 1; i <= n; ++i) {
p_dpOld = p_dp;
a_dpOld = a_dp;
p_dp = ((p_dpOld + a_dpOld) % MOD + (l_dp[0][0] + l_dp[1][0] + l_dp[2][0]) % MOD) % MOD;
a_dp = (p_dpOld + (l_dp[0][1] + l_dp[1][1] + l_dp[2][1]) % MOD) % MOD;
l_dp[2][0] = l_dp[1][0]; l_dp[1][0] = l_dp[0][0]; l_dp[0][0] = p_dpOld;
l_dp[2][1] = l_dp[1][1]; l_dp[1][1] = l_dp[0][1]; l_dp[0][1] = a_dpOld;
}
return ((l_dp[0][0] + l_dp[1][0] + l_dp[2][0]) % MOD + (l_dp[0][1] + l_dp[1][1] + l_dp[2][1]) % MOD + a_dp + p_dp) % MOD;
}
int main() {
int n = 2;
printf("%d\n", checkRecord(n));
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
public int CheckRecord(int n) {
if (n == 0) return 0;
int[][][] dp = new int[2][][];
for (int i = 0; i < 2; i++) {
dp[i] = new int[n + 1][];
for (int j = 0; j <= n; j++) {
dp[i][j] = new int[3];
}
}
dp[0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int a = 0; a <= 1; a++) {
for (int l = 0; l < 3; l++) {
dp[a][i + 1][0] = (int)((dp[a][i + 1][0] + (long)dp[a][i][l]) % MOD);
if (a == 0) {
dp[1][i + 1][0] = (int)((dp[1][i + 1][0] + (long)dp[a][i][l]) % MOD);
}
if (l < 2) {
dp[a][i + 1][l + 1] = (int)((dp[a][i + 1][l + 1] + (long)dp[a][i][l]) % MOD);
}
}
}
}
int total = 0;
for (int a = 0; a <= 1; a++) {
for (int l = 0; l < 3; l++) {
total = (int)((total + (long)dp[a][n][l]) % MOD);
}
}
return total;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int n = 2;
Console.WriteLine(solution.CheckRecord(n));
}
}The Python implementation similarly utilizes dynamic programming, leveraging lists to maintain counts of state transitions dynamically updated for each sequence length up to n.
Time complexity: O(n), Space complexity: O(n), same as other solutions due to the space needed for the DP array.
Approach 2: Mathematical Matrix Exponentiation Approach
This approach uses matrix exponentiation to efficiently solve the problem by leveraging the recursive relationship of the transformation matrices, which model the state transitions of the sequences. The matrix exponentiation technique drastically reduces the time complexity by harnessing fast exponentiation properties.
def multiply(a, b, m):
return [[sum(x * y % m for x, y in zip(a_row, b_col)) % m for b_col in zip(*b)] for a_row in a]
MOD = 1000000007
F = [
[1, 1, 0, 1, 0, 0],
[1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1]
]
n = 2
def power(F, n, M):
size = len(F)
result = [[int(i == j) for j in range(size)] for i in range(size)]
while n:
if n % 2:
result = multiply(result, F, M)
F = multiply(F, F, M)
n //= 2
return result
def checkRecord(n):
if n == 1: return 3
result = power(F, n - 1, MOD)
return int(2 * result[0][0] + result[0][1] + result[0][3]) % MOD
print(checkRecord(2))public class AttendanceRecordMatrix {
static final int MOD = 1000000007;
static int[][] multiply(int[][] A, int[][] B) {
int[][] C = new int[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] = (int)((C[i][j] + (long)A[i][k] * B[k][j]) % MOD);
return C;
}
static int[][] power(int[][] F, int n) {
int[][] result = new int[6][6];
for (int i = 0; i < 6; ++i) {
result[i][i] = 1;
}
while (n > 0) {
if ((n & 1) == 1) result = multiply(result, F);
F = multiply(F, F);
n >>= 1;
}
return result;
}
public int checkRecord(int n) {
if (n == 1) return 3;
int[][] F = {
{1, 1, 0, 1, 0, 0},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 1}
};
int[][] result = power(F, n - 1);
return (2 * result[0][0] + result[0][1] + result[0][3]) % MOD;
}
public static void main(String[] args) {
AttendanceRecordMatrix ar = new AttendanceRecordMatrix();
int n = 2;
System.out.println(ar.checkRecord(n));
}
}#include <iostream>
#include <vector>
#define MOD 1000000007
typedef std::vector<std::vector<long long>> matrix;
matrix multiply(matrix A, matrix B) {
int size = A.size();
matrix C(size, std::vector<long long>(size));
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
for (int k = 0; k < size; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j] % MOD) % MOD;
return C;
}
matrix power(matrix A, int n) {
int size = A.size();
matrix result(size, std::vector<long long>(size));
for (int i = 0; i < size; i++) result[i][i] = 1;
while (n > 0) {
if (n % 2 == 1) result = multiply(result, A);
A = multiply(A, A);
n /= 2;
}
return result;
}
int checkRecord(int n) {
if (n == 1) return 3;
matrix F = { {1, 1, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1} };
matrix result = power(F, n - 1);
return (2 * result[0][0] + result[0][1] + result[0][3]) % MOD;
}
int main() {
int n = 2;
std::cout << checkRecord(n) << std::endl;
return 0;
}const MOD = 1000000007;
function multiply(A, B) {
let size = A.length;
let C = Array.from({ length: size }, () => Array(size).fill(0));
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
for (let k = 0; k < size; k++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j] % MOD) % MOD;
}
}
}
return C;
}
function power(F, n) {
let size = F.length;
let result = Array.from({ length: size }, (_, i) => Array.from({ length: size }, (_, j) => (i === j ? 1 : 0)));
while (n > 0) {
if (n % 2 === 1) result = multiply(result, F);
F = multiply(F, F);
n = Math.floor(n / 2);
}
return result;
}
function checkRecord(n) {
if (n === 1) return 3;
let F = [
[1, 1, 0, 1, 0, 0],
[1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1]
];
let result = power(F, n - 1);
return (2 * result[0][0] + result[0][1] + result[0][3]) % MOD;
}
console.log(checkRecord(2));#include <stdio.h>
#define MOD 1000000007
void multiply(int F[6][6], int M[6][6]) {
int x[6][6];
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
x[i][j] = 0;
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
for (int k = 0; k < 6; k++)
x[i][j] = (x[i][j] + (long long)F[i][k] * M[k][j]) % MOD;
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
F[i][j] = x[i][j];
}
void power(int F[6][6], int n) {
int M[6][6] = {{1, 1, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1}};
if (n <= 1)
return;
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
int checkRecord(int n) {
if(n == 1) return 3;
int F[6][6] = {{1, 1, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1}};
power(F, n - 1);
return (int)(((long long)F[0][0] * 2 + F[0][1] + F[0][3]) % MOD);
}
int main() {
int n = 2;
printf("%d\n", checkRecord(n));
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
private static int[][] Multiply(int[][] A, int[][] B) {
int size = A.Length;
var C = new int[size][];
for (int i = 0; i < size; ++i) {
C[i] = new int[size];
for (int j = 0; j < size; ++j) {
for (int k = 0; k < size; ++k) {
C[i][j] = (int)((C[i][j] + (long)A[i][k] * B[k][j]) % MOD);
}
}
}
return C;
}
private static int[][] Power(int[][] F, int n) {
int size = F.Length;
int[][] result = new int[size][];
for (int i = 0; i < size; i++) {
result[i] = new int[size];
result[i][i] = 1;
}
while (n > 0) {
if ((n & 1) == 1) result = Multiply(result, F);
F = Multiply(F, F);
n >>= 1;
}
return result;
}
public int CheckRecord(int n) {
if (n == 1) return 3;
int[][] F = {
new int[] {1, 1, 0, 1, 0, 0},
new int[] {1, 0, 1, 0, 0, 0},
new int[] {0, 1, 0, 0, 0, 0},
new int[] {0, 0, 0, 1, 1, 0},
new int[] {0, 0, 0, 0, 1, 1},
new int[] {0, 0, 0, 0, 0, 1}
};
var result = Power(F, n - 1);
return (int)((2 * result[0][0] + result[0][1] + result[0][3]) % MOD);
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.CheckRecord(2));
}
}This Python code uses functions for matrix multiplication and exponentiation in order to model the problem's constraints and efficiently calculate the total valid sequences.
Time complexity: O(log n), Space complexity: O(1), because matrix sizes remain constant.
Approach 3: Default Approach
func checkRecord(n int) int {
f := make([][][]int, n)
for i := range f {
f[i] = make([][]int, 2)
for j := range f[i] {
f[i][j] = make([]int, 3)
for k := range f[i][j] {
f[i][j][k] = -1
}
}
}
const mod = 1e9 + 7
var dfs func(i, j, k int) int
dfs = func(i, j, k int) int {
if i >= n {
return 1
}
if f[i][j][k] != -1 {
return f[i][j][k]
}
ans := dfs(i+1, j, 0)
if j == 0 {
ans = (ans + dfs(i+1, j+1, 0)) % mod
}
if k < 2 {
ans = (ans + dfs(i+1, j, k+1)) % mod
}
f[i][j][k] = ans
return ans
}
return dfs(0, 0, 0)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time complexity: O(n), Space complexity: O(n), same as other solutions due to the space needed for the DP array. |
| Mathematical Matrix Exponentiation Approach | Time complexity: O(log n), Space complexity: O(1), because matrix sizes remain constant. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (State Tracking) | O(n) | O(n) or O(1) | Best general solution. Easy to reason about constraints and typical interview expectation. |
| Matrix Exponentiation | O(log n) | O(1) | Useful when n is extremely large or when optimizing DP recurrences with fixed states. |
Frequently asked questions
Is Student Attendance Record II easy or hard?
LeetCode classifies this problem as Hard because it requires modeling multiple constraints simultaneously. The difficulty comes from defining correct DP states and transitions, and recognizing that the recurrence can also be optimized using matrix exponentiation.
Student Attendance Record II Python/Java solution
Python and Java implementations typically use a 3D DP state: day index, absence count (0 or 1), and consecutive L count (0–2). Each iteration updates the states using modular arithmetic with 1e9+7. The same logic translates directly across Python, Java, C++, and other languages.
How to solve Student Attendance Record II in O(n)?
Use DP with states representing (absences used, consecutive L count). For each position, append 'P', 'A', or 'L' if valid. 'P' resets the late streak, 'A' increments absence count if it is still zero, and 'L' increases the late streak up to two. Summing all valid states after n steps gives the answer.
What is the best approach for Student Attendance Record II?
Dynamic Programming with state tracking is the most practical solution. Track the number of absences used (0 or 1) and the number of trailing L characters (0–2) while iterating through the days. This creates only six states per day, giving O(n) time complexity and O(1) or O(n) space.
Is Student Attendance Record II asked at Google/Amazon/Meta?
Variants of constrained sequence counting and DP state transition problems appear in interviews at companies like Google, Amazon, and Meta. This problem tests dynamic programming modeling, state compression, and sometimes mathematical optimization using matrix exponentiation.
What data structure is used in Student Attendance Record II?
The core structure is a dynamic programming table or a few rolling arrays representing the six possible states. In the optimized solution, a fixed-size matrix is used to represent state transitions for fast exponentiation.
What is the time complexity of Student Attendance Record II?
The standard dynamic programming solution runs in O(n) time because each day updates a constant number of states (six). A matrix exponentiation optimization reduces the complexity to O(log n) by exponentiating a fixed transition matrix.