C++ | Caching | Beats 98% - TC
Intuition
use array to keep track of the videos uploaded
use caching to store previous results of longest() function to avoid recalculation
Approach
our DS cont
# Intuition
- use array to keep track of the videos uploaded
- use caching to store previous results of `longest()` function to avoid recalculation
# Approach
- our DS contains a boolean array to store wether the ith video is uploaded or not, variable prefix to keep track of the largest prefix, and another variable to keep track of the total videos uploaded till now
- To find the longest prefix we need to find the first occurance in the `videos` array where the value is 0, i.e the video is not uploaded , if the `ith` element is the smallest index where value of `videos[i] = 0` then `(i-1)` will be the answer.
- For caching: instead of starting from 0 to n each time we start from `prefix` to `n`, because we know that `0 - prefix` is already occupied with `1s` as its the prefix and there is no need to check again as we are not deleting the videos, so we start from `prefix` to look for any `0s` and finally return our answer
# Complexity
- Time complexity:
O(n)

- Space complexity:
O(n)

# Code
```cpp []
class LUPrefix {
    vector<int> videos ;
    int cnt ;
    int prefix ;
public:
    LUPrefix(int n) {
        this->videos.resize(n+1,0) ;
        this->videos[0] = 1 ;
        this->cnt = 0 ;
        this->prefix = 0 ;
    }
    
    void upload(int video) {
        this->videos[video] = 1 ;
        ++cnt ;
    }
    
    int longest() {
        int i = prefix ;
        while(i <= cnt && videos[i] == 1) ++i ;
        prefix = i - 1 ;
        return prefix ;
    }
};

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix* obj = new LUPrefix(n);
 * obj->upload(video);
 * int param_2 = obj->longest();
 */
```
['C++']