Painting the Walls solution and explanation
Google
9 more videos on this problem
Painting the Walls - Leetcode 2742 - PythonNeetCodeIO · 14:29 · 19K views
Painting the Walls | Why Greedy Fails | Recursion | Memoization | GOOGLE | Leetcode - 2742codestorywithMIK · 28:12 · 9K views
Leetcode Weekly 350: 2742. Painting the WallsDivyansh Tyagi · 23:00 · 2K views
Leetcode weekly contest 350 solution | Painting the Walls | Hard | Hindi explanationPawan Kumar Giri · 26:01 · 1K views
Leetcode 2742 Painting the WallsJeevan Kumar - Cracckify · 18:45 · 1K views
Painting the Walls | Leetcode 2742 | Recursion + Memo | Weekly 350Tech Courses · 15:23 · 1K views
2742. Painting the Walls(Weekly Contest 350 )Ayush Rao · 9:21 · 917 views
Painting the Walls - Dynamic Programming - 2742 LeetCode Hard - in 7 mins- ExplainedLeet Logics · 6:40 · 884 views
2742. Painting the Walls (Leetcode Hard)Programming Live with Larry · 45:47 · 817 views
Daily Leetcode #1292: Oct 14, 2023 - 2742. Painting the WallsProgramming Live with Larry · 17:33 · 536 views
The problem
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
ithwall intime[i]units of time and takescost[i]units of money. - A free painter that paints any wall in
1unit of time at a cost of0. 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] <= 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.
def minCost(cost, time):
n = len(cost)
dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(n):
occupied = 0
for j in range(i + 1, n + 1):
if occupied >= time[i]:
dp[j] = min(dp[j], dp[i] + cost[j-1])
break
occupied += time[i]
return dp[n]
# Example usage
cost = [1, 2, 3, 2]
time = [1, 2, 3, 2]
print(minCost(cost, time))import java.util.Arrays;
public class PaintWalls {
public static int minCost(int[] cost, int[] time) {
int n = cost.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int occupied = 0;
for (int j = i; j > 0; j--) {
if (occupied >= time[j - 1]) {
dp[i] = Math.min(dp[i], dp[j - 1] + cost[i - 1]);
break;
}
occupied += time[j - 1];
}
}
return dp[n];
}
public static void main(String[] args) {
int[] cost = {1, 2, 3, 2};
int[] time = {1, 2, 3, 2};
System.out.println(minCost(cost, time));
}
}#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int minCost(vector<int>& cost, vector<int>& time) {
int n = cost.size();
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (j == i || time[i] + (j == 0 ? 0 : time[j-1]) <= time[i]) {
dp[j + 1] = min(dp[j + 1], dp[i] + cost[j]);
}
}
}
return dp[n];
}
int main() {
vector<int> cost = {1, 2, 3, 2};
vector<int> time = {1, 2, 3, 2};
cout << minCost(cost, time) << endl;
return 0;
}function minCost(cost, time) {
const n = cost.length;
const dp = Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i < n; i++) {
let occupied = 0;
for (let j = i + 1; j <= n; j++) {
if (occupied >= time[i]) {
dp[j] = Math.min(dp[j], dp[i] + cost[j - 1]);
break;
}
occupied += time[i];
}
}
return dp[n];
}
// Example usage:
const cost = [1, 2, 3, 2];
const time = [1, 2, 3, 2];
console.log(minCost(cost, time));#include <stdio.h>
#include <limits.h>
int minCost(int* cost, int* time, int n) {
int dp[n+1];
int occupied = 0;
dp[0] = 0;
dp[1] = cost[0];
for (int i = 2; i <= n; i++) {
dp[i] = INT_MAX;
for (int j = i-1; j >= 0; j--) {
if (occupied >= time[j]) {
dp[i] = fmin(dp[i], dp[j] + cost[i-1]);
break;
}
occupied += time[j];
}
}
return dp[n];
}
int main() {
int cost[] = {1, 2, 3, 2};
int time[] = {1, 2, 3, 2};
int n = sizeof(cost) / sizeof(cost[0]);
printf("%d\n", minCost(cost, time, n));
return 0;
}using System;
class Program {
static int MinCost(int[] cost, int[] time) {
int n = cost.Length;
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) dp[i] = int.MaxValue;
dp[0] = 0;
for (int i = 0; i < n; i++) {
int occupied = 0;
for (int j = i + 1; j <= n; j++) {
if (occupied >= time[i]) {
dp[j] = Math.Min(dp[j], dp[i] + cost[j - 1]);
break;
}
occupied += time[i];
}
}
return dp[n];
}
static void Main() {
int[] cost = {1, 2, 3, 2};
int[] time = {1, 2, 3, 2};
Console.WriteLine(MinCost(cost, time));
}
}This Python solution utilizes a list to manage the state of minimum cost to paint up to each wall by assessing which painter to use based on availability and cost-effectiveness.
Time Complexity: O(n^2), Space Complexity: O(n)
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.
def minCost(cost, time):
ratios = sorted((c / t, c, t) for c, t in zip(cost, time))
total_cost = 0
occupied_time = 0
for _, c, t in ratios:
if occupied_time < t:
total_cost += c
occupied_time += t
return total_cost
# Example usage
cost = [1, 2, 3, 2]
time = [1, 2, 3, 2]
print(minCost(cost, time))import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class PaintWalls {
static class Pair implements Comparable<Pair> {
int cost;
int time;
Pair(int cost, int time) {
this.cost = cost;
this.time = time;
}
@Override
public int compareTo(Pair o) {
return Double.compare((double) this.cost / this.time, (double) o.cost / o.time);
}
}
public static int minCost(int[] cost, int[] time) {
int n = cost.length;
List<Pair> ratio = new ArrayList<>();
for (int i = 0; i < n; i++) {
ratio.add(new Pair(cost[i], time[i]));
}
Collections.sort(ratio);
int totalCost = 0;
int occupiedTime = 0;
for (Pair p : ratio) {
if (occupiedTime < p.time) {
totalCost += p.cost;
occupiedTime += p.time;
}
}
return totalCost;
}
public static void main(String[] args) {
int[] cost = {1, 2, 3, 2};
int[] time = {1, 2, 3, 2};
System.out.println(minCost(cost, time));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
return (double)a.first / a.second < (double)b.first / b.second;
}
int minCost(vector<int> &cost, vector<int> &time) {
int n = cost.size();
vector<pair<int, int>> ratio;
for (int i = 0; i < n; i++) {
ratio.push_back(make_pair(cost[i], time[i]));
}
sort(ratio.begin(), ratio.end(), compare);
int totalCost = 0;
int occupiedTime = 0;
for (int i = 0; i < n; i++) {
if (occupiedTime < ratio[i].second) {
totalCost += ratio[i].first;
occupiedTime += ratio[i].second;
}
}
return totalCost;
}
int main() {
vector<int> cost = {1, 2, 3, 2};
vector<int> time = {1, 2, 3, 2};
cout << minCost(cost, time) << endl;
return 0;
}function minCost(cost, time) {
const ratios = cost.map((c, i) => [c / time[i], c, time[i]]);
ratios.sort((a, b) => a[0] - b[0]);
let totalCost = 0;
let occupiedTime = 0;
for (let [_, c, t] of ratios) {
if (occupiedTime < t) {
totalCost += c;
occupiedTime += t;
}
}
return totalCost;
}
// Example usage:
const cost = [1, 2, 3, 2];
const time = [1, 2, 3, 2];
console.log(minCost(cost, time));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
double r1 = *(int *)a;
double r2 = *(int *)b;
return (r1 > r2) - (r1 < r2);
}
int minCost(int *cost, int *time, int n) {
double ratio[n];
for (int i = 0; i < n; i++) {
ratio[i] = (double)cost[i] / time[i];
}
qsort(ratio, n, sizeof(double), cmp);
int totalCost = 0;
int occupiedTime = 0;
for (int i = 0; i < n; i++) {
if (occupiedTime < time[i]) {
totalCost += cost[i];
occupiedTime += time[i];
}
}
return totalCost;
}
int main() {
int cost[] = {1, 2, 3, 2};
int time[] = {1, 2, 3, 2};
int n = sizeof(cost) / sizeof(cost[0]);
printf("%d\n", minCost(cost, time, n));
return 0;
}using System;
using System.Collections.Generic;
class Program {
class Pair : IComparable<Pair> {
public int cost, time;
public Pair(int c, int t) {
cost = c;
time = t;
}
public int CompareTo(Pair other) {
return ((double)cost / time).CompareTo((double)other.cost / other.time);
}
}
static int MinCost(int[] cost, int[] time) {
List<Pair> ratios = new List<Pair>();
for (int i = 0; i < cost.Length; i++) {
ratios.Add(new Pair(cost[i], time[i]));
}
ratios.Sort();
int totalCost = 0;
int occupiedTime = 0;
foreach (Pair pair in ratios) {
if (occupiedTime < pair.time) {
totalCost += pair.cost;
occupiedTime += pair.time;
}
}
return totalCost;
}
static void Main() {
int[] cost = {1, 2, 3, 2};
int[] time = {1, 2, 3, 2};
Console.WriteLine(MinCost(cost, time));
}
}This Python solution employs sorting based on cost/time ratios to prioritize which walls to paint. The greedy selection ensures we minimize the cost by picking efficient orders.
Time Complexity: O(n log n), Space Complexity: O(n)
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 is0; - If
i \ge n, return+infty; - Otherwise, if the
ith wall is painted by a paid painter, the cost iscost[i], thendfs(i, j) = dfs(i + 1, j + time[i]) + cost[i]; if theith wall is painted by a free painter, the cost is0, thendfs(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.
func paintWalls(cost []int, time []int) int {
n := len(cost)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n<<1|1)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if n-i <= j-n {
return 0
}
if i >= n {
return 1 << 30
}
if f[i][j] == -1 {
f[i][j] = min(dfs(i+1, j+time[i])+cost[i], dfs(i+1, j-1))
}
return f[i][j]
}
return dfs(0, n)
}impl Solution {
#[allow(dead_code)]
pub fn paint_walls(cost: Vec<i32>, time: Vec<i32>) -> i32 {
let n = cost.len();
let mut record_vec: Vec<Vec<i32>> = vec![vec![-1; n << 1 | 1]; n];
Self::dfs(&mut record_vec, 0, n as i32, n as i32, &time, &cost)
}
#[allow(dead_code)]
fn dfs(
record_vec: &mut Vec<Vec<i32>>,
i: i32,
j: i32,
n: i32,
time: &Vec<i32>,
cost: &Vec<i32>,
) -> i32 {
if n - i <= j - n {
// All the remaining walls can be printed at no cost
// Just return 0
return 0;
}
if i >= n {
// No way this case can be achieved
// Just return +INF
return 1 << 30;
}
if record_vec[i as usize][j as usize] == -1 {
// This record hasn't been written
record_vec[i as usize][j as usize] = std::cmp::min(
Self::dfs(record_vec, i + 1, j + time[i as usize], n, time, cost)
+ cost[i as usize],
Self::dfs(record_vec, i + 1, j - 1, n, time, cost),
);
}
record_vec[i as usize][j as usize]
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.