JavaScript Solution O(nk) Time O(1) Space


  • 0
    O

    This solution is the JavaScript version of: https://discuss.leetcode.com/topic/25489/fast-dp-java-solution-runtime-o-nk-space-o-1/2

    var minCostII = function(costs) {
      if (!costs || !costs.length || !costs[0].length) return 0;
      
      const numHouses = costs.length;
      const numColors = costs[0].length;
      
      let prevMin = 0;
      let prevSecondMin = 0;
      let prevMinIndex = -1;
      
      for (let i = 0; i < numHouses; i++) {
          let min = Number.MAX_SAFE_INTEGER;
          let secondMin = Number.MAX_SAFE_INTEGER;
          let minIndex = -1;
          
          for (let j = 0; j < numColors; j++) {
              const cost = costs[i][j] + (prevMinIndex === j ? prevSecondMin : prevMin);
              if (minIndex < 0 || cost < min) {
                  secondMin = min;
                  min = cost;
                  minIndex = j;
              } else if (cost < secondMin) {
                  secondMin = cost;
              }
          }
          prevMin = min;
          prevSecondMin = secondMin;
          prevMinIndex = minIndex;
      }
      
      return prevMin;
    };
    

Log in to reply
 

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