The EndGame : Maximum Sliding Window || newton school coding contest questions || newton school assignment solution

 The EndGame : Maximum Sliding Window

  Contributed by : Shweta Gurang

Problem Statement You are given an array A of size N. You have to print the maximum in every K-sized subarray from the left to the right in the array A. More formally, you have to print N - K + 1 integers X1, X2, ..., XN-K+1 such that Xi (1 <= i <= N - K + 1) is the maximum element in the subarray Ai, Ai+1, ..., Ai+K-1. Input 1. The first line contains an integer N, denoting the size of the array. 2. The second line has N space- separated integers of the array A. 3. The third line contains integer K, denoting the size of the sliding window Constraints : 1 <= N <= 10^5 10^-4 <= A[i] <= 10^4 1 <= K <= N Output Print the max of K numbers for each position of sliding window Example Sample Input:- 8 1 3 -1 -3 5 3 6 7 3 Sample Output:- 3 3 5 5 6 7 Explanation:- Window position Max - - - - [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 Sample Input:- 1 1 1 Sample Output:- 1

 

 

import java.io.*; // for handling input/output import java.util.*; // contains Collections framework // don't change the name of this class // you can add inner classes if needed class Main {     public static void main (String[] args) {                       // Your code here                       Scanner sc = new Scanner(System.in);                       int t =1;                       while(t-->0){                           int n = sc.nextInt();                           int arr[] = new int[n];                           for(int i = 0;i<n;i++){                           arr[i] =  sc.nextInt();                       }                       int k = sc.nextInt();                       ArrayList<Integer> res = new Solution().max_of_subarrays(arr , n , k);                       for(int i = 0;i<res.size();i++)                             System.out.print(res.get(i)+" ");                         System.out.println();     }     } } class Solution{     static ArrayList<Integer> max_of_subarrays(int arr[],int n,int k){         LinkedList<Integer>list = new LinkedList<>();         ArrayList<Integer> res = new ArrayList<>();         for(int i = 0 ; i<k;i++){             while(!list.isEmpty() && arr[i]>=arr[list.peekLast()]){                 list.removeLast();             }             list.add(i);         }         res.add(arr[list.peek()]);         for(int i=k;i<n;i++){             while(!list.isEmpty()&& list.peek()<=(i-k)){                 list.removeFirst();             }             while(!list.isEmpty() && arr[i]>=arr[list.peekLast()]){                 list.removeLast();             }             list.addLast(i);                 res.add(arr[list.peek()]);             }             return res;         }     }