SLIDING WINDOW (FIXED SIZE)

Max Sum Subarray of size K:
https://www.geeksforgeeks.org/problems/max-sum-subarray-of-size-k5313/1

class Solution {
    public int maxSubarraySum(int[] arr, int k) {
        // Code here
        int start = 0;
        int end = 0;
        int sum =0;
        int max= -1;
        while(end<arr.length){
            sum = sum+arr[end];
            if(((end-start)+1)<k){
                end++;
            } else if(((end-start)+1)==k){
                max = Math.max(sum, max);
                sum = sum - arr[start];
                start++;
                end++;
            }
        }
        return max;
    }
}

First Negative in Windows of Size K:
https://www.geeksforgeeks.org/problems/first-negative-integer-in-every-window-of-size-k3345/1

Get Nivetharavi’s stories in your inbox
Join Medium for free to get updates from this writer.
Subscribe
Subscribe
Remember me for faster sign in
class Solution {
    static List<Integer> firstNegInt(int arr[], int k) {
        // code here
        int start = 0;
        int end = 0;
        
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        
        while(end < arr.length){
            if(arr[end]<0)
                queue.add(arr[end]);
            
            if(((end-start)+1)<k){
                end++;
            } else if(((end-start)+1)==k){
                if (queue.isEmpty()) {
                    result.add(0);
                } else {
                    result.add(queue.peek());
                }
                
                if(!queue.isEmpty()) {
                    if (queue.contains(arr[start])) {
                        queue.remove(arr[start]);
                    }
                }
                start++;
                end++;
            }
        }
        
        return result;
        
    }
}

Count Occurences of Anagrams:
https://www.geeksforgeeks.org/problems/count-occurences-of-anagrams5839/1

class Solution {

    int search(String pat, String txt) {
        // code here
        Map<Character, Integer> patMap = new HashMap<>();
        
        // Storing the occurence of each char of pat in the Map
        for (int i = 0; i<pat.length(); i++){
            char ch = pat.charAt(i);
            if(patMap.containsKey(ch))
                patMap.put(ch, (patMap.get(ch)+1));
            else
                patMap.put(ch, 1);
        }
        int start = 0;
        int end =0;
        int countResult = 0; // count of the occurrences of anagrams of the word 
        int count = patMap.size(); // count of the pat stored in map
        
        while(end<txt.length()){
            
            char ch1 = txt.charAt(end);
            
            if(patMap.containsKey(ch1)){
                patMap.put(ch1, (patMap.get(ch1)-1));
                if(patMap.get(ch1)==0)
                    count--;
            }
            
            if(end-start +1 < pat.length()){
                end++;
            } else if( end-start+1 == pat.length()){
                if (count==0)
                    countResult++;
                    
                char ch2 = txt.charAt(start);
                
                if(patMap.containsKey(ch2)){
                    if(patMap.get(ch2)==0)
                        count++;
                    patMap.put(ch2, (patMap.get(ch2)+1));
                
                }
                
                start++;
                end++;
            }
        }
        return countResult;
        
    }
}

K Sized Subarray Maximum:
https://www.geeksforgeeks.org/problems/maximum-of-all-subarrays-of-size-k3101/1

class Solution {
    public ArrayList<Integer> maxOfSubarrays(int[] arr, int k) {
        // code here
        int start = 0;
        int end = 0;
        
        //Using deque to removeLast/removeFirst and addLast()/addFirst()
        Deque<Integer> queue = new ArrayDeque<>();
        
        ArrayList<Integer> result = new ArrayList<>();
        
        while(end<arr.length){
            
            int num = arr[end];
            //removing all the smaller elements than num before adding the num
            while(queue.size() > 0 && queue.peekLast() < num){
                queue.removeLast();
            }
            
            queue.addLast(num);
            
            if(end - start + 1 < k){
                end++;
            } else if (end - start + 1 == k){
                
                result.add(queue.peekFirst());
                
                int startNum = arr[start];
                
                // removing the start if it was the first of queue
                if(startNum == queue.peekFirst()){
                    queue.removeFirst();
                }
                
                start++;
                end++;
            }
        }
        return result;
    }
}