Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK

SuryaPratapK/Maximun in all subarrays of size K

Created March 27, 2020 18:47
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save SuryaPratapK/c483adb1be61d94498652f98efe87aa4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save SuryaPratapK/c483adb1be61d94498652f98efe87aa4 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Maximun in all subarrays of size K
#include <bits/stdc++.h>
using namespace std;
// A Dequeue (Double ended queue) based method for printing maximum element of
// all subarrays of size k
void printKMax(int arr[], int n, int k)
{
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
std::deque<int> Qi(k);
/* Process first k (or first window) elements of array */
int i;
for (i = 0; i < k; ++i) {
// For every element, the previous smaller elements are useless so
// remove them from Qi
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear
// Add new element at rear of queue
Qi.push_back(i);
}
// Process rest of the elements, i.e., from arr[k] to arr[n-1]
for (; i < n; ++i) {
// The element at the front of the queue is the largest element of
// previous window, so print it
cout << arr[Qi.front()] << " ";
// Remove the elements which are out of this window
while ((!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front(); // Remove from front of queue
// Remove all elements smaller than the currently
// being added element (remove useless elements)
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
// Add current element at the rear of Qi
Qi.push_back(i);
}
// Print the maximum element of last window
cout << arr[Qi.front()];
}
// Driver program to test above functions
int main()
{
int arr[] = { 12, 1, 78, 90, 57, 89, 56 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printKMax(arr, n, k);
return 0;
}
@naggycoder
Copy link
Copy Markdown

naggycoder commented May 30, 2020

I have written in java. But is giving limit limit exception.Could you please in diagnosing it

import java.util.;
import java.lang.;
import java.io.*;
class GFG
{
public static void main (String[] args)
{
Scanner scanner = new Scanner(System.in);
int T = Integer.parseInt(scanner.nextLine());

    while(T-->0){
        
        String[] inp = scanner.nextLine().split("\\s+");
        int N = Integer.parseInt(inp[0]);
        int k = Integer.parseInt(inp[1]);
        
        String[] inp1 = scanner.nextLine().split("\\s+");
        
        int[] a = new int[N];
        
        for(int i=0;i<N;i++){
            a[i] = Integer.parseInt(inp1[i]);
        }    
        int max = Integer.MIN_VALUE;
        StringBuffer result = new StringBuffer();
        
        Deque<Integer> deque = new LinkedList<>();
        int i;
        for( i=0; i<k; i++){
            while((!deque.isEmpty()) && a[i]>=a[deque.peekLast()]){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        
        for(;i<N; i++){
            
            result.append(a[deque.peekFirst()] + " ");
            
            while((!deque.isEmpty()) && deque.peek()<=i-k){
                deque.removeFirst();
            }
            
            while(!deque.isEmpty() && a[i]>=a[deque.peekLast()]){
                deque.removeLast();
            }
            
            deque.addLast(i);
        }
        result.append(a[deque.peekFirst()] + " ");
        System.out.println(result);
    }
    
 }

}

@Rashvi
Copy link
Copy Markdown

Rashvi commented Jan 13, 2021

I have written in java. But is giving limit limit exception.Could you please in diagnosing it

import java.util.; import java.lang.;
import java.io.*;
class GFG
{
public static void main (String[] args)
{
Scanner scanner = new Scanner(System.in);
int T = Integer.parseInt(scanner.nextLine());

    while(T-->0){
        
        String[] inp = scanner.nextLine().split("\\s+");
        int N = Integer.parseInt(inp[0]);
        int k = Integer.parseInt(inp[1]);
        
        String[] inp1 = scanner.nextLine().split("\\s+");
        
        int[] a = new int[N];
        
        for(int i=0;i<N;i++){
            a[i] = Integer.parseInt(inp1[i]);
        }    
        int max = Integer.MIN_VALUE;
        StringBuffer result = new StringBuffer();
        
        Deque<Integer> deque = new LinkedList<>();
        int i;
        for( i=0; i<k; i++){
            while((!deque.isEmpty()) && a[i]>=a[deque.peekLast()]){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        
        for(;i<N; i++){
            
            result.append(a[deque.peekFirst()] + " ");
            
            while((!deque.isEmpty()) && deque.peek()<=i-k){
                deque.removeFirst();
            }
            
            while(!deque.isEmpty() && a[i]>=a[deque.peekLast()]){
                deque.removeLast();
            }
            
            deque.addLast(i);
        }
        result.append(a[deque.peekFirst()] + " ");
        System.out.println(result);
    }
    
 }

}

static ArrayList max_of_subarrays(int arr[], int n, int k)
{
// Your code here
ArrayList ans = new ArrayList<>();
LinkedList max = new LinkedList<>();

    for(int i = 0 ; i < n ; i++){
        if(!(max.isEmpty()) && i-k == max.peek()){
            max.poll();
        }
           
        if((!max.isEmpty()) && arr[i]  <= arr[max.peekLast()]){
            max.addLast(i);
        }else{
            while( !max.isEmpty() && arr[i] > arr[max.peekLast()]  ){
             max.removeLast();
             
            }
           
            max.addLast(i);
        }
        if(i >= k-1)
        ans.add(arr[max.peek()]);
    }
    
    
    return ans;
}

->I try to implement in java maybe this will be helpful.
-> max is the LinkedList that contains the possible maximum elements and final answer is store in ans

@keshavck
Copy link
Copy Markdown

keshavck commented May 3, 2022

Here's the successful submission solution using Dqueue in java. O(n).

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] maxWindow = new int[nums.length-k+1];
        Deque<Integer> dque = new LinkedList();
        int left =0;int right=0;
        while(right<nums.length){
	   //Remove the last element if the current element is greater than lastly added element
            while(!dque.isEmpty() && nums[dque.getLast()] < nums[right]){
                dque.removeLast(); //remove from last
            }
	    //always add from last
            dque.addLast(right);
	    //remove the left value; coz out of window bound
	    //(i.e when window is slided remove first)
            if(left > dque.getFirst()) dque.removeFirst();
            
            //check for window formation
            if(right+1 >= k) {
                maxWindow[left]=nums[dque.getFirst()];
                left++;
            }
            right++;
        }
        return maxWindow;
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment