You are given an integer n representing the number of sheets.
You are also given an integer array limit of size m, where limit[i] is the maximum number of sheets that can be painted using color i.
You must paint all n sheets under the following conditions:
i cannot exceed limit[i].Return an integer denoting the number of distinct ways to paint all sheets. Since the answer may be large, return it modulo 109 + 7.
Note: Two ways differ if at least one sheet is painted with a different color.
Example 1:
Input: n = 4, limit = [3,1,2]
Output: 6
Explanation:
For each ordered pair(i, j), where color i is used for the first segment and color j for the second segment (i != j), a split of x and 4 - x is valid if 1 <= x <= limit[i] and 1 <= 4 - x <= limit[j].
Valid pairs and counts are:
(0, 1): x = 3(0, 2): x = 2, 3(1, 0): x = 1(2, 0): x = 1, 2Therefore, there are 6 valid ways in total.
Example 2:
Input: n = 3, limit = [1,2]
Output: 2
Explanation:
For each ordered pair (i, j), where color i is used for the first segment and color j for the second segment (i != j), a split of x and 3 - x is valid if 1 <= x <= limit[i] and 1 <= 3 - x <= limit[j].
Valid pairs and counts are:
(0, 1): x = 1(1, 0): x = 2Hence, there are 2 valid ways in total.
Example 3:
Input: n = 3, limit = [2,2]
Output: 4
Explanation:
For each ordered pair (i, j), where color i is used for the first segment and color j for the second segment (i != j), a split of x and 3 - x is valid if 1 <= x <= limit[i] and 1 <= 3 - x <= limit[j].
Valid pairs and counts are:
(0, 1): x = 1, 2(1, 0): x = 1, 2Therefore, there are 4 valid ways in total.
Constraints:
2 <= n <= 1092 <= m == limit.length <= 1051 <= limit[i] <= 109Problem Overview: You are given several sheets that must be painted using a set of colors while respecting specific adjacency or placement constraints. The goal is to compute how many valid painting configurations exist. Because the number of combinations grows quickly, the result is typically calculated using modular arithmetic.
Approach 1: Brute Force Enumeration (Exponential Time, Exponential Space)
The most direct strategy generates every possible color assignment for the sheets and checks whether it satisfies the constraints. This means recursively assigning a color to each sheet and validating the configuration at the end. If there are k colors and n sheets, the search space becomes k^n. Time complexity is O(k^n) with recursion depth O(n) space. This approach works only for very small inputs but helps illustrate the structure of the problem before optimization.
Approach 2: Dynamic Programming by Position (O(n * k) time, O(n * k) space)
Instead of recomputing configurations repeatedly, track the number of valid ways to paint up to sheet i using a particular color. The DP state dp[i][c] represents the number of ways where sheet i is painted with color c. Transitions depend on the constraint rules (for example, preventing the same color on adjacent sheets). For each sheet, iterate through all colors and accumulate valid transitions from the previous sheet. This converts the exponential search into polynomial time using ideas common in dynamic programming.
Approach 3: Optimized DP / Combinatorial Counting (O(n) time, O(1) space)
Observing the transition pattern reveals that many DP states share identical behavior. Instead of storing values for every color, track aggregated states such as "same pattern" vs "different pattern" or "previous color reused" vs "new color chosen". Each step updates these counts using simple arithmetic and multiplies by the number of available colors. This compresses the DP table into a few running variables. Time complexity becomes O(n) with O(1) space while still applying modular arithmetic to avoid overflow. The technique resembles state compression used in combinatorics and DP transitions.
Recommended for interviews: Start by describing the brute force recursion to demonstrate understanding of the combinatorial search space. Then move to the dynamic programming formulation that tracks valid states per sheet. Interviewers typically expect the optimized DP or mathematical recurrence because it reduces both memory usage and runtime while keeping the logic clear.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(k^n) | O(n) | Only for very small inputs or to reason about constraints |
| Dynamic Programming Table | O(n * k) | O(n * k) | General solution when tracking transitions between colors |
| Optimized DP / State Compression | O(n) | O(1) | Preferred interview solution when recurrence can be simplified |
Practice Number of Ways to Paint Sheets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor