Is Painting the Walls easy or hard?

Painting the Walls is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the coverage effect of the free painter and transforming it into a knapsack-style dynamic programming state transition.

Painting the Walls Python/Java solution

Most implementations use the same DP formulation across languages. Maintain a DP array of size n+1, iterate through each wall, and update coverage states in reverse order. This approach translates directly to Python, Java, C++, C#, and JavaScript.

How to solve Painting the Walls in O(n)?

An exact O(n) algorithm is not known for the optimal solution because the problem requires evaluating combinations of painters. The best guaranteed solution uses dynamic programming with O(n^2) time, though greedy heuristics can run closer to O(n log n) with sorting or heaps.

What is the best approach for Painting the Walls?

Dynamic programming is the most reliable approach. Model the problem so that hiring a painter for wall i covers 1 + time[i] walls. Using a DP array where dp[j] stores the minimum cost to paint j walls allows you to compute the optimal answer in O(n^2) time and O(n) space.

Is Painting the Walls asked at Google/Amazon/Meta?

Painting the Walls is a hard dynamic programming problem similar to optimization questions seen in Google and Meta interviews. Variants involving resource scheduling, coverage DP, and cost minimization appear frequently in big tech interview rounds.

What data structure is used in Painting the Walls?

The core solution uses a one-dimensional dynamic programming array to track minimum cost for covering a number of walls. Some heuristic solutions may also use sorting or priority queues to evaluate greedy cost-efficiency choices.

What is the time complexity of Painting the Walls?

The standard dynamic programming solution runs in O(n^2) time because each wall updates up to n DP states. Space complexity is O(n) using a 1D DP array that tracks the minimum cost required to cover a given number of walls.

Description Hints 2 Solution Video 14:29

2742. Painting the Walls

Hard49.0% acceptance5 companies

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:

A paid painter that paints the i^th wall in time[i] units of time and takes cost[i] units of money.
A free painter that paints any wall in 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 <= 500
cost.length == time.length
1 <= cost[i] <= 10⁶
1 <= time[i] <= 500

Asked at 5 companies

Snowflake Meesho

Google Amazon Meta

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Can we break the problem down into smaller subproblems and use DP?

Hint 2

Paid painters will be used for a maximum of N/2 units of time. There is no need to use paid painter for a time greater than this.

14:29

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def paintWalls(self, cost: List[int], time: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3,2]
[1,2,3,2]

Input

[2,3,4,2]
[1,1,1,1]

Your code is saved on this device.Solution