Day 63 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/walls-coloring-ii--170647/1

Walls Coloring II

Difficulty: Hard Accuracy: 50.15%

You are given n walls arranged in a row, and each wall must be painted using one of the k available colors. The cost of painting ith wall with jth color is given by costs[i][j]. Your task is to determine the minimum total cost required to paint all the walls in such a way that no two adjacent walls share the same color. If it is impossible to paint the walls under this condition, you must 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 = 8
Input: 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.
Constraints:
0 ≤ n ≤ 103
0 ≤ k ≤ 103
1 ≤ costs[i][j] ≤ 105

Solution:
from typing import List

class Solution:
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
if n == 0:
return 0
k = len(costs[0])
if k == 0:
return -1
if n > 1 and k == 1:
return -1

prev_min = prev_second_min = 0
prev_min_idx = prev_second_min_idx = -1

    for i in range(n):
        curr_min = curr_second_min = float('inf')
        curr_min_idx = curr_second_min_idx = -1

        for j in range(k):
            cost = costs[i][j]
            if j != prev_min_idx:
                total_cost = cost + prev_min
            else:
                total_cost = cost + prev_second_min

            if total_cost < curr_min:
                curr_second_min = curr_min
                curr_second_min_idx = curr_min_idx
                curr_min = total_cost
                curr_min_idx = j
            elif total_cost < curr_second_min:
                curr_second_min = total_cost
                curr_second_min_idx = j

        prev_min, prev_second_min = curr_min, curr_second_min
        prev_min_idx, prev_second_min_idx = curr_min_idx, curr_second_min_idx

    return prev_min