TSECJ01 - Editorial

editorial
, ,
1

PROBLEM LINK:

Problem

Editorialist: Vishesh Sharma

DIFFICULTY -

Hard

PREREQUISITES -

Deques

EXPLANATION -

The problem asks us to find the maximum values for each subarray of size s and then print the minimum of these maximums. The main problem is to keep track of the maximum elements for each subarray of size s. Using a deque can easily solve this problem for us.

For each query, we get an integer s, and we’ll try to maintain a deque of size s where it contains the maximum element at one of its ends. We slide over the array, keeping a window of size s.

Pretend we are at index I, and the maximum element is at the end of the deque. When we add the (i+1)th element, we first delete all the elements from the deque that do not fall within the current window of size s. Then, we delete those elements that are less than the (i+1)th element and push it accordingly so that the maximum element of this window is at the end of the deque.

We maintain the answer by taking the minimum of the answer with the maximum value for each subarray for a particular s and print it at the end when all the subarrays are processed.

Code:

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

class Solution {

static int solve(int[] a,int n,int m){
    ArrayDeque<Integer> ad=new ArrayDeque<Integer>();
    int min=Integer.MAX_VALUE;
    int i=0;
    for( ; i < m; i++){
        while(!ad.isEmpty()&&a[ad.peekFirst()] < a[i])
            ad.pollFirst();
        ad.addFirst(i);
    }
    
    min=Math.min(min,a[ad.peekLast()]);
    while(i < n){
        while(!ad.isEmpty()&&ad.peekLast() <= (i-m))
            ad.pollLast();
        while(!ad.isEmpty()&&a[ad.peekFirst()] < a[i])
            ad.pollFirst();
        ad.addFirst(i);
        min=Math.min(min,a[ad.peekLast()]);
        i++;
    }
    return min;
    
}

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int q=sc.nextInt();
    int a[]=new int[n];
    for(int i=0;i<n;i++) a[i]=sc.nextInt();
    while(q-->0){
        int m=sc.nextInt();
        System.out.println(solve(a,n,m));
        }
    }
}

Time Complexity-

O(N*Q)