Skip to main content
Talentd

Painting the Walls - Solution & Explanation

HardArrayDynamic Programming20 min readAsked at: Amazon, Meta, Snowflake +2
Practice this problem

Problem Statement

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 ith 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] <= 106
  • 1 <= time[i] <= 500

Approach Overview

Problem 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.

Approach 1: Approach 1: Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), Space Complexity: O(n)

Try this approach in the editor ā†’

Approach 2: Approach 2: Greedy Strategy

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), Space Complexity: O(n)

Try this approach in the editor ā†’

Approach 3: Memorization

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:

  • If 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;
  • If i \ge n, return +infty;
  • Otherwise, if the 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.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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ā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(nĀ²)O(n)General case where optimal minimum cost must be guaranteed
Greedy Strategy with Sorting/HeapO(n log n)O(n)Useful heuristic when prioritizing high time-to-cost efficiency

Video Solution

Painting the Walls - Leetcode 2742 - Python ā€¢ NeetCodeIO ā€¢ 19,218 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Painting the Walls with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays