Java Solution O(1) Space


  • 0
    A
    public class Solution {
        public int minCostII(int[][] costs) {
            if(costs == null || costs.length == 0 || costs[0].length == 0) return 0;
            int m = costs.length;
            int n = costs[0].length;
            int minOne = -1;
            int minTwo = -1;
            int  prevOne = -1;
            int preTwo = -1;
            
            for(int j=0;j<n;j++) {
                if(prevOne == -1 || costs[0][j] <= costs[0][prevOne]) {
                    preTwo = prevOne;
                    prevOne = j;
                }
                else if(preTwo == -1 || costs[0][j] <= costs[0][preTwo]) {
                    preTwo = j;
                }
            }
            
            for(int i=1;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(j == prevOne) {
                        costs[i][j] += costs[i-1][preTwo];
                    } else {
                        costs[i][j] += costs[i-1][prevOne];
                    }
                    
                    if(minOne == -1 || costs[i][j] <= costs[i][minOne]) {
                        minTwo = minOne;
                        minOne = j;
                    }
                    else if(minTwo == -1 || costs[i][j] <= costs[i][minTwo]) {
                        minTwo = j;
                    }
                }
                prevOne = minOne;
                preTwo = minTwo;
                minOne = -1;
                minTwo = -1;
            }
            int min = Integer.MAX_VALUE;
            for(int i=0;i<n;i++) {
                min = Math.min(min, costs[m-1][i]);
            }
            return min;
        }
    }

Log in to reply
 

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