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

LeetCode:

• https://leetcode.com/problems/painting-the-walls/description/

Examples

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 hte 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^6
1 <= time[i] <= 500

• Problem Size:
  • Since cost.length is at most 500, it's small
  • You can afford O(n^2) or O(n*m) solutions without worrying too much about performance. You will not get the TLE.
• Data range:
  • cost[i] can be very large (up to 1 million), so if you are summing costs, be careful about integer overflow in some languages (like C++, Java).
  • time[i] is small (up to 500), meaning if you want to do dynamic programming (DP) based on total time, it's feasible.

Different Approaches

1️⃣ Recursive (Brute-Force Approach, TLE)

Intuition:

At every wall i, we have two options:

• Option 1: Hire the painter → pay cost[i], and paint (1 + time[i]) walls in total (1 current + time[i] extra)
• Option 2: Paint it yourself → move to next wall without paying cost.

We want the minimum cost to paint all walls.

Code:

#include <bits/stdc++.h>
using namespace std;

int solve(int i, int wallsLeft, vector<int>& cost, vector<int>& time) {
    if (wallsLeft <= 0) return 0; // Base case: all walls are painted
    if (i >= cost.size()) return 1e9; // No more painters available

    // Option 1: Hire painter i
    int hire = cost[i] + solve(i + 1, wallsLeft - 1 - time[i], cost, time);

    // Option 2: Skip painter i (paint yourself)
    int skip = solve(i + 1, wallsLeft, cost, time);

    return min(hire, skip);
}

int paintWalls(vector<int>& cost, vector<int>& time) {
    int n = cost.size();
    return solve(0, n, cost, time);
}

Complexity Analysis:

• Time Complexity:O(2^n)
  • In worst case – because foe each wall, we have 2 options (take or skip).
  • Not efficient for large inputs (n up to 500). Will TLE (Time Limit Exceeded) in contests.
• Space Complexity:O(n)
  • Stack space because of recursion depth up to n.

2️⃣ Memoization (Top-Down Approach)

Approach:

Try each wall: either hire a painter or skip it. Track how many walls are left.

Code:

#include <bits/stdc++.h>
using namespace std;

int dp[501][501];

int solve(int i, int wallsLeft, vector<int>& cost, vector<int>& time) {
    if (wallsLeft <= 0) return 0;
    if (i >= cost.size()) return 1e9;

    if (dp[i][wallsLeft] != -1) return dp[i][wallsLeft];

    // Option 1: Hire painter i
    int hire = cost[i] + solve(i + 1, wallsLeft - 1 - time[i], cost, time);

    // Option 2: Skip (paint it yourself)
    int skip = solve(i + 1, wallsLeft, cost, time);

    return dp[i][wallsLeft] = min(hire, skip);
}

int paintWalls(vector<int>& cost, vector<int>& time) {
    int n = cost.size();
    memset(dp, -1, sizeof(dp));
    return solve(0, n, cost, time);
}

Complexity Analysis:

• Time Complexity:O(n^2)
  • n is the number of walls (≤ 500), and each recursive state is (i, wallLeft).
  • Memoization ensure we don't recompute the same state.
• Space Complexity:O(n^2)
  • For the DP table.

3️⃣ Tabulation (Bottom-up Approach)

• Think “past” first (build up small answers first.
• Precompute answers from the start.
• Iterative (loops)