Debug the Fruit Into Baskets problem in Javascript using Map Object-CodePudding

I am getting stuck in below coding problem. It seems like there is a bug in Map.prototype.entries(), however I would like to have your expert comments on this

Question meaning: What is the length of longest subarray that contains up to two distinct integers?

Here is the problem statement , it's a LC problem

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets. Once you reach a tree with fruit that cannot fit in your baskets, you must stop. Given the integer array fruits, return the maximum number of fruits you can pick.

Below is my code

var totalFruit = function(fruits) {
        // create a map  of fruit type
        var fruitTypes = new Map();
        var fruitCount = 0;
        var maxFruits = 0;
        // iterate till end
        for(var indx=0; indx<fruits.length; indx  )
        {
            console.log('\nI am at index:' indx ' now and value is:' fruits[indx]);
            // add only 2 types of fruit
            if(fruitTypes.size <=2)
            {   
                
                fruitTypes.set(fruits[indx],   fruitCount);
                maxFruits = fruitCount;
                console.log('\n maxFruit count is ' maxFruits);

            }

            // if the type of fruit is more than two
            if(fruitTypes.size > 2)
            {
                const iterator1 = fruitTypes.entries();

console.log(iterator1.next().value);
// expected output: ["0", "foo"]
                                // now remove the first set of fruit 
                console.log('\nfruittype size  is: '  fruitTypes.size ' and fruit count is: ' fruitCount);
                const key = fruitTypes.keys();
                var keyToDelete = key.next().value;
                const value = fruitTypes.values();
                var valueToSubtract = value.next().value;

                
                console.log('Deleting fruit type: ' keyToDelete  ' and substracting number of fruits=' valueToSubtract);
                fruitTypes.delete(keyToDelete);
                fruitCount = fruitCount - valueToSubtract;
                console.log('\nfruittype size now is: '  fruitTypes.size ' and fruit count is: ' fruitCount);
            }

        }
        console.log("\nmaxFruits=" maxFruits ", fruitcount=" fruitCount);
        return Math.max(maxFruits,  fruitCount);
};

var fruits = [3,3,3,1,2,1,1,2,3,3,4];

console.log('\nmaximum fruit count=' totalFruit(fruits));

The code is working fine but failing for the given test case, i.e.

Input: [3,3,3,1,2,1,1,2,3,3,4] Output: 4 Expected: 5

Can someone point help troubleshooting where I did the mistake?

CodePudding user response：

This is not all fancy written in 1 line of code or anything, but it works well. You can event specify more baskets:

var totalFruit = function(fruits) {
  // create a map  of fruit type
  const nBASKETS = 2;
  let nTotalFruit = 0;
  let cur_fruit = 0;
  let nCurLongest = 0;
  let nCurFruitCnt = 0;
  let nBeginIdx = 0;
  
  for(let i = 0; i < nBASKETS; i   )
    // find longest sub-array, record its size, then remove it
    for(var indx=0; indx<fruits.length; indx  ){
      if(indx)
        if(fruits[indx] == cur_fruit)
          nCurFruitCnt   
        else {
          if(nCurFruitCnt > nCurLongest){
            nCurLongest = nCurFruitCnt;
            nBeginIdx = indx - nCurFruitCnt
          }
          nCurFruitCnt = 1;
          cur_fruit = fruits[indx]
        }
      else{ // left boundary
       cur_fruit = fruits[indx];
       nCurFruitCnt = 1;
       nCurLongest = 1;
       nBeginIdx = 0
      }

      if(indx == fruits.length - 1){ // right boundary
        if(nCurFruitCnt > nCurLongest){
            nCurLongest = nCurFruitCnt;
          nBeginIdx = indx - nCurFruitCnt
        }
            
        // processed array... remove longest sub-array
        nTotalFruit  = nCurLongest;
        fruits.splice(nBeginIdx, nCurLongest)
      }
    }
  return nTotalFruit
}
var fruits = [3,3,3,3,3,1,1,2,1,1,3,3,3,3];

console.log('\nmaximum fruit count = ' totalFruit(fruits));

CodePudding user response：

You need to keep track of the maxFruits while iterating - don't unconditionally overwrite it with maxFruits = fruitCount, instead call maxFruits = Math.max(fruitCount, maxFruits);. Otherwise, a possibly higher prior record may be lost.
With fruitTypes.set(fruits[indx], fruitCount);, you're not adding the right value - you should be adding to the current value at that index in the Map. For example, given [1, 2, 2], after the third iteration, you'd want the Map to contain

1 => 1,
2 => 2

and not

1 => 1
2 => 3

because there are two elements of type 2, not three.

But I don't think this approach is the right one, since it'd be a bit ugly to identify how many items to subtract when encountering a new time. For example, with

[1, 2, 1, 1, 3]

when iterating over the 3, you'd need to be able to identify that you need to remove both the 1 (index 0) and the 2 (index 1) - summing up to 2, while leaving the rest. The earliest key in the Map isn't necessarily the one to delete, either, as you can see by the above example.

This is how I'd do it - keep track of both the number of single consecutive types up to the current iteration (eg [3, 3, 3] -> size 3) and also the number of two-consecutive types up to the current iteration (eg [4, 3, 3, 3] -> size 4). When a different type is found, assign the single-consecutive to the two-consecutive, and take the maximum of two-consecutives found over all iterations.

const calculateFruits = (fruitTypes) => [...fruitTypes.values()].reduce((a, b) => a   b);
var totalFruit = function(fruits) {
  let consecutiveIdentical = 0;
  let consecutiveOfTwoTypes = 0;
  let currentType;
  let currentTypes = [];
  let maxFruitsSoFar = 0;
  for (const type of fruits) {
    if (!currentTypes.includes(type)) {
      consecutiveOfTwoTypes = consecutiveIdentical;
      if (currentTypes.length === 2) {
        currentTypes = [currentType, type];
        consecutiveOfTwoTypes = consecutiveIdentical;
      } else {
        currentTypes.push(type);
      }
    }
    consecutiveOfTwoTypes  ;
    if (currentType !== type) {
      consecutiveIdentical = 1;
    } else {
      consecutiveIdentical  ;
    }
    currentType = type;
    maxFruitsSoFar = Math.max(maxFruitsSoFar, consecutiveOfTwoTypes);
  }
  return maxFruitsSoFar;
}
var fruits = [33, 3, 3, 2, 1, 1, 2, 3, 3, 3, 3]

console.log('maximum fruit count='   totalFruit(fruits));

CodePudding user response：

At the first, I make a copy of fruit types,

Then for different fruits, I check the chaining data in a row

const calculate = (fruits) => {
  const typeOfFruits = [...(new Set(fruits))];
  let total = 0;

  typeOfFruits.forEach(f => {
    let NumberOfFruit = 0;
    let chain = false;

    for (let i = 0; i < fruits.length; i  ) {
      if (!(!!NumberOfFruit)) {
        if (fruits[i] === f && fruits[i   1] === f) {
          NumberOfFruit  = 1;
          chain = true;
        }
      }
      else {
        if (chain) {
          if (fruits[i] === f) NumberOfFruit  = 1;
          else chain = false;
        }
      }
    }
    total  = NumberOfFruit;
  });

    return total;
}

calculate([3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]); // 5