Queries with Fixed Length

Sort by

recency

|

143 Discussions

|

  • + 0 comments
    def solve(arr, queries):   
        mins = []
    
        for k in queries:
            current_window = deque()
            maxs = []
            for i in range(len(arr)):
                if current_window and current_window[0] < i - k + 1:
                    current_window.popleft()
    
                while current_window and arr[current_window[-1]] < arr[i]:
                    current_window.pop()
    
    
                current_window.append(i)
    
                if i >= k -1:
                    maxs.append(arr[current_window[0]])
            mins.append(min(maxs))
    
        return mins
    
  • + 0 comments

    C++ implementation using a modified add/pop operation in deque :

    void add(deque<int>& q, int v){
        while(!q.empty() && q.back() < v) q.pop_back();
        q.push_back(v);      
    }
    
    int getMax(deque<int>& q){ return q.front(); }
    
    void pop(deque<int>& q, int rv){
        if(!q.empty() && rv == q.front()) q.pop_front();
    }
    
    int computeMinOfSubarrays(vector<int> maxs){
        int ans = INT_MAX;
        for(auto m : maxs) ans = min(ans, m);
        return ans;    
    }
    
    vector<int> solve(vector<int> arr, vector<int> queries) {
       vector<int> mins;
       for(auto subArrayLength : queries){
           deque<int> q; vector<int> maxs; 
           int size = 0;
           int toBeRemoved = 0;
           for(int i=0; i<arr.size(); ++i){
               add(q, arr[i]);
               size++;
               if(size == subArrayLength){
                   size -= 1;
                   maxs.push_back(getMax(q));
                   pop(q, arr[toBeRemoved++]);
               }
           }
           mins.push_back(computeMinOfSubarrays(maxs));
       } 
       return mins; 
    }
    
  • + 0 comments

    It can be optimized with dp, but since it is with deque...

    int Solve(vector<int> arr, int d)
    {
        int mn, mx;
        deque<int> mmi;
        mmi.push_back(0);
        for(int i = 1; i < d; mmi.push_back(i), i++)
            while(!mmi.empty() && arr[mmi.back()] < arr[i])
                mmi.pop_back();
        mn = mx = mmi.front();
        for(int i = d; i < arr.size(); i++)
        {
            if(mx == i - d)
                mmi.pop_front();
            while(!mmi.empty() && arr[mmi.back()] <= arr[i])
                mmi.pop_back();
            mmi.push_back(i);
            mx = mmi.front();
            mn = arr[mx] < arr[mn] ? mx : mn;
        }
    
        return arr[mn];
    }
    
  • + 0 comments

    Clean solution in C++

    vector<int> solve(vector<int> arr, vector<int> queries) {
        vector<int> res;
        int N = arr.size();
        for (int i = 0; i < queries.size(); i++) {
            int d = queries[i];
            vector<int> q;
            int mini = INT32_MAX; 
            for (int j = 0; j < N;j ++){ 
                // q is a decreasing vector
                while (!q.empty() && q.back() < arr[j]) {
                    q.pop_back();
                }
                q.push_back(arr[j]);
                if (j + 1 >= d) {
                    if (mini > q[0]) {
                        mini = q[0];
                    }
                    if (q[0] == arr[j+1-d]) {
                        q.erase(q.begin());
                    }
                }
            } 
            res.push_back(mini);
        }
        
        return res;
    }
    
  • + 1 comment
    from collections import deque
    def solve1(arr,dis):
        ans=[];d=deque();i=0;j=0
        while j<len(arr):
            while d and d[-1]<arr[j]:
                d.pop()
            d.append(arr[j])
            if j-i+1<dis:
                j+=1
            else:
                ans.append(d[0])
                if d[0]==arr[i]:
                    d.popleft()
                i+=1
                j+=1
        return min(ans)
        
    
    def solve(arr, queries):
        res=[]
        for i in queries:
            if i==1:
                res.append(min(arr))
            elif i==len(arr):
                res.append(max(arr))
            else:
                res.append(solve1(arr,i))
        return res