You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:
ith wall in time[i] units of time and takes cost[i] units of money.1 unit of time at a cost of 0. But the free painter can only be used if the paid painter is already occupied.Return the minimum amount of money required to paint the n walls.
Example 1:
Input: cost = [1,2,3,2], time = [1,2,3,2] Output: 3 Explanation: The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.
Example 2:
Input: cost = [2,3,4,2], time = [1,1,1,1] Output: 4 Explanation: The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.
Constraints:
1 <= cost.length <= 500cost.length == time.length1 <= cost[i] <= 1061 <= time[i] <= 500Problem Overview: You are given two arrays cost and time. Hiring a paid painter for wall i costs cost[i] and takes time[i] units, during which a free painter can paint other walls. The goal is to minimize the total cost required to paint all walls.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
This problem behaves like a knapsack-style decision process. When you hire a paid painter for wall i, that painter finishes one wall and the free painter can complete up to time[i] additional walls while the paid work happens. That means a single paid job effectively covers 1 + time[i] walls. Use dynamic programming where dp[j] represents the minimum cost required to finish j walls. Iterate through each wall and update the DP state backwards, similar to a 0/1 knapsack transition. The update becomes dp[min(n, j + time[i] + 1)] = min(dp[min(n, j + time[i] + 1)], dp[j] + cost[i]). This ensures each paid painter expands coverage efficiently while minimizing cost. Time complexity is O(n²) because each wall updates up to n states, and space complexity is O(n). This approach directly models the scheduling benefit of the free painter and guarantees the optimal result.
The DP formulation is a classic resource coverage optimization problem and commonly appears in dynamic programming interview questions. The input arrays are processed sequentially, making the state transition straightforward while keeping memory usage small.
Approach 2: Greedy Strategy with Priority Selection (O(n log n) time, O(n) space)
A heuristic approach tries to prioritize walls that provide the most free painting coverage relative to their cost. Compute an efficiency metric such as (time[i] + 1) / cost[i] and process walls that give the largest coverage benefit first. Use sorting or a priority queue to repeatedly pick the wall that yields the most additional painted walls per unit cost. Each selection reduces the remaining number of walls that must be handled by paid painters. This greedy strategy runs in O(n log n) time due to sorting or heap operations and uses O(n) space.
Greedy works well in many practical cases because larger time[i] values effectively amortize costs across more walls. However, it does not guarantee optimality for all inputs since the benefit of one painter depends on combinations with others. For guaranteed correctness, dynamic programming remains the safer option.
The greedy reasoning relies on evaluating tradeoffs between cost and coverage, which is a common technique in array optimization problems and interview-style greedy decisions.
Recommended for interviews: The dynamic programming solution is the expected approach. Interviewers want to see you convert the free-time effect into a state transition similar to knapsack coverage. Discussing a greedy idea shows good intuition about cost efficiency, but implementing the DP demonstrates stronger algorithmic control and guarantees the optimal answer.
This approach uses a dynamic programming strategy to determine the minimum cost. The idea is to leverage a DP array where dp[i] represents the minimum cost to paint up to the i-th wall. For each wall, we decide whether to use only the paid painter or to also utilize the free painter effectively when paid painter is occupied.
This C solution implements a dynamic programming approach. It uses a 'dp' array where each index i captures the minimum cost to paint walls up to that point. The loop iteratively decides whether to utilize the paid or free painter based on occupancy.
Time Complexity: O(n^2), Space Complexity: O(n)
This approach leverages a greedy strategy, prioritizing the choice that minimizes cost per time unit. By sorting or considering smallest cost per time unit, we attempt to reach a solution that overall minimizes the total cost.
This C greedy approach calculates ratios of cost per time unit and sorts them to choose the painting sequence that increases efficiency, minimizing the cost.
Time Complexity: O(n log n), Space Complexity: O(n)
We can consider whether each wall is painted by a paid painter or a free painter. Design a function dfs(i, j), which means that from the ith wall, and the current remaining free painter working time is j, the minimum cost of painting all the remaining walls. Then the answer is dfs(0, 0).
The calculation process of function dfs(i, j) is as follows:
n - i \le j, it means that there are no more walls than the free painter's working time, so the remaining walls are painted by the free painter, and the cost is 0;i \ge n, return +infty;ith wall is painted by a paid painter, the cost is cost[i], then dfs(i, j) = dfs(i + 1, j + time[i]) + cost[i]; if the ith wall is painted by a free painter, the cost is 0, then dfs(i, j) = dfs(i + 1, j - 1).Note that the parameter j may be less than 0. Therefore, in the actual coding process, except for the Python language, we add an offset n to j so that the range of j is [0, 2n].
Time complexity O(n^2), space complexity O(n^2). Where n is the length of the array.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n^2), Space Complexity: O(n) |
| Approach 2: Greedy Strategy | Time Complexity: O(n log n), Space Complexity: O(n) |
| Memorization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | General case where optimal minimum cost must be guaranteed |
| Greedy Strategy with Sorting/Heap | O(n log n) | O(n) | Useful heuristic when prioritizing high time-to-cost efficiency |
Painting the Walls - Leetcode 2742 - Python • NeetCodeIO • 18,523 views views
Watch 9 more video solutions →Practice Painting the Walls with our built-in code editor and test cases.
Practice on FleetCode