Java 3ms solution without modifying the costs matrix


  • 0
    W

    The idea is basically the same as other solutions. The point of this one is that I use a minExclude function which returns the min value excluding current position.

    public class Solution {
        public static int minCostII (int[][] costs) {
        	if (costs == null || costs.length < 1 || costs[0].length < 1) return 0;
        	int n = costs.length;
        	
        	int[] minCosts = new int[costs[0].length];
        	for (int i = 0; i < n - 1; i++) {
        		arrayAdd(minCosts, costs[i]);
        		minCosts = minExclude(minCosts);
        	}
        	arrayAdd(minCosts, costs[n-1]);
        	
        	int min = minCosts[0];
        	for (int c : minCosts)  if (c < min) min = c;
        	return min;
        }
        
        public static void arrayAdd(int[] arr1, int[] arr2) {
        	for (int i = 0; i < arr1.length; i++) {
        		arr1[i] += arr2[i];
        	}
        }
        
        // min excluding item i = min(0, i-1) + min(i+1,n)
        public static int[] minExclude(int[] nums) {
        	int[] mins = new int[nums.length];
        	mins[0] = Integer.MAX_VALUE;
        	for (int i = 1; i < nums.length; i++) {
        		mins[i] = Math.min(nums[i-1], mins[i-1]);
        	}
        	
        	int minRight = Integer.MAX_VALUE;
        	for (int i = nums.length - 2; i >= 0; i--) {
        		minRight = Math.min(minRight, nums[i+1]);
        		mins[i] = Math.min(minRight, mins[i]);
        	}
        	
        	return mins;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.