Sliding Window - Decoding Pattern 1

Identify the Pattern

Sliding Windows is one of the most important / most asked patterns in coding interviews, when there is a problem given to you in an interview that involves any kind of subarray or substring and you need to find the largest max/min or count then most probably it's a problem of Sliding Windows

Types

Sliding Window Problems are generally of two types

• Fixed Sized Sliding Window Problem

• Variable Sized Sliding Window Problem

Here in this article, Decoding Pattern 1 we are going to discuss the fixed-sized sliding window pattern in subarray problems and the next part will be on the sliding window pattern for substring problems

What is Fixed Size Sliding Window?

Fixed-size sliding window patterns are nothing but the problem in which we are being provided with the size of the window in the problem itself

For eg: You are given an array of size N and a number K. Return the maximum sum of a subarray of size K, the given K here is the window size

Find the first negative number in every window of size K

These kinds of problems where the size of the window is predefined are known as fixed-size sliding window patterns

I hope you are getting a taste of it now! Let's move directly to problems now

Problems Involving Fixed-Sized Sliding Windows with Arrays

Maximum Sum Subarray of size K

long maximumSumSubarray(int K, vector<int> &Arr , int N){

        long long sum = 0;
        long long maxi = INT_MIN;
        long long start = 0, end = 0;

        while(end < N){
            sum += Arr[end];
            int windowSize = end - start + 1;
            if(windowSize < K){
                end++;
            }
            else if(windowSize == K){
                maxi = max(maxi, sum);
                sum-=Arr[start];
                start++;
                end++;
            }
        }
        return maxi;
    }

Max Avg Subarray

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double sum = 0;
        double mx = INT_MIN;
        double avg = 0;
        int start = 0, end = 0;
        while(end < nums.size()){
            int windowSize = end - start + 1;
            sum += nums[end];
            if(windowSize < k){
                end++;
            }
            else if(windowSize == k){
                avg = sum/k;
                mx = max(avg, mx);                
                sum -= nums[start];
                start++;
                end++;
            }
        }
        return mx;
    }
};

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

class Solution {
public:
    int numOfSubarrays(vector<int>& nums, int k, int threshold) {
        int sum = 0;
        int mx = INT_MIN;
        int avg ;
        int count = 0;
        int start = 0, end = 0;
        while(end < nums.size()){
            int windowSize = end - start + 1;
            sum += nums[end];
            if(windowSize < k){
                end++;
            }
            else if(windowSize == k){
                avg = sum/k;
                if(avg >= threshold){
                    count++;
                }              
                sum -= nums[start];
                start++;
                end++;
            }
        }
        return count;
    }
};

Find K beauty of a Number

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        int start = 0, end =0;
        string s = to_string(num);
        int count = 0;

        while(end < s.size()){
            int wSize = end - start + 1;
            if(wSize < k){
                end++;
            }
            else if(wSize == k){
                string check = s.substr(start, k);
                int divisor = stoi(check);
                if(divisor!=0 && num % divisor == 0){
                    count++;
                }
                start++;end++;
            }
        }
        return count;
    }
};

First Negative in window of size K

vector<int> firstNegative(vector<int> arr, int n, int k) {
    int start = 0;
    int end = 0;
    deque<int> q;
    vector<int>ans;
    while(end < n){
        // if element is -ve push that in deque
        if(arr[end] < 0){
            q.push_back(arr[end]);
        }
        int windowSize = end - start + 1;
        if(windowSize < k){
            end++;
        }
        // check if deque is empty when window size hits
        // if empty push back 0 else push front element of deque
        else if(windowSize == k){
            if(q.size() == 0){
                ans.push_back(0);
            }
            else{
                ans.push_back(q.front());
                if(arr[start] == q.front()){
                    q.pop_front();
                }
            }
            start++;
            end++;
        }
    }    
    return ans;
}

Sliding Window Maximum

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int start = 0;
        int end = 0;
        vector<int>ans;
        deque<int> dq;
        while(end < nums.size()){
            int windowSize = end - start + 1;
            while(!dq.empty() && nums[end] > dq.back()){
                dq.pop_back();
            }
            dq.push_back(nums[end]);    
            if (windowSize < k) {
                end++;
            }
            else if (windowSize == k) {
                ans.push_back(dq.front());
                if(nums[start] == dq.front()){
                    dq.pop_front();
                }
                start++;
                end++;
            }
        }
        return ans;
    }
}