The DSA Toolkit: #1 Sliding Window

How to identify a Problem is a Sliding window problem?

1. It is an Array or a String question.




2. Subarray or Substring is asked in the question.




3. Either windowSize or windowCondition is given (and the other one is asked).




4. Identify the format of the problem: fixed-size Sliding Window or variable-sized window.




5. Also, the window size is calculated windowSize = (j-i+1) for any interval.

So, we have two types of sliding window questions: first, a fixed-sized window whose size is explicitly stated in the question; and second, a variable-sized window whose size is not specified in the question and depends on a condition given in the question.

1. Fixed-Size Sliding Window Format

In these types of questions, the window size will be given in the question, and we will be asked to either minimize or maximize a stated condition.

For example: “Find the maximum sum of a subarray of size k.” Here, the window size will be “k”, and we have to “maximize the sum” of the subarrays.

• windowSize → GIVEN




• condition → Maximize or Minimize
  
  

int i=0, j=0;

while (j < A.size()) {

    // Do Calculations



    if(windowSize < k) {

        // Increase Window by adding more elements

    } else if (windowSize == k){

        // Get answer from the calculations



        // Remove the calculations for element `i` (Window start element)

        // Slide Window from i gradually

    }

}

windowSize -> GIVEN

Condition -> MAXIMIZE

Problems:

• GeeksforGeeks - Max Sum Subarray of size K




• GeeksforGeeks - First negative in every window of size k




• LeetCode - Find All Anagrams in a String




• LeetCode - Sliding Window Maximum




• LeetCode - Permutation in String

2. Variable-size Sliding Window Format

In these types of questions, the window size is not specified. Instead, a condition is stated, and we have to either maximize or minimize the window based on that..

For example: “Find the Longest subarray with sum K.” Here, the condition is explicitly stated in the question that the sum should be equal to “k” (sum == k), and we have to “maximize” the window, i.e., find the longest subarray.

• condition → GIVEN




• windowSize → Maximize or Minimize
  
  

int i=0, j=0;

while (j < A.size()) {

    // Do Calculations



    if(condition < k) {

        // Increase Window if condition not met



    } else if (condition == k){

        // Get answer from calculations

        j++;

    } else { // condition >k

            while(condition >k){

                // Remove the calculations for element `i` (Window Start)

                // Slide Window from i

            }



            // Check answer at this point as well

            j++;

    }

}

Problems:

• takeUforward - Longest subarray with sum K




• GeeksforGeeks - Longest Substring with K Uniques




• LeetCode - Longest Substring Without Repeating Characters




• LeetCode - Minimum Window Substring