[leetcode] Paint House II

Space can be optimized more since only the min from previous is needed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

public class Solution { public int minCostII(int[][] costs) { if (costs == null||costs.length == 0){ return 0; } if (costs[0].length <= 1 && costs.length > 1){ return Integer.MAX_VALUE; } int colorsAmt = costs[0].length; int housesAmt = costs.length; int minIndex = -1; int rolling[] = new int[colorsAmt]; int current[] = new int[colorsAmt]; for (int i = 0; i < colorsAmt; i++){ rolling[i] = costs[0][i]; if (minIndex == -1 || rolling[minIndex] > costs[0][i]){ minIndex = i; } } for (int i = 1; i < housesAmt; i++){ int newMin = -1; for (int j = 0; j < colorsAmt; j++){ if (minIndex == j){ int temp = findMinExceptIndex(rolling, minIndex); current[j] = costs[i][j] + rolling[temp]; }else{ current[j] = costs[i][j] + rolling[minIndex]; } if (newMin == -1 || current[newMin] > current[j]){ newMin = j; } } minIndex = newMin; int[] tempArr = rolling; rolling = current; current = tempArr; } return rolling[minIndex]; } private int findMinExceptIndex(int array[], int index){ int result = -1; for (int i = 0; i < array.length; i++){ if ((result == -1 || array[result] > array[i]) && i != index){ result = i; } } return result; } }