Student Attendance Record II

The problem is asking to find the number of possible attendance records of length n that make a student eligible for an attendance award. The constraints are that the student must be absent for fewer than 2 days total and must never be late for 3 or more consecutive days.

We can use dynamic programming to solve this problem by tracking the state of the last two days for absences and the last three days for lateness.

Here’s the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7

        # dp[i][j][k] represents the count of valid sequences of length i
        # where there are j absences and k trailing late days
        dp = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]

        # Base case: an empty string is a valid attendance record
        dp[0][0][0] = 1

        for i in range(n):
            for j in range(2):
                for k in range(3):
                    # Add a 'P': No change to the absence count, reset the late count
                    dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]) % MOD

                    # Add an 'A': Increase the absence count, reset the late count
                    if j < 1:
                        dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][k]) % MOD

                    # Add an 'L': No change to the absence count, increase the late count
                    if k < 2:
                        dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD

        # Sum all the valid sequences
        total_count = 0
        for j in range(2):
            for k in range(3):
                total_count = (total_count + dp[n][j][k]) % MOD

        return total_count

This code will calculate the number of possible attendance records that make a student eligible for an award, according to the specified rules, and return the result modulo (10^9 + 7).

10 Prerequisite LeetCode Problems

“552. Student Attendance Record II” is a dynamic programming problem that focuses on state transitions. Here are 10 problems to prepare:

70. Climbing Stairs: This problem introduces you to the fundamental concepts of dynamic programming.
198. House Robber: This is another basic dynamic programming problem that teaches you how to define and transition between states.
300. Longest Increasing Subsequence: This problem is a bit more complex and teaches you how to handle state transitions that are not adjacent.
509. Fibonacci Number: This problem introduces you to dynamic programming with a simpler recurrence relation.
746. Min Cost Climbing Stairs: This problem is another basic dynamic programming problem, but with a different type of state transition.
1143. Longest Common Subsequence: This problem will give you a better understanding of how to handle and manipulate 2D dynamic programming problems.
121. Best Time to Buy and Sell Stock: This problem involves dynamic programming with a slightly more complex state definition.
63. Unique Paths II: This problem requires a clear understanding of the state transition and how to handle obstacles.
646. Maximum Length of Pair Chain: This problem introduces the concept of dynamic programming with sorting, which is an important technique for solving some DP problems.
376. Wiggle Subsequence: This problem requires careful consideration of state definitions and transitions.

After solving these problems, you should have a better understanding of how to define states, transition between them, and handle more complex dynamic programming problems. This will prepare you to tackle “552. Student Attendance Record II”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import numpy as np

class Solution:
    def checkRecord(self, n: int) -> int:
        MODULUS = 10**9 + 7

        initial_counts = np.array(
            [1, 0, 0, 0, 0, 0], 
            dtype=np.int64
        )

        adjacency_matrix = np.array([
            [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],
        ], dtype=np.int64)

        def power(A, exp):
            B = np.identity(len(A), dtype=np.int64)
            for bit in reversed(bin(exp)[2:]):
                if bit == '1':
                    B = B @ A
                    B %= MODULUS
                A = A @ A
                A %= MODULUS
            return B

        final_counts = power(adjacency_matrix, n) @ initial_counts

        return sum(final_counts) % MODULUS

Problem Classification

Language Agnostic Coding Drills

Understanding import statements: Import statements allow you to use libraries, such as numpy in this case. Familiarize yourself with numpy’s features for numerical computing.
Defining constants: The constant MODULUS is defined to be used in calculations later on.
Using numpy arrays: The initial_counts and adjacency_matrix variables are initialized as numpy arrays. A numpy array is a grid of values, all of the same type, and is indexed by a tuple of nonnegative integers.
Matrix Operations: Familiarize yourself with operations on matrices using numpy, specifically multiplication with the ‘@’ operator. A key part of this code is the power function, which is using exponentiation by squaring to compute matrix powers efficiently.
Understanding binary numbers: The power function relies on understanding binary numbers. The binary representation of the exponent is used to efficiently compute the power of the matrix.
Modulo arithmetic: The ‘%’ operator is used to calculate the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation).
Object-Oriented Programming: The entire code is wrapped inside a class Solution and the function checkRecord which could be called on an instance of this class. Understand how classes work in Python, how to define methods and how to access them.

The final solution for the problem uses a combination of the above mentioned coding concepts. Each of these concepts can be practiced separately and then combined to form a solution similar to the Python code. Understanding each of these aspects in depth will allow you to write and understand complex Python programs efficiently.

To solve this problem, it models the different possibilities for attendance records as states in a Markov Chain, with the six states corresponding to:

No absences and no lates.
No absences and exactly one late.
No absences and at least two lates.
At least one absence and no lates.
At least one absence and exactly one late.
At least one absence and at least two lates.

The adjacency matrix is used to describe the transitions between these states, and matrix exponentiation is used to quickly calculate the number of possible attendance records of length n.

The function returns the total sum of all these possibilities, modulus 10**9 + 7 as the final result. This value is used for the modulus operation to prevent overflow of integer values and it’s a common practice in competitive programming problems.

Targeted Drills in Python

Understanding import statements
Python’s import statement allows us to use functions, classes, and variables defined in another module. Here’s a simple drill for you:
Import the math module and use its sqrt() function to calculate the square root of a number.
1 2 3 4 5
import math num = 25 root = math.sqrt(num) print(root)
Defining constants
Python doesn’t have built-in constant types, but by convention, we use all capital letters to define a constant.
Define a constant PI and use it to calculate the area of a circle with a given radius.
1 2 3 4 5
PI = 3.14159 radius = 5 area = PI * radius ** 2 print(area)
Using numpy arrays
NumPy arrays are a fundamental structure for scientific computing with Python. Here’s a simple drill:
Create a numpy array of integers from 1 to 5 and print it.
1 2 3 4
import numpy as np arr = np.array([1, 2, 3, 4, 5]) print(arr)

Matrix Operations

NumPy supports various matrix operations. Let’s do a simple multiplication:

Create two 2x2 matrices and multiply them.

1
2
3
4
5
6
import numpy as np

A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
product = np.dot(A, B)
print(product)

Understanding binary numbers
Python provides built-in functions to work with binary numbers.
Convert an integer to binary and print it.
1 2 3
num = 10 binary = bin(num) print(binary)
Modulo arithmetic
Modulo operation finds the remainder after division of one number by another.
Perform a modulo operation of 10 divided by 3.
1 2
result = 10 % 3 print(result)

Object-Oriented Programming

Python is an object-oriented programming language. You can define classes, create objects, and more.

Define a simple class Rectangle with a constructor that accepts length and width. Add a method area that calculates the area of the rectangle.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Rectangle:
    def __init__(self, length, width):
        self.length = length
        self.width = width

    def area(self):
        return self.length * self.width

rect = Rectangle(5, 4)
print(rect.area())

These drills can be combined and expanded to solve more complex problems, including the one in the code example. By practicing these drills, you can build a strong foundation in Python programming and problem-solving.