Skip to main content
Talentd

Number of Ways to Paint Sheets - Solution & Explanation

HardPremiumFree on FleetCode4 min read
Practice this problem

Problem Statement

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:

  • Exactly two distinct colors are used.
  • Each color must cover a single contiguous segment of sheets.
  • The number of sheets painted with color 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, 2

Therefore, 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 = 2

Hence, 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, 2

Therefore, there are 4 valid ways in total.

 

Constraints:

  • 2 <= n <= 109
  • 2 <= m == limit.length <= 105
  • 1 <= limit[i] <= 109

Approach Overview

Problem 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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(k^n)O(n)Only for very small inputs or to reason about constraints
Dynamic Programming TableO(n * k)O(n * k)General solution when tracking transitions between colors
Optimized DP / State CompressionO(n)O(1)Preferred interview solution when recurrence can be simplified

Frequently Asked Questions

Is Number of Ways to Paint Sheets easy or hard?
Number of Ways to Paint Sheets is classified as a Hard problem because it requires identifying the correct DP states and deriving the recurrence. Once the pattern is recognized, the final implementation becomes concise with O(n) time and constant space.
Number of Ways to Paint Sheets Python/Java solution
The solution can be implemented in Python, Java, C++, or Go using dynamic programming. Maintain counters representing valid states for the previous sheet and update them iteratively. Each update applies the recurrence and modulo operation to keep numbers within range.
How to solve Number of Ways to Paint Sheets in O(n)?
Define recurrence relations that represent how many valid colorings end in certain patterns. Instead of storing a full DP table, keep a few counters describing valid configurations up to the previous sheet. Update those counters for each new sheet using the allowed color transitions, applying modulo arithmetic when necessary.
What is the best approach for Number of Ways to Paint Sheets?
The best approach uses dynamic programming with state compression. Instead of tracking every color choice for every sheet, maintain aggregated states representing valid transitions between sheets. This reduces the runtime to O(n) with constant space while still counting all valid configurations using modular arithmetic.
Is Number of Ways to Paint Sheets asked at Google/Amazon/Meta?
Problems involving counting valid painting configurations commonly appear in interviews at companies like Google, Amazon, and Meta. They test dynamic programming skills, recurrence derivation, and the ability to optimize combinatorial counting problems.
What data structure is used in Number of Ways to Paint Sheets?
The main technique relies on dynamic programming arrays or a few running variables for state compression. No complex data structures are required; the focus is on recurrence relations and efficient counting using arithmetic operations.
What is the time complexity of Number of Ways to Paint Sheets?
The optimized dynamic programming solution runs in O(n) time where n is the number of sheets. Each step updates a small set of state variables derived from the previous sheet. Space complexity can be reduced to O(1) because only the previous state is required.

Ready to solve this problem?

Practice Number of Ways to Paint Sheets with our built-in code editor and test cases.

Practice on FleetCode