Solve the problem by simulating the whole process

If you can solve the problem by simulating the whole process and the code is doable, then just do it.

Problem

904. Fruit Into Baskets

Explanation

Suppose we have fruit a and b, for the new fruit, it will have 2 cases:

• new fruit is a or b
• new fruit is NEW: it is not a and it not b

We can solve the problem by each case.

Code

struct Fruit{
    int value;
    int cnt;
    int rightmost_idx;
    Fruit( int value, int cnt, int rightmost_idx):rightmost_idx(rightmost_idx), value(value), cnt(cnt){
    }
};
class Solution {
public:
    void pickup_one_more_fruit(Fruit& fruit, int idx){
        fruit.rightmost_idx = idx; fruit.cnt ++;
    }
    void pickup_the_first_new_fruit(Fruit& fruit, int fruit_val, int idx){
        fruit.value = fruit_val;
        fruit.rightmost_idx = idx;
        fruit.cnt = 1;
    }
    int totalFruit(vector<int>& fruits) {
        Fruit a(-1,0, -1), b(-1,0, -1);
        int ret = INT_MIN;
        const int n = fruits.size();
        for (int i = 0; i < n; ++i){ 
            int this_v = fruits[i];
            if (this_v == a.value){
                pickup_one_more_fruit(a, i);
            } else if (this_v == b.value){
                pickup_one_more_fruit(b, i);
            }
            else if (a.rightmost_idx > b.rightmost_idx){ // found a new fruit, keep 'a' and overwrite 'b' with the new fruit
                    /* Need to update the a.cnt for example
                        a b a a c
                        when c comes, the a's cnt should be 2 instead of 3. 
                        We can use current idx - b's rightmost_idx -1 to update
                    */
                    a.cnt = i - b.rightmost_idx - 1;
                    pickup_the_first_new_fruit(b, this_v, i);
                   
            } else {// keep 'b' overwrite 'a' with the new fruit
                    b.cnt = i - a.rightmost_idx - 1;
                    pickup_the_first_new_fruit(a, this_v, i);
                }  
            
            ret = max(ret, a.cnt + b.cnt);
        }
    return ret ==INT_MIN? 0 : ret;
    }
};

Complexity

Time: O(n)

Space: O(1)