[Sliding Window] How many fruits can be put in the basket?

Problem: 904. Fruit in basket

Article directory

Question analysis
Algorithm principle analysis
- Brute force enumeration + hash table
- Sliding window optimization
- Array optimized again
the complexity
Code

Question analysis

First, let’s analyze the idea of this question

First, let’s understand the meaning through the description of the question. The question gives us a fruit array, which stores the number of fruits on each tree. When we take two baskets to pick fruits, we can choose any tree to start picking.
Although the basket can only hold one kind of fruit, that is, two baskets can only hold two kinds of fruit, the number of each fruit is not limited, so As long as there are no more than two types of fruit

Let’s take a closer look at the example. For example, this example 1, {1, 2, 1} means that there is a [Fruit No. 1] on the first tree, and there is a [Fruit No. 1] on the second tree. Fruit No. 2], and there is a [Fruit No. 1] on the third tree. So if we start picking from the first tree, we can pick 2 No. 1 fruits and 1 No. 2 fruit
See example 2, there is a [Fruit No. 0] on the first tree, a [Fruit No. 1] on the second tree, a [Fruit No. 2] on the third tree, and also a [Fruit No. 2] on the third tree. One [Fruit No. 2].
- If we start picking from the first tree, we must stop after picking the fruits [No. 0] and [No. 1].
- If we start picking from the second tree, we can pick fruits [No. 1] and [No. 2], and we can pick two fruits [No. 2]. There are 3 fruit trees in total, so we start from the second tree. It is best to start picking from a tree
I believe that after reading the above descriptions, readers should be very clear. Let’s give another example {1, 1, 1, 1, 1, 1}. For this, we can know The type of fruit picked is 1 and the quantity is 6

Then we convert this question into: Find the longest sub-array length, with no more than two types of fruits in the sub-array

Analysis of algorithm principles

Next, let’s analyze the algorithm principle of this question.

Violent enumeration + hash table

First of all, the first equivalent must be violent enumeration, starting from the first number and enumerating backward, and so on, to find the one that meets the conditions and has the longest length. Just add what you traverse to the hash table and make judgments step by step during the traversal process.
The code for the violent solution will not be shown here. Readers can try to write it themselves.

Sliding window optimization

We mainly talk about how to use [sliding window] to optimize things. For sliding windows, we know that they are based on “double pointers”, so here we will need a left pointer and a right pointer. When the right pointer moves backward, when it cannot continue to move backward, it means [left, right ]The number of fruits in this interval has reached ②, At this time we need to consider doing the [Out of the window] operation

At this time, we move the left pointer one space to the right. At this time, readers can think about what changes will occur to the current kinds?

I have listed two types below. One is the case where kinds remains unchanged, because in the process of moving backward, the type of fruit that is canceled may be in [left, right]There are still fruits of this type in this interval
The second one is the situation where kinds become smaller, which is easy to understand. If the removed fruit is not included in the [left, right] interval, it means that The variety will decrease

Correspondingly, we need to give the corresponding changes in the right pointer. If kinds does not change, right does not need to change either. Because if you move it to the right, you may increase the types of fruits; if kinds becomes smaller, then right can be moved to the right. At this time The types of fruits can be increased

Next, let us take a look at the execution process of the algorithm.

Here, there are two types of data stored in our hash table, one is the current fruit type, and the other is the number corresponding to this fruit.
So when we use the right pointer right to traverse, the corresponding number is + +. When this number is greater than 2, the window will start to appear, and the corresponding number will be leftThe number of fruits pointed to by the left pointer, but this is not reduced casually. When it is reduced to [0], it is necessary to consider deleting the corresponding fruit from the hash table.
Finally, what we have to do after the window is opened is to update the longest result.

Okay, the above is the analysis of the algorithm principles related to [Sliding Window]. For detailed code, please see [Code]

Then some students asked: Why not just talk about the algorithm related to the sliding window? Instead, we have to talk about the violent solution every time. Isn’t this unnecessary?

Classmate, you should understand that when we do algorithm questions in written examinations and interviews, we don’t think of the algorithms and data structures that need to be used as soon as we see a question. Generally, when we get a question, we usually Let’s consider the violent solution first. After thinking about it for a period of time, you will start to think about whether it can be solved by some algorithms.When we usually answer questions, the important thing is not that you can think of the algorithm right away. We are more concerned about solving the problem. process, everyone must pay special attention when practicing algorithm questions

Array optimized again

Some readers may be wondering, why should we optimize again after using [Sliding Window] for optimization? We can take a look at the results after the sliding window code is submitted.

It can be seen that the efficiency is not very high. The reason is that we frequently go in and out of the window.

So how to do an optimization?

Let’s take a look at the hint given to us by the question. The maximum number of this fruit array is $ 10^5 $. In fact, we don’t need to use a hash table to store it, but directly use [array ] to store, because each element of the array is actually a mapping, which is similar to the principle of a hash table.

We can choose to directly set the size of the array to this size, and we need to put a kinds variable in the loop to replace the number statistics of the hash table.

int hash[100001] = {<!-- --> 0 };
for(int left = 0, right = 0, kinds = 0; right < n; + + right)

Then when we encounter the number of fruits reduced to 0, we do not use erase, but directly kinds-- to control the number of fruits in the current window.

if(hash[fruits[left]] == 0)
    // hash.erase(fruits[left]);
    kinds--;

Then when we enter the loop traversal, we also need to make a judgment. If the number of fruits currently traversed is 0, we will accumulate the number of kinds

// Upon entering, if the type of fruit is found to be 0, then the type of fruit will be increased by one.
if(hash[fruits[right]] == 0)
    kinds + + ;

Then in the end, when we judge the number of fruits halfway, we only need to make a judgment on this kinds

fi(kinds > 2)

For the specific code, please refer to the [Code] section. Let’s see the execution results after submission. We can observe that the performance has indeed been greatly improved.

Complexity

Next, let’s analyze the time complexity

time complexity:

First, in terms of time complexity, for the [Sliding Window] part of the code, we use the left and right double pointers to traverse and search the entire array, and during the search process When the number of fruits > 2, you need to perform window operations, because the complexity of erase() is

O

(

n

)

O(n)

O(n), so in the worst case the complexity can reach

O

(

n

2

)

O(n^2)

O(n2)

For array optimization, although the hash table is eliminated, the counting function is lost. But we only performed the traversal operation. The intermediate loop process used the marking operation performed by kinds and did not involve erase(). Therefore, the worst complexity is because

O

(

n

)

O(n)

O(n)

Space complexity:

Regarding space complexity, the two optimization methods do not involve the application of additional space, so the space complexity is:

O

(

1

)

O(1)

O(1)

Code

Next is the code part

The first thing is the code related to [sliding window] optimization

  class Solution {<!-- -->
public:
    int totalFruit(vector<int> & amp; fruits) {<!-- -->
        int n = fruits.size();
        unordered_map<int, int>hash;

        int max_len = INT_MIN;
        for(int left = 0, right = 0; right < n; + + right)
        {<!-- -->
            // 1. Enter the window
            hash[fruits[right]] + + ;
            // When there are more than 2 types of fruits, the window starts to appear
            if(hash.size() > 2)
            {<!-- -->
                // 2. Exit the window [left cannot be moved back at this time, so the fruit needs to be deleted]
                hash[fruits[left]]--;
                // If the number of current fruit types reaches 0, delete it from the hash table
                if(hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);
                left + + ;
            }
            //update results
            max_len = max(max_len, right - left + 1);
        }
        return max_len == INT_MIN ? 0 : max_len;
    }
};

The next thing is the code about [array optimization]

class Solution {<!-- -->
public:
    int totalFruit(vector<int> & amp; fruits) {<!-- -->
        int n = fruits.size();
        //unordered_map<int, int> hash;
        int hash[100001] = {<!-- --> 0 };
        int max_len = INT_MIN;
        for(int left = 0, right = 0, kinds = 0; right < n; + + right)
        {<!-- -->
            // Once the judgment is made, if the type of fruit is 0, then the type of fruit will be increased by one.
            if(hash[fruits[right]] == 0)
                kinds + + ;
            // 1. Enter the window
            hash[fruits[right]] + + ;
            // Determine whether there are more than two types of fruits in the current hash table
            if(kinds > 2)
            {<!-- -->
                // 2. Exit the window
                hash[fruits[left]]--;
                // If the current number of fruits is 0 after exiting the window, delete the fruit from the hash table
                if(hash[fruits[left]] == 0)
                    // hash.erase(fruits[left]);
                    kinds--;
                left + + ;
            }
            // 3. Update the maximum length
            max_len = max(max_len, right - left + 1);
        }
        return max_len == INT_MIN ? 0 : max_len;
    }
};