2742. Painting the Walls LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2742. Painting the Walls LeetCode Solution with the best time and space complexity. The solution to Painting the Walls problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Painting the Walls solution in C++
Painting the Walls solution in Java
Painting the Walls solution in Python
Additional Resources

2742. Painting the Walls LeetCode Solution image

Problem Statement of Painting the Walls

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

Complexity Analysis

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

2742. Painting the Walls LeetCode Solution in C++

class Solution {
 public:
  int paintWalls(vector<int>& cost, vector<int>& time) {
    const int n = cost.size();
    vector<vector<int>> mem(n, vector<int>(n + 1));
    return paintWalls(cost, time, 0, time.size(), mem);
  }

 private:
  static constexpr int kMax = 500'000'000;

  // Returns the minimum cost to paint j walls by painters[i..n).
  int paintWalls(const vector<int>& cost, const vector<int>& time, int i,
                 int walls, vector<vector<int>>& mem) {
    if (walls <= 0)
      return 0;
    if (i == cost.size())
      return kMax;
    if (mem[i][walls] > 0)
      return mem[i][walls];
    const int pick =
        cost[i] + paintWalls(cost, time, i + 1, walls - time[i] - 1, mem);
    const int skip = paintWalls(cost, time, i + 1, walls, mem);
    return mem[i][walls] = min(pick, skip);
  }
};
/* code provided by PROGIEZ */

2742. Painting the Walls LeetCode Solution in Java

class Solution {
  public int paintWalls(int[] cost, int[] time) {
    final int n = cost.length;
    int[][] mem = new int[n][n + 1];
    return paintWalls(cost, time, 0, time.length, mem);
  }

  private static final int kMax = 500_000_000;

  // Returns the minimum cost to paint j walls by painters[i..n).
  private int paintWalls(int[] cost, int[] time, int i, int walls, int[][] mem) {
    if (walls <= 0)
      return 0;
    if (i == cost.length)
      return kMax;
    if (mem[i][walls] > 0)
      return mem[i][walls];
    final int pick = cost[i] + paintWalls(cost, time, i + 1, walls - time[i] - 1, mem);
    final int skip = paintWalls(cost, time, i + 1, walls, mem);
    return mem[i][walls] = Math.min(pick, skip);
  }
}
// code provided by PROGIEZ

2742. Painting the Walls LeetCode Solution in Python

class Solution:
  def paintWalls(self, cost: list[int], time: list[int]) -> int:
    n = len(cost)

    @functools.lru_cache(None)
    def dp(i: int, walls: int) -> int:
      """Returns the minimum cost to paint j walls by painters[i..n)."""
      if walls <= 0:
        return 0
      if i == n:
        return math.inf
      pick = cost[i] + dp(i + 1, walls - time[i] - 1)
      skip = dp(i + 1, walls)
      return min(pick, skip)

    return dp(0, n)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents