Paint House II

'''
Logic:
Logic is same as paint house 1 but we need minimum from previous row but we can get the first and second minimum
because if the minimum cost is of different color then cost to color is current_cost+previous min
        else current_cost+second_previous_min;
'''
import math
def paintCost(n, k, arr):
    min_val = float('inf')
    smin_val = float('inf')

    for j in range(k):
        if arr[0][j] <= min_val:
            smin_val = min_val
            min_val = arr[0][j]

        elif arr[0][j] <= smin_val:
            smin_val = arr[0][j]

    # process remaining rows
    for i in range(1, n):

        cmin = float('inf')
        csmin = float('inf')

        for j in range(k):

            if arr[i - 1][j] != min_val: #they can directly check is that min_val there or not, no need to store index.
                arr[i][j] += min_val
            else:
                arr[i][j] += smin_val

            # update current min and second min
            if arr[i][j] <= cmin:
                csmin = cmin
                cmin = arr[i][j]

            elif arr[i][j] <= csmin:
                csmin = arr[i][j]

        min_val = cmin
        smin_val = csmin

    return min_val