There is a row of N walls in Geeksland. The king of Geeksland ordered Alexa to color all the walls on the occasion of New Year. Alexa can color each wall with one of the K colors. The cost associated with coloring each wall with a particular color is represented by a 2D costs array of size N * K. For example, costs[0][0] is the cost of coloring wall 0 with color 0; costs[1][2] is the cost of coloring wall 1 with color 2, and so on… Find the minimum cost to color all the walls such that no two adjacent walls have the same color.
Note: If you are not able to paint all the walls, then you should return -1.
Examples:
Input: N = 4, K = 3, costs[][] = {{1, 5, 7}, {5, 8, 4}, {3, 2, 9}, {1, 2, 4}}
Output: 8
Explanation: Paint wall 0 with color 0. Cost = 1
Paint wall 1 with color 2. Cost = 4
Paint wall 2 with color 1. Cost = 2
Paint wall 3 with color 0. Cost = 1
Total Cost = 1 + 4 + 2 + 1 = 8Input: N = 5, K = 1, costs[][] = {{5}, {4}, {9}, {2}, {1}}
Output: -1
Explanation: It is not possible to color all the walls under the given conditions.
Approach: To solve the problem follow the below idea:
This is a classic knapsack problem. To calculate the minimum cost to color, the idea is to use dynamic programming. It creates a 2D vector called dp with n rows and k columns, where dp[i][j] represents the minimum cost of painting the first i houses, where the ith house is painted with the jth color.
Below are the steps for the above approach:
- Define dp[n][k], where dp[i][j] means the minimum cost for wall i with color j.
- Initial value: dp[0][j] = costs[0][j]. For others, dp[i][j] = INT_MAX, i ≥ 1.
- Recurrence relation: dp[i][j] = min(dp[i][j], dp[i – 1][k] + cost[i][j]), where k != j.
- Final state: Min(dp[n – 1][k]).
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int minCost(vector<vector<int> >& costs){ int n = costs.size(); int k = costs[0].size(); if (n > 1 && k == 1) return -1; vector<vector<int> > dp(n, vector<int>(k, 0)); for (int i = 0; i < k; i++) { dp[0][i] = costs[0][i]; } for (int itr = 1; itr < n; itr++) { for (int i = 0; i < k; i++) { int mini = INT_MAX; for (int j = 0; j < k; j++) { if (i == j) continue; else mini = min(mini, dp[itr - 1][j]); } dp[itr][i] = costs[itr][i] + mini; } } int ans = INT_MAX; for (int i = 0; i < k; i++) { ans = min(ans, dp[n - 1][i]); } if (ans == INT_MAX) return 0; return ans;}// Drivers codeint main(){ vector<vector<int> > costs = { { 1, 5, 7 }, { 5, 8, 4 }, { 3, 2, 9 }, { 1, 2, 4 } }; // Function Call int ans = minCost(costs); cout << ans; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { static int minCost(int[][] costs) { int n = costs.length; int k = costs[0].length; if (n > 1 && k == 1) return -1; int[][] dp = new int[n][k]; for (int i = 0; i < k; i++) dp[0][i] = costs[0][i]; for (int itr = 1; itr < n; itr++) { for (int i = 0; i < k; i++) { int mini = Integer.MAX_VALUE; for (int j = 0; j < k; j++) { if (i == j) continue; else mini = Math.min(mini, dp[itr - 1][j]); } dp[itr][i] = costs[itr][i] + mini; } } int ans = Integer.MAX_VALUE; for (int i = 0; i < k; i++) ans = Math.min(ans, dp[n - 1][i]); if (ans == Integer.MAX_VALUE) return 0; return ans; } public static void main(String[] args) { int[][] costs = { { 1, 5, 7 }, { 5, 8, 4 }, { 3, 2, 9 }, { 1, 2, 4 } }; int ans = minCost(costs); System.out.println(ans); }} |
Python3
# Python3 code for the above approach:def min_cost(costs): n = len(costs) k = len(costs[0]) if n > 1 and k == 1: return -1 dp = [[0] * k for _ in range(n)] for i in range(k): dp[0][i] = costs[0][i] for itr in range(1, n): for i in range(k): mini = float('inf') for j in range(k): if i == j: continue else: mini = min(mini, dp[itr - 1][j]) dp[itr][i] = costs[itr][i] + mini ans = float('inf') for i in range(k): ans = min(ans, dp[n - 1][i]) if ans == float('inf'): return 0 return ans# Driver codecosts = [[1, 5, 7], [5, 8, 4], [3, 2, 9], [1, 2, 4]]ans = min_cost(costs)print(ans) |
C#
// C# code for the above approach:using System;class GFG { static int MinCost(int[][] costs) { int n = costs.Length; int k = costs[0].Length; if (n > 1 && k == 1) return -1; int[][] dp = new int[n][]; for (int i = 0; i < n; i++) dp[i] = new int[k]; for (int i = 0; i < k; i++) dp[0][i] = costs[0][i]; for (int itr = 1; itr < n; itr++) { for (int i = 0; i < k; i++) { int mini = int.MaxValue; for (int j = 0; j < k; j++) { if (i == j) continue; else mini = Math.Min(mini, dp[itr - 1][j]); } dp[itr][i] = costs[itr][i] + mini; } } int ans = int.MaxValue; for (int i = 0; i < k; i++) ans = Math.Min(ans, dp[n - 1][i]); if (ans == int.MaxValue) return 0; return ans; } static void Main(string[] args) { int[][] costs = new int[][] { new int[] { 1, 5, 7 }, new int[] { 5, 8, 4 }, new int[] { 3, 2, 9 }, new int[] { 1, 2, 4 } }; int ans = MinCost(costs); Console.WriteLine(ans); }} |
Javascript
// JavaScript code for the above approach:function minCost(costs) { const n = costs.length; const k = costs[0].length; if (n > 1 && k === 1) { return -1; } const dp = new Array(n).fill().map(() => new Array(k).fill(0)); for (let i = 0; i < k; i++) { dp[0][i] = costs[0][i]; } for (let itr = 1; itr < n; itr++) { for (let i = 0; i < k; i++) { let mini = Infinity; for (let j = 0; j < k; j++) { if (i === j) { continue; } else { mini = Math.min(mini, dp[itr - 1][j]); } } dp[itr][i] = costs[itr][i] + mini; } } let ans = Infinity; for (let i = 0; i < k; i++) { ans = Math.min(ans, dp[n - 1][i]); } if (ans === Infinity) { return 0; } return ans;}// Driver codeconst costs = [ [1, 5, 7], [5, 8, 4], [3, 2, 9], [1, 2, 4],];const ans = minCost(costs);console.log(ans); |
Output
8
Time Complexity: O(N*K*K)
Auxiliary Space: O(N*K)
Efficient approach: To solve the problem follow the below idea:
To optimize the code and avoid using a 2D array to store the costs of painting each house with each color, the code uses a 1D array dp to store the minimum cost of painting the previous house with each color, and a separate 1D array prev_dp to store the minimum cost of painting the previous house with each color in the previous iteration. This way, we can update the dp array in place without overwriting the values needed for the next iteration.
Below are the steps for the above approach:
- Define the state: Let dp[i][j] be the minimum cost of painting the first i houses with the last house painted with color j.
- Define the base case: The base case is when there are no houses to paint, so dp[0][j] = 0.
- Define the recurrence relation: The recurrence relation is dp[i][j] = min(dp[i-1][k]) + cost[i-1][j], where k != j and cost[i-1][j] is the cost of painting house i-1 with color j.
- Define the final answer: The final answer is min(dp[N][j]).
- Implement the solution: The given code implements the above steps by using two arrays dp and prev_dp to store the minimum cost of painting the previous i-1 houses and the current i houses respectively. It first initializes the dp array with the cost of painting the first house with each color. Then, for each subsequent house, it calculates the minimum cost of painting the house with each color while ensuring that no two adjacent houses have the same color. Finally, it returns the minimum value in the dp array as the answer.
C++
#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost of painting n houses with k colorsint minCost(vector<vector<int> >& costs){ // Get the number of houses and colors int n = costs.size(); int k = costs[0].size(); // Check for invalid input where there are more than 1 houses but only 1 color if (n > 1 && k == 1) return -1; // Initialize two vectors to keep track of minimum costs of painting the previous and current house vector<int> dp(k, 0); vector<int> prev_dp(k, 0); // Set the initial minimum costs of painting the first house with each color for (int i = 0; i < k; i++) { dp[i] = costs[0][i]; } // Iterate through the remaining houses for (int i = 1; i < n; i++) { int min1 = INT_MAX, min2 = INT_MAX; // Find the minimum and second minimum cost of painting the previous house with different colors for (int j = 0; j < k; j++) { if (dp[j] < min1) { min2 = min1; min1 = dp[j]; } else if (dp[j] < min2) { min2 = dp[j]; } } // Calculate the minimum cost of painting the current house with each color for (int j = 0; j < k; j++) { if (dp[j] == min1) { dp[j] = min2 + costs[i][j]; } else { dp[j] = min1 + costs[i][j]; } } } // Return the minimum cost of painting the last house return *min_element(dp.begin(), dp.end());}// Main functionint main(){ // Example input vector<vector<int> > costs = { { 1, 5, 7 }, { 5, 8, 4 }, { 3, 2, 9 }, { 1, 2, 4 } }; // Call the minCost function to get the result int ans = minCost(costs); // Output the result cout << ans << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to find the minimum cost of painting n houses with k colors public static int minCost(int[][] costs) { // Get the number of houses and colors int n = costs.length; int k = costs[0].length; // Check for invalid input where there are more than 1 // houses but only 1 color if (n > 1 && k == 1) return -1; // Initialize two arrays to keep track of minimum costs // of painting the previous and current house int[] dp = new int[k]; int[] prev_dp = new int[k]; // Set the initial minimum costs of painting the first house // with each color for (int i = 0; i < k; i++) { dp[i] = costs[0][i]; } // Iterate through the remaining houses for (int i = 1; i < n; i++) { int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; // Find the minimum and second minimum cost of painting the // previous house with different colors for (int j = 0; j < k; j++) { if (dp[j] < min1) { min2 = min1; min1 = dp[j]; } else if (dp[j] < min2) { min2 = dp[j]; } } // Calculate the minimum cost of painting the current house // with each color for (int j = 0; j < k; j++) { if (dp[j] == min1) { dp[j] = min2 + costs[i][j]; } else { dp[j] = min1 + costs[i][j]; } } } // Return the minimum cost of painting the last house return Arrays.stream(dp).min().getAsInt(); } // Main function public static void main(String[] args) { // Example input int[][] costs = { { 1, 5, 7 }, { 5, 8, 4 }, { 3, 2, 9 }, { 1, 2, 4 } }; // Call the minCost function to get the result int ans = minCost(costs); // Output the result System.out.println(ans); }} |
Python
# python code for following approachimport sys# Function to find the minimum cost of painting n houses with k colorsdef minCost(costs): # Get the number of houses and colors n = len(costs) k = len(costs[0]) # Check for invalid input where there are more than 1 houses but only 1 color if n > 1 and k == 1: return -1 # Initialize two lists to keep track of minimum costs of painting the previous and current house dp = [0] * k prev_dp = [0] * k # Set the initial minimum costs of painting the first house with each color for i in range(k): dp[i] = costs[0][i] # Iterate through the remaining houses for i in range(1, n): min1 = sys.maxsize min2 = sys.maxsize # Find the minimum and second minimum cost of painting the previous house with different colors for j in range(k): if dp[j] < min1: min2 = min1 min1 = dp[j] elif dp[j] < min2: min2 = dp[j] # Calculate the minimum cost of painting the current house with each color for j in range(k): if dp[j] == min1: dp[j] = min2 + costs[i][j] else: dp[j] = min1 + costs[i][j] # Return the minimum cost of painting the last house return min(dp)# Main functionif __name__ == "__main__": # Example input costs = [ [1, 5, 7], [5, 8, 4], [3, 2, 9], [1, 2, 4] ] # Call the minCost function to get the result ans = minCost(costs) # Output the result print(ans)# This code generated by chetan bargal |
Javascript
// Function to find the minimum cost of painting n houses with k colorsfunction minCost(costs){ // Get the number of houses and colors const n = costs.length; const k = costs[0].length; // Check for invalid input where // there are more than 1 houses but only 1 color if (n > 1 && k === 1) { return -1; } // Initialize two arrays to keep track of // minimum costs of painting the previous and current house let dp = new Array(k).fill(0); let prev_dp = new Array(k).fill(0); // Set the initial minimum costs // of painting the first house with each color for (let i = 0; i < k; i++) { dp[i] = costs[0][i]; } // Iterate through the remaining houses for (let i = 1; i < n; i++) { let min1 = Number.MAX_VALUE, min2 = Number.MAX_VALUE; // Find the minimum and second minimum cost // of painting the previous house with different colors for (let j = 0; j < k; j++) { if (dp[j] < min1) { min2 = min1; min1 = dp[j]; } else if (dp[j] < min2) { min2 = dp[j]; } } // Calculate the minimum cost of painting the current house with each color for (let j = 0; j < k; j++) { if (dp[j] === min1) { dp[j] = min2 + costs[i][j]; } else { dp[j] = min1 + costs[i][j]; } } } // Return the minimum cost of painting the last house return Math.min(...dp);}// Main functionfunction main() { // Example input const costs = [ [1, 5, 7], [5, 8, 4], [3, 2, 9], [1, 2, 4] ]; // Call the minCost function to get the result const ans = minCost(costs); // Output the result console.log(ans);}// Call the main functionmain(); |
C#
using System;using System.Collections.Generic;using System.Linq;public class Gfg { // Function to find the minimum cost of painting n // houses with k colors public static int minCost(List<List<int> > costs) { // Get the number of houses and colors int n = costs.Count; int k = costs[0].Count; // Check for invalid input where there are more than // 1 houses but only 1 color if (n > 1 && k == 1) return -1; // Initialize two lists to keep track of minimum // costs of painting the previous and current house List<int> dp = new List<int>(Enumerable.Repeat(0, k)); List<int> prev_dp = new List<int>(Enumerable.Repeat(0, k)); // Set the initial minimum costs of painting the // first house with each color for (int i = 0; i < k; i++) { dp[i] = costs[0][i]; } // Iterate through the remaining houses for (int i = 1; i < n; i++) { int min1 = int.MaxValue, min2 = int.MaxValue; // Find the minimum and second minimum cost of // painting the previous house with different // colors for (int j = 0; j < k; j++) { if (dp[j] < min1) { min2 = min1; min1 = dp[j]; } else if (dp[j] < min2) { min2 = dp[j]; } } // Calculate the minimum cost of painting the // current house with each color for (int j = 0; j < k; j++) { if (dp[j] == min1) { dp[j] = min2 + costs[i][j]; } else { dp[j] = min1 + costs[i][j]; } } } // Return the minimum cost of painting the last // house return dp.Min(); } // Main function public static void Main() { // Example input List<List<int> > costs = new List<List<int> >{ new List<int>{ 1, 5, 7 }, new List<int>{ 5, 8, 4 }, new List<int>{ 3, 2, 9 }, new List<int>{ 1, 2, 4 } }; // Call the minCost function to get the result int ans = minCost(costs); // Output the result Console.WriteLine(ans); }} |
Output
8
Time Complexity: O(N*K)
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
