Leetcode — 904. Fruit Into Baskets

The link to the problem: https://leetcode.com/problems/fruit-into-baskets/

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

1. Add one piece of fruit from this tree to your baskets. If you cannot, stop.
2. Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
Example 2
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Thoughts:

The description above and the examples are just copied from Leetcode. It’s hard for me to understand what it means until I read the whole thing 3 times lol

Let’s rephrase the question like —

You are given an integer array, tree, tree[i] represents the type of fruit of the ith tree. (We use different integers to represent different fruit types.) The fruit types of trees in different positions might be the same or different.
You can only pick one piece of fruit per tree. Although there’s no restriction on how many trees that you can pick the fruits from, you can only hold at most 2 different types of fruit at a time. 
Once you decide to pick one piece of fruit at tree i, you can keep picking fruits from the following trees until you found a third different type of tree. Hence, it is important to decide which tree you want to start. 
Return the maximum number of fruits you can take.

Since it’s impossible for us to know from which tree we should start to pick fruit immediately, I will always assume we MUST pick a piece of fruit at the current tree. Once we found that the current decision will violate the rule of “at most 2 different types of fruit”, then we will assume we start to pick fruit at tree j instead of at the very beginning tree. Note that if we pick the fruits from tree j to tree i, we are always following the rule.

👷For example, when the given array is [1,2,2,3,2,2].

Let’s assume 1 = apple🍎, 2 = banana🍌, 3 = pineapple🍍, so you can easily imagine and understand the scenario better.

The whole process will be like this:

🔧Step 1. We take a type 1 fruit. Currently, we have an apple in our basket: [ 🍎]

🔧Step 2. We take a type 2 fruit. Currently, we have an apple and a banana in our basket: [ 🍎, 🍌]

🔧Step 3. We take a type 2 fruit. Currently, we have an apple and two banana in our basket: [ 🍎, 🍌, 🍌]

🔧Step 4. We take a type 3 fruit. However, currently, our basket already has 2 different types of fruits. We decide to abandon the apple so that we can add one type 3 fruit into our basket. Currently, we have two banana and a pineapple: [ 🍌, 🍌, 🍍]

🔧Step 5. We take a type 2 fruit. Currently, we have three banana and one pineapple in our basket: [ 🍌, 🍌, 🍍, 🍌]

🔧Step 6. We take a type 2 fruit. Currently, we have four banana and one pineapple in our basket: [ 🍌, 🍌,🍍, 🍌, 🍌]

🚧Hence, we will get at most 5 fruits on our hands in the whole process.

In the above example, you might notice there are several things we need to know before solving this problem:

1. What are the 2 different types of fruit in our hands (or basket) when we reach tree i?
2. How do we decide which type of fruit to abandon if we see a new type of fruit?
3. How do we know the total number of fruits in our hands?

It’s not hard to answer our first two bullet points.

1. We can use variables to record the two different types of fruits that we are holding right now.
2. If we met a new type of fruit at tree i, then we should keep the type of fruit at tree i-1. Otherwise, we need to drop all the fruits in our hands to include the current type of fruit.

Let’s continue the topic of abandoning fruits. Since we decide to abandon the type of fruit, then we should DROP all the fruits that we picked before the latest time we pick the type of fruit that is not the same as the fruit at the tree i-1.
For example, if we are holding fruits like : [ 🍎, 🍐, 🍎,🍐,🍐] before we met a new type of fruit and we now decide not to accept apples in our hands, then we should only hold [🍐,🍐] after this decision.

We should always count if we met the same type of fruit in a row. When we grab another type of fruit, we will reset the count. (I think it’s kind of like the concept of the combo when we play games 🎮 🙉)

Code Logic:

We will have several variables to assist us to solve the problem:

1. type1, type2: store the two different types of fruits in our hands. Note that we will always assume type1 is the type of fruit we grabbed from the previous tree (tree[i-1]).
2. combos: count how many fruits we have met type1 fruits continually before we grab a fruit from the current tree i. For example, if the value of this variable is 2, it means both tree[i-2] and tree[i-1] contains type1 fruits and tree[i-3] contains type2 fruits.
3. curLen: calculate the total number of fruits in our hands right now.
4. max: store the maximum number of fruits that we can hold in our hands so far.

Hence, what we are going to do in the code is always trying to keep those variables updated:

• Update(or Swap) type1 and type2 if needed. Since type1 should always be the same type as tree[i-1].
• Let combos be 1 if we updated the value of type1.
• If we include a new type other than type1 and type2, then curLen needed to be reset. Note that curLen is not reset to 1 since we will still keep the type of fruit at tree[i-1].

Below is the 4ms code that beats 99% —

public int totalFruit(int[] tree) {
        int n = tree.length;
        int type1 = tree[0], type2 = -1;
        int combos = 1;//assume type1 is prev type
        int curLen = 1, max = 1;
        for(int i=1;i<n;i++)
        {
            if(tree[i] != type1 && tree[i] != type2 && type2!=-1)
            {
                max = Math.max(curLen, max);
                curLen = combos + 1;
                type2 = type1; 
                type1 = tree[i];
                combos = 1;
                continue;
            }
            if(tree[i] == type1)
                combos++;
            else //swap type1 and type2 
            {
                type2 = type1;
                type1 = tree[i];
                combos = 1;
            }
            curLen++;
        }
        return Math.max(max,curLen);
    }