2742. Painting the Walls - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given two 0-indexed arrays, cost and time, each of length n, representing n different walls. There are two painters available to paint the walls:

Paid painter: Can paint the i-th wall in time[i] units of time, and charges cost[i] money.
Free painter: Can paint any wall in 1 unit of time for free, but can only work when the paid painter is already busy painting . In other words, the free painter can only paint concurrently while the paid painter is working; if the paid painter is not occupied, the free painter cannot paint.

The task is to paint all n walls with the minimum total cost. You can choose for each wall whether to hire the paid painter or let the free painter handle it (subject to the above concurrency rule).

Goal: Return the minimum amount of money required to paint all n walls.

Examples

Example 1:

Input: cost = [1, 2, 3, 2], time = [1, 2, 3, 2]
Output: 3
Explanation: We can paint walls at index 0 and 1 using the paid painter (costs 1 and 2, respectively). The paid painter spends 1 + 2 = 3 units of time on these two walls. While the paid painter is busy, the free painter can paint walls 2 and 3 (each in 1 unit of time) concurrently at no cost . All walls are finished in 3 time units, and the total cost is 1 + 2 = 3.

Example 2:

Input: cost = [2, 3, 4, 2], time = [1, 1, 1, 1]
Output: 4
Explanation: One optimal strategy is to hire the paid painter for walls at index 0 and 3 (costs 2 and 2). The paid painter will take 1 + 1 = 2 units of time to paint these walls; meanwhile, the free painter can paint walls 1 and 2 in those 2 time units (1 unit each) for free . Total cost = 2 + 2 = 4.

Example 3: (Edge-case scenario)

Input: cost = [10, 1, 1, 1], time = [10, 1, 1, 1]
Output: 2
Explanation: Here the first wall has a large time (10) but also a high cost (10). It turns out to be cheaper to pay the painters for two of the smaller walls instead. For instance, hire the paid painter for walls 1 and 2 (cost 1 + 1 = 2, taking 1 + 1 = 2 units of time). While the paid painter is busy for those 2 time units, the free painter can paint wall 0 (which would have cost 10 if paid) and wall 3 for free. This way, all 4 walls get painted in 2 time units, and the total cost is only 2.

Constraints

1 <= n <= 500 (number of walls)
cost.length == time.length == n
1 <= cost[i] <= 10^6 for each i
1 <= time[i] <= 500 for each i

(n = length of the arrays.)

Under these constraints, an efficient solution is needed (n can be up to 500, which is too large for brute force $2^n$ ). The problem is categorized as Hard, indicating that a straightforward greedy strategy might not work in all cases. We’ll need to carefully reason about the dynamic programming solution to efficiently explore the choices.

Hints

Think about the concurrency condition: The free painter can only work when the paid painter is busy. This means the number of walls painted for free cannot exceed the total time the paid painter spends working. Formally, if you hire the paid painter for k walls (with total painting time T), at most T other walls can be painted by the free painter during those T time units. Equivalently, if you end up paying for k walls, you must have T (total paid time) ≥ (n - k) to allow the free painter to cover the rest. Keep this condition in mind when deciding which walls to pay for.
Greedy choices can be tricky: It might be tempting to always pay for the wall that takes the longest time (to maximize free painter working time) or the cheapest wall, but neither strategy alone guarantees the optimal result. For example, in Example 3 above, paying for the longest-time wall (time=10) is not optimal because its cost is too high; it was cheaper to pay for two shorter walls instead. This hints that we need to consider combinations of choices rather than a simple greedy rule.
Dynamic Programming approach: Try to formulate the problem as a DP. Consider making a decision for each wall: either hire the paid painter for it or let it be painted for free. If you choose free for a wall, you then must have a paid painter working simultaneously – perhaps on another wall. This suggests a recursive structure where each decision affects how much “free painting time” is available for other walls. Think about a state that captures how many walls are left and how much concurrent time is available (or needed). This will lead to a recursion that you can memoize.

Approach Breakdown

We will discuss several approaches to solve the problem, from brute force to optimized dynamic programming, highlighting the thought process and trade-offs at each step.

Brute Force Approach (Exhaustive Search)

Idea: The most straightforward (but inefficient) approach is to try all possible ways to assign each wall to either the paid or free painter, then check which assignments are valid and what their costs are. In other words, consider every subset of walls to paint with the paid painter, and let the rest be painted free, then pick the subset that yields a valid schedule with minimum cost.

How to generate assignments: We have n walls, each can be either:

Paid (we incur its cost and add its painting time to the schedule), or
Free (no cost, but requires the paid painter to be busy at the same time).

This is a binary choice per wall, so there are $2^n$ possible assignments overall (which is huge for n=500). However, many assignments will be invalid because they violate the concurrency rule (too many free walls without enough paid time to cover them).

Validating an assignment: Given a set of walls chosen to be painted by the paid painter, how do we check if the free painter can cover the rest? We can sum up the time of all paid-painted walls (let’s call this T_paid) and count the number of free-painted walls (call this N_free). The assignment is valid if and only if T_paid ≥ N_free . This condition ensures the free painter has enough total time to paint N_free walls while the paid painter is working. If the condition holds, the total cost of that assignment is the sum of cost for the paid walls (free walls contribute 0 cost). We want the minimum cost among all valid assignments.

Example (small n): Suppose cost = [3, 5] and time = [1, 1] (2 walls). The possible assignments:

Paid none (all free): invalid, because if no paid painter is working, free painter cannot paint any wall.
Paid wall0 only, free wall1: Paid time = 1, free walls = 1 ⇒ valid (1 ≥ 1). Cost = 3.
Paid wall1 only, free wall0: Paid time = 1, free walls = 1 ⇒ valid (1 ≥ 1). Cost = 5.
Paid both walls: Paid time = 1+1=2, free walls = 0 ⇒ valid. Cost = 3+5 = 8. Among valid schedules, the cheapest cost is 3 (paint wall0 with paid painter, wall1 with free painter). This matches the condition that we needed at least 1 paid wall (with time 1) to cover the other wall for free.

Inefficiency: Exhaustively checking all subsets is exponential ( $2^n$ combinations). Even with pruning invalid cases early, the worst-case scenario is far beyond feasible for n up to 500. This brute force approach only works for very small n (perhaps n ≤ 20). We need a more clever method.

Recursive backtracking approach: To conceptualize brute force, we can also think of it as a recursion that tries to assign each wall one by one:

Recurse on wall index i with two branches:
- Paid: include cost[i] in cost sum and add time[i] to a running paid-time total.
- Free: no cost added, but this wall will require 1 unit of concurrent free time.
Ensure at each step that the number of free-painted walls so far does not exceed the paid time accumulated so far (a partial validity check). This can prune some branches early.
In the end, check if all walls are assigned and the final schedule is valid, track the min cost.

This recursion still explores an exponential state-space in the worst case, but it helps in framing the subproblem for DP optimization next.

Brute Force Complexity: ~O( $2^n$ ) time in the worst case (exponential) and O(n) space for recursion stack. This is not usable for n=500, but it sets the stage for optimization by noticing overlapping subproblems.

Brute Force Example Trace (small n):
Imagine n=3 for a brute force trace, cost=[2,1,3], time=[1,1,2]. A possible recursion tree:

                start (i=0, paid_time=0, free_count=0, cost=0)
               /                                    \
    Pay wall0 (paid_time=1, cost=2)       Free wall0 (free_count=1, cost=0)
          /              \                   /                \
  (i=1) Pay wall1   (i=1) Free wall1   (i=1) Pay wall1    (i=1) Free wall1
        ...            ...                  ...               ...

Each path continues until i = 3 (all walls assigned). Many paths will be invalid (for example, if we tried Free wall0 and Free wall1, we would have free_count=2 while paid_time=0, which is invalid early). By systematically exploring and pruning, we find the minimum cost valid path.

Brute Force Implementation (for conceptual understanding only):

Python3

. . . .

Note: This brute-force search is not efficient for large n and is shown for illustrative purposes. We need to introduce DP to cut down the repeated work.

Memoization (Top-Down DP)

Idea: The brute force approach has overlapping subproblems. We can define a recursive state that captures the essential information needed as we assign walls, and cache (memoize) the results of subproblems to avoid re-computation.

One way to define the state:

i = current wall index we are considering (0 to n).
j = a measure of how much "free painting time" is available or needed at this point.

We need to quantify the balance between paid time and free tasks as a state. There are a couple of ways to do this:

We could track paid_time and free_count separately, but that leads to two parameters. Instead, we can combine them into a single parameter that represents the difference or balance between the two.
Define j = (paid time accumulated so far) – (free tasks assigned so far). This j can be thought of as the remaining concurrent time available for free painter up to this point. It can be positive (meaning we have more paid time than free tasks so far, so we have spare capacity for free painter) or negative (meaning we have assigned more free tasks than we currently have time for — which is a temporary situation that will require future paid tasks to fix).

With this interpretation:

j (free time balance) increases when we assign a wall to the paid painter (because we gain time[i] units of paid work time during which the free painter could operate, increasing available free painting capacity).
j decreases when we assign a wall to the free painter (because we use 1 unit of that capacity for a free task).
We must ensure that by the end of the assignment (when all walls are processed), we have covered all free tasks with paid time, which means we need j >= 0. In fact, for a valid schedule at the end, j should be ≥ 0, and if it is, all remaining needed free painting can be done within the available time.

Let's define a DP function dfs(i, j) = minimum cost to finish painting walls from index i to n-1, given a current free-time balance of j units. Here j can be understood as how many free-painted walls we can still accommodate concurrently (it’s like remaining "credit"). Initially, before painting any wall, j = 0 (no free time available yet, since no paid work has started).

Recurrence:

Base case: If we have considered all walls (i == n):
- If j >= 0 (free time balance is non-negative), that means all free tasks have been accounted for by paid time. No more cost needed, return 0.
- If j < 0, it means there were more free tasks than paid time (invalid scenario). We can return infinity (a very large cost) to indicate this branch is not feasible.
If there are no more walls left to consider (i reached n) or effectively no tasks left: Another way to handle the base case is to check if n - i <= j. This means the number of walls left to paint is less than or equal to the available free painter time. In that case, we can paint all remaining walls for free without additional cost. So return 0 cost.
Recursive cases for wall i:
1. Pay for wall i: Use the paid painter. We incur cost[i], and we gain time[i] units of free painter capacity. Also, this wall itself is handled by paid painter (so it doesn't consume a free slot). The new balance becomes j + time[i] (we add paid time), and we move to the next wall i+1. Cost for this choice = cost[i] + dfs(i+1, j + time[i]) .
2. Free for wall i: Paint it with the free painter at no cost. However, doing so uses 1 unit of the free painter’s available time. This effectively reduces our balance by 1. The new balance becomes j - 1, and move to i+1. Cost for this choice = 0 + dfs(i+1, j - 1) . (If j - 1 goes negative, it’s not immediately disallowed; it means we have one more free task than available paid time so far, but it might be resolved by future paid assignments. We'll rely on the base case to catch if it never gets resolved by the end.)

We take the minimum cost of these two choices. We will also use memoization to avoid re-solving the same (i, j) state repeatedly, since many different assignment paths can lead to the same state.

One caveat: In implementation, j can be negative, and its range can vary. In the worst case, if we decide to do many walls free first, j could be as low as -n (all walls attempted free without paid time yet), and if we pay for many walls with large times, j could be as high as sum of all times. But note that if j ever exceeds the number of remaining walls, the recursion would have already returned 0 cost (base case) because it means we have more than enough free capacity for the rest. So we can clamp or limit j to a reasonable range. A safe range for j is [-n, n] (since if we paid every wall, we’d have at most n*time units, but we don’t need more than n free slots because there are only n walls). Many implementations offset j by +n to use it as an array index (0 to 2n range) .

Top-Down DP Complexity: There are at most n possible indices × 2n possible balance states ≈ $2n^2$ states, each solved with O(1) work (just two recursive calls and a min). So time complexity is about O( $n^2$ ) . For n=500, $n^2 = 250,000$ , which is very manageable. Space complexity is O( $n \times 2n$ ) for the memo table (O( $n^2$ ) memory), plus recursion stack O(n).

Top-Down DP Example:
Using the previous small example cost=[3,5], time=[1,1]:

dfs(0,0) checks wall0:
- Pay option: cost=3 + dfs(1, 0+1) = 3 + dfs(1,1)
- Free option: cost=0 + dfs(1, 0-1) = dfs(1,-1)
Evaluate dfs(1,1) (wall1, balance=1): Since only one wall remains and balance 1 means we have enough free time for 1 wall, dfs(1,1) sees n-i=1 <= j=1 and returns 0 (base case). So the pay option yields cost 3 + 0 = 3.
Evaluate dfs(1,-1) (wall1, balance=-1): balance -1 means we currently need 1 unit of paid time but don’t have it. We try options for wall1:
- Pay wall1: cost=5 + dfs(2, -1+1) = 5 + dfs(2,0). dfs(2,0) (i=2 means no walls left, j=0) returns 0 (no walls left and no deficit), so this yields 5.
- Free wall1: cost=0 + dfs(2, -1-1) = dfs(2,-2). Now no walls left but j=-2 (deficit 2 free tasks not covered) triggers invalid case, returning inf. So free option is invalid.
- Thus dfs(1,-1) returns min(5, inf) = 5.
Back to dfs(0,0): free option cost = 5, paid option cost = 3. We take min = 3. This matches our earlier reasoning that paying wall0 and freeing wall1 is optimal (cost3). The DP avoided exploring a lot of invalid combinations explicitly because the state-space was pruned by the j balance logic.

Top-Down DP Implementation (with memoization):

Python3

. . . .

In the Python code above, we use balance as j (free time balance). We rely on the condition if n - i <= balance: return 0 as the base case to stop recursion early when the free painter can cover the rest of the walls. If we reach the end (i == n) with balance < 0, we return INF (invalid). The memoization (lru_cache) ensures each state (i, balance) is computed once.

Top-Down DP in Java: We can implement the same idea in Java. We will offset the balance by +n to use it as an index (to avoid negative indices). The balance range [-n, +n] will be mapped to [0, 2n] in an array. We'll use a memo table memo[i][balance_offset] with i up to n and balance_offset up to 2n.

Java

. . . .

Explanation: In the Java code, we offset balance by +n when calling dfs (so initial call is dfs(0, n) corresponding to balance 0). We check the base and recursion similarly to the Python version. We use Integer.MAX_VALUE/2 as a stand-in for infinity (to avoid overflow when adding costs).

Complexity: Top-down DP runs in $O(n^2)$ time and $O(n^2)$ space. With n up to 500, this is efficient. The memoization prunes away the exponential blow-up of brute force by reusing results for each state.

Bottom-Up DP (Tabulation)

We can convert the above recursion into an iterative DP table. However, an even easier way to think about the bottom-up solution is to approach it like a covering/knapSack problem:

Alternative perspective (Covering interpretation):
Consider that hiring the paid painter for a particular wall i has a "benefit": it allows that wall to be painted (obviously) plus it opens up time[i] slots for other walls to be painted free concurrently. In total, paying for wall i can cover (time[i] + 1) walls (itself + time[i] others for free). We need to cover all n walls. We want to achieve coverage of n walls with minimum cost.

This looks analogous to a knapSack / coin change style problem:

We have n "items" (each wall as a potential paid assignment).
Each item i can cover cover_i = time[i] + 1 walls if we use it (like an item weight or value).
Each item i has a cost (like weight or cost in knapSack terms) = cost[i].
We want to cover at least n walls in total (like reaching a target value) with minimum total cost.

However, we can't just take fractional coverage — if we pay for a wall, we get its full cover benefit. We either take it or not (this is a 0/1 choice, not fractional or unlimited). So this is a 0/1 knapSack variant where we must reach a total coverage of at least n.

Let's define a DP array where the index represents how many walls have been covered so far, and the value represents the minimum cost to achieve that coverage. We will build this up by considering walls one by one as potential paid choices.

State definition: dp[x] = minimum cost to cover x walls (using some combination of paid walls and free coverage). Here "cover x walls" means we have successfully painted x walls (some possibly by free painter under the umbrella of paid time). We will ultimately look for dp[n] (covering n walls).
Initially, dp[0] = 0 (cost 0 to cover 0 walls) and dp[x] = ∞ (or a very large number) for x > 0 (since we haven’t covered any walls yet).
Transition: For each wall i (treated as a potential paid wall), we can update the dp array. If we pay for wall i, we can cover 1 + time[i] walls with that one payment (itself + free coverage). Essentially, if before using wall i we had a scenario that covered k walls, then after paying for wall i, we can cover k + (time[i] + 1) walls (we use the free painter to immediately cover time[i] additional walls “for free” during the paid time).
- So for each state k that we could reach before, we can reach a new state min(n, k + time[i] + 1) after using wall i, with an additional cost cost[i].
- We take min(n, ...) because covering more than n walls is effectively just covering n (we don’t need to exceed the total number of walls).
We must be careful to not reuse a wall more than once; this means we should iterate in a way that each wall’s effect is only applied once (like typical 0/1 knapSack, we iterate the DP array backwards).

Bottom-Up Procedure:

Initialize an array dp of length n+1 with dp[0] = 0 and dp[1..n] = INF (a large number).
For each wall i from 0 to n-1:
- Let cover = time[i] + 1 (the number of walls this paid assignment can cover).
- For x from n down to 0 (backward iteration):
  - Compute newCover = min(n, x + cover) – this is how many walls can be covered if we take wall i in addition to the x already covered.
  - Update dp[newCover] = min(dp[newCover], dp[x] + cost[i]).
- Iterating backwards ensures that we don’t reuse wall i multiple times in one iteration (classic method for 0/1 knapSack updates).
After processing all walls, dp[n] will hold the minimum cost to cover n walls (i.e., paint all walls).

Explanation: Essentially, we are trying all combinations of paid walls implicitly through this DP. The state dp[x] accumulates the best ways to cover x walls. Whenever we consider a new paid wall, we see how it can extend any previously achieved coverage. The concurrency rule is inherently satisfied because we only count free coverage when it comes with a paid wall’s time.

Bottom-Up Example:
For a simple example, cost=[2,3], time=[1,1] (2 walls):

Initially: dp = [0, inf, inf] (index 0..2).
Consider wall0 (cover=2, cost=2):
- Starting from back:
  - From x=2 down to 0:
    - x=2: newCover = min(2, 2+2) = 2. Update dp[2] = min(dp[2], dp[2-2] + 2) = min(inf, dp[0] + 2) = 2. (Here dp[0] + cost0 covers 2 walls.)
    - x=1: newCover = min(2, 1+2) = 2. Update dp[2] = min(current_dp[2]=2, dp[1-?]...) actually we should consider dp[max(x-cover,0)] in backward formula, but easier is thinking as above forward. In backward method: we essentially did dp[2] = min(dp[2], dp[0]+2).
    - x=0: newCover = min(2, 0+2) = 2. Update dp[2] = min(2, dp[0]+2) = 2 (already done). We might also update dp[?] for x=1 but since cover=2, effectively any x yields newCover = 2 for x>=0 in this case.
  - Now dp = [0, inf, 2].
Consider wall1 (cover=2, cost=3):
- Backward loop:
  - x=2: newCover = min(2, 2+2) = 2. Update dp[2] = min(dp[2], dp[max(2-2,0)] + 3) = min(2, dp[0] + 3) = 2. (No change, because dp[0]+3=3 which is higher than current dp[2]=2.)
  - x=1: newCover = min(2, 1+2) = 2. Update dp[2] = min(2, dp[max(1-2,0)] + 3) = min(2, dp[0]+3) = 2. (No change.)
  - x=0: newCover = min(2, 0+2) = 2. Update dp[2] = min(2, dp[0]+3) = 2.
- dp remains [0, inf, 2].

At the end, dp[2] = 2, meaning the minimum cost to cover 2 walls is 2, which corresponds to using wall0 as the paid one (cost2) and covering both walls (itself and the other) – exactly the solution. If we check, using wall1 alone would have cost 3 which is not optimal, and using both paid would cost 5 which is not optimal. The DP correctly found cost 2.

Bottom-Up 2D DP interpretation: Another way to do bottom-up is to mirror the recursion in a 2D table of size [n+1][2n+1] (for i and balance). But the 1D approach described above is more space-efficient and intuitive in terms of covering count. It directly computes the answer in one table.

Bottom-Up Implementation (Optimized 1D DP):

Python3

. . . .

In the above code, we use a MAX_COST sentinel for infinity. We update dp for each wall. We skip states that haven’t been reached yet (dp[covered] is infinity). This ensures we only transition from achievable states. The result is dp[n].

Bottom-Up Implementation in Java (Optimized):

Java

. . . .

This Java code corresponds to the 1D DP approach. We use MAX = 500_000_000 as an effectively infinite cost (since max cost per wall is 1e6 and 500 walls would sum to 5e8 at most, this is a safe upper bound). The logic is the same: iterate over walls, update the dp array in reverse.

Complexity: The bottom-up approach uses nested loops: one over n walls and one over up to n coverage states. This is O( $n^2$ ) time, and O(n) space for the dp array . With n=500, this is about 250k operations, which is very fast. The space usage is significantly improved over the 2D memo table, but even the 2D version (which would be 500×1000) is fine. We prefer the 1D approach for simplicity and clarity.

Optimal Approach Explanation (Choosing the Right DP Strategy)

The optimal solution for this problem is the dynamic programming approach described above. To summarize and emphasize the decision-making structure:

Why DP: We have to decide for each wall whether to pay or not, and the feasibility/cost of each decision depends on how it affects the ability to paint other walls for free. This dependency and need for an optimal global outcome is classic DP territory. Greedy choices can fail because a locally expensive wall might provide a lot of free painting time that saves more cost elsewhere, or vice versa a cheap wall might allow enough concurrency to avoid a very expensive wall.
State representation: The key was to find a suitable state. We saw two ways: (1) DP with index and time-balance (like dfs(i, j) in the memoization approach), and (2) DP by coverage count (like the bottom-up approach). Both are essentially equivalent formulations of the problem’s constraints.
Why the coverage DP works: It transforms the concurrency constraint into a coverage counting problem. By ensuring we don’t count free walls without accompanying paid time, we inherently respect the rules. Each paid wall adds capacity for free walls. The DP accumulates these capacities and tracks cost, ensuring we never exceed capacity without paying cost.
Step-by-step reasoning in the optimal approach:
1. Calculate coverage requirement: We need to cover n walls.
2. For each wall as a paid option, determine how many walls it can cover (itself + free capacity). This is cover_i = time[i] + 1.
3. Use DP to combine these options optimally: starting from 0 walls covered (cost 0), try adding each paid wall option and update the best cost for each coverage amount up to n.
4. Result is the minimum cost to reach coverage = n.
Comparison of top-down vs bottom-up: The top-down memoization and bottom-up achieve the same result. The choice often comes down to preference. Top-down can be easier to implement with complex state logic because you focus on the recursion, whereas bottom-up requires thinking in terms of iteratively building solutions. In this problem, the bottom-up solution turned out to be quite elegant by using the coverage interpretation. It saves space and is straightforward to reason about as a knapSack-like combination of "items." The time complexity for both is $O(n^2)$ .

To illustrate the optimal approach with a visual example, consider: cost = [5, 1, 6], time = [2, 1, 1] (3 walls). Here:

Wall0: cost 5, time 2, covers 3 walls (itself + 2 free) if used.
Wall1: cost 1, time 1, covers 2 walls if used.
Wall2: cost 6, time 1, covers 2 walls if used.

We need to cover 3 walls. The options:

Use Wall0 alone: covers 3 walls (all) at cost 5.
Use Wall1 + Wall2: Wall1 covers 2, Wall2 covers 2, combined they can cover up to 4 walls (with overlap, effectively all 3) at cost 1+6=7.
Use Wall0 + Wall1: Wall0 covers 3 (already all) so Wall1 is extra (cost 6 total, but not needed since wall0 alone did it).
Use Wall1 alone: covers 2 walls, not enough for all 3 (invalid because one wall would remain uncovered free).
Use Wall2 alone: covers 2, not enough (invalid).
Use Wall0 + Wall2: cost 11, covers 3 (Wall0 already covers all, Wall2 extra).
Use none: covers 0 (invalid).

The best is Wall0 alone with cost 5. The DP would find:

Start dp = [0, inf, inf, inf].
Process Wall0 (cover3, cost5): dp[3] = 5.
Process Wall1 (cover2, cost1): dp[2] = 1 (from dp[0]+1). Also dp[3] = min(current 5, dp[1]+1?). dp[1] was inf, so no change for dp[3] here.
Process Wall2 (cover2, cost6): dp[2] = min(current 1, dp[0]+6) = 1. dp[3] could be updated from dp[1]+6 (dp[1] inf, no change) or dp[1] from dp[-?], etc.
We end with dp[3] = 5 as the minimum cost, which matches the optimal choice.

The DP systematically explored combinations without brute forcing all subsets explicitly.

Thus, the optimal approach is to use dynamic programming (either top-down or bottom-up). The bottom-up method with a 1D array treating each paid wall as contributing coverage is particularly clean and runs efficiently.

Common Mistakes

Misunderstanding the concurrency rule: A frequent mistake is to assume the free painter can work independently or simultaneously without restriction. Remember that if the paid painter isn’t painting, the free painter must stop. Any solution that tries to let the free painter handle walls without enough paid time will be invalid.
Greedy selection of walls: Picking walls with the largest time[i] (to maximize free coverage) or lowest cost[i] (to minimize cost) in isolation can fail. The optimal solution often requires a balance. For example, a wall with huge time but also huge cost might not be worth it if two cheaper walls could together provide the same total free time. Always verify a greedy strategy against counterexamples.
Off-by-one errors in DP transitions: When implementing the DP, it’s easy to make mistakes in the transition. For instance, forgetting the +1 (covering the paid wall itself) or mis-setting the bounds (like using max(walls - time[i] - 1, 0) incorrectly). Make sure that if a wall provides time[i] free slots, you count the wall itself as well. The coverage method time[i] + 1 is a convenient way to remember this.
Incorrect base conditions in recursion: In the top-down approach, one might forget to handle the case where remaining walls can all be done free. If you only check for i == n and then balance, you might miss returning 0 in cases where there are still walls left but already enough free time accumulated. The condition if (n - i) <= j: return 0 is crucial to avoid unnecessary computation and to handle those scenarios .
Not offsetting negative indices (in memoization): If implementing memoization with a 2D array, forgetting to offset the balance index (so that it’s non-negative) will cause index-out-of-range errors. Ensure your j (balance) mapping to array index is correct (as we did by offsetting by +n).
Using an inappropriate data type for INF: In languages like Java, using a very large integer for infinity can overflow if you add to it. We used Integer.MAX_VALUE/2 to be safe. In Python, using float('inf') or math.inf is fine. Just be careful in comparisons and additions involving your "infinity" sentinel.

Edge Cases

Minimum n (n=1): With only one wall, the answer is simply to pay for that wall. The free painter can’t work without the paid painter, so you have to hire the paid painter for the single wall. The cost will just be cost[0]. Our DP logic handles this: you start with 0 covered, one item can cover 1+time[0] ≥ 1, so dp[1] becomes cost[0]. Or the recursive solution would try free (which would lead to invalid since no paid time) vs paid (which yields the cost).
All walls very quick to paint (time[i] = 1 for all): If every wall takes 1 time unit for the paid painter, each paid wall covers 2 walls (itself + 1 free). This means in an optimal strategy you need to pay for about half the walls (every paid painter covers itself and one free wall). In fact, if n is even, you’ll pay for n/2 walls; if n is odd, you’ll pay for ceil(n/2). Which walls should those be? Intuitively, the cheapest walls. Our DP will naturally choose the cheapest set of roughly n/2 walls to minimize cost. For example, if time = [1,1,1,1] and cost = [5,1,4,2], the optimal paid set would be walls with cost 1 and 2 (covering 4 walls total) for cost 3. A greedy approach of “take cheapest” also works in that particular sub-case, but the DP handles the general case.
A wall with very large time that covers all others: If there is a wall i with time[i] >= n-1, it means paying for this one wall allows the free painter to potentially paint all other walls. Then the answer will never be worse than cost[i] (you can always just use that wall’s time to do everything). However, if that wall’s cost is extremely high, the DP might find a combination of smaller-time walls that collectively also provide enough free time at a lower cost. Edge-case to consider: multiple ways to cover all tasks. Our DP ensures the minimum cost is found.
All walls have the same cost and time: If cost and time are uniform for all walls, then any set of paid walls of a certain size is as good as any other set of that size in terms of cost/time trade-off. The problem reduces to picking the minimum number of paid walls needed. For example, if cost=[5,5,5,5] and time=[2,2,2,2] for n=4, each paid covers 3 walls. One paid wall (time=2) can cover itself + 2 free = 3 walls, not enough for 4; two paid walls (total time=4) can cover 4 walls (2 paid + 2 free). So minimum 2 paid needed, cost = 10. The DP would find that as well. Be mindful of the fence cases where coverage just falls short and an additional paid wall is needed.
Large costs vs small costs: If some wall is extremely expensive compared to others, the optimal solution will try to avoid paying for it unless its time benefit is so huge that it offsets the cost. The DP inherently checks that trade-off. Conversely, if a wall is very cheap but provides little free time, the DP might include it just because it's low cost (even though it doesn't cover many free tasks, it might still be part of the cheapest way to reach coverage).
No possible free painting (like if n=1 or if you must pay all): The worst-case scenario is you have to pay for every wall (for instance, if every wall had time=0, hypothetically, or free painter couldn’t work at all). In our problem, time is at least 1, so even the smallest paid job gives a free slot. But if n is small, you might end up paying all anyway (like n=1). The DP gracefully handles that (it would simply choose all walls as paid if needed).
Checking validity: Always ensure the final result satisfies the condition total_paid_time >= total_free_walls. Our algorithms guarantee this by construction. If you want to double-check an output, you can simulate the painting schedule: sort chosen paid walls by time (just for scheduling), schedule them back-to-back, and count if free painter can fill the gaps.

Alternative Variations

This problem touches on a scheduling concept (painting with concurrency constraint) and a combinatorial optimization (choosing which walls to pay for). Here are some variations or related scenarios:

Multiple free painters: What if you had more than one free painter available (say k free painters), all of whom can work when the paid painter is busy? The concurrency rule would change: up to k walls could be painted free in parallel during each unit of time the paid painter works. The condition would become that the total free-painted walls ≤ k * (total paid time). The DP could be adapted by increasing the coverage from each paid wall to time[i] * k + 1 (itself + k * time[i] free walls). The problem becomes easier as k grows (more free labor).
Free painter requires same time as paid for each wall: Imagine a variation where the free painter also takes time[i] to paint wall i (instead of always 1). In that case, the scheduling would need a different analysis: you would essentially have two workers (one paid, one free) with identical speed except one costs money. You’d assign walls to two workers minimizing cost with the constraint that at most one of them is free. That becomes more of a scheduling problem where you want to allocate longer tasks to the paid worker if possible, etc. The DP approach would change because the free painter’s time contribution depends on which wall they paint. (Our problem simplifies free painter time to 1 for any wall, which was crucial for our DP formulation.)
Paid painter cost-time tradeoff: A different twist could be if the paid painter’s cost was also time-based (e.g., cost per hour instead of per wall fixed). Here cost might accumulate with time. That would encourage using free painter more for longer tasks, possibly turning into a different optimization (maybe greedy works if cost per time is constant?).
Minimum time to paint all walls given a budget: A different optimization goal could be: given a budget of money, what’s the minimum time to finish painting all walls? That turns the problem on its head – now cost is a constraint and time is the objective. You’d try to maximize use of paid painter time given a cost constraint. The DP could be adapted to maximize coverage (or minimize total time which would equal maximize concurrency usage) under a cost limit.
General two-worker scheduling: This problem essentially had two workers (paid and free) but with a special rule. A general case is if you have two painters with different speeds and costs, how to assign tasks to minimize cost or time. That might require more complex scheduling algorithms (like variants of the assignment problem or linear programming if fractional work were allowed, but here it’s integral assignment).
Quality variations: Perhaps the free painter might do a lower quality job, requiring repainting after some time – then you might factor in some penalty or requirement to occasionally use paid painter anyway. This would complicate the DP.
Other “coupon” or “freebie” interpretations: The problem can be seen as: each paid wall gives you a "coupon" of time[i] free paints. What if coupons could accumulate or carry over differently? Or if each paid painter after finishing could continue to allow free painter for the remaining time if not fully utilized? In our scheduling, we assume any unused concurrent time is just wasted (free painter sits idle if paid finishes early relative to free tasks).

The given problem is a specific scenario, but it’s related to resource allocation problems where using one resource unlocks the ability to use another resource for free or cheaper. Variations could adjust those parameters or constraints.

Here are a few related LeetCode problems and how they relate:

2742. Painting the Walls - Detailed Explanation

Problem Statement

Examples

Constraints

Hints

Approach Breakdown

Brute Force Approach (Exhaustive Search)

Memoization (Top-Down DP)

Bottom-Up DP (Tabulation)

Optimal Approach Explanation (Choosing the Right DP Strategy)

Common Mistakes

Edge Cases

Alternative Variations

Related Problems