We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Queries with Fixed Length
  5. Discussions

Queries with Fixed Length

Sort by

recency

|

144 Discussions

|

  • muhibpasha786
     + 0 comments

    import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.regex.*;

    class Result {

    /*
 * Complete the 'solve' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY arr
 *  2. INTEGER_ARRAY queries
 */

public static List<Integer> solve(List<Integer> arr, List<Integer> queries) {
    List<Integer> results = new ArrayList<>();
    int n = arr.size();

    for (int d : queries) {
        Deque<Integer> dq = new LinkedList<>();
        int minOfMax = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            // remove indices out of this window
            while (!dq.isEmpty() && dq.peekFirst() <= i - d) {
                dq.pollFirst();
            }

            // maintain decreasing order
            while (!dq.isEmpty() && arr.get(dq.peekLast()) <= arr.get(i)) {
                dq.pollLast();
            }

            dq.offerLast(i);

            // when window size is ready
            if (i >= d - 1) {
                int currentMax = arr.get(dq.peekFirst());
                minOfMax = Math.min(minOfMax, currentMax);
            }
        }

        results.add(minOfMax);
    }

    return results;
}

    }

    public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

    int n = Integer.parseInt(firstMultipleInput[0]);
    int q = Integer.parseInt(firstMultipleInput[1]);

    String[] arrTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
    List<Integer> arr = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        int arrItem = Integer.parseInt(arrTemp[i]);
        arr.add(arrItem);
    }

    List<Integer> queries = new ArrayList<>();
    for (int i = 0; i < q; i++) {
        int queriesItem = Integer.parseInt(bufferedReader.readLine().trim());
        queries.add(queriesItem);
    }

    List<Integer> result = Result.solve(arr, queries);

    for (int i = 0; i < result.size(); i++) {
        bufferedWriter.write(String.valueOf(result.get(i)));
        if (i != result.size() - 1) {
            bufferedWriter.write("\n");
        }
    }

    bufferedWriter.newLine();

    bufferedReader.close();
    bufferedWriter.close();
}

    }

  • manceraaxel
     + 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

  • BreaklessCS
     + 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; 
}

  • daniel_leovel
     + 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];
}

  • dangquoctienvktl
     + 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;
}