DSA: Sliding Window Technique

What is the Sliding Window Technique?

The Window Sliding Technique is a technique for reducing the time complexity of algorithms using nested loops. We can avoid nested loops and obtain greater performance by traversing the array with a single loop and sliding a window over it.

Use of Sliding Window Technique for 2D Arrays:

A sliding window is a technique used to process sub-arrays or sub-matrices of an array or matrix sequentially. In a 2D array, a sliding window can be used to traverse all possible sub-matrices of a given size.

How to use a Sliding Window?

Here are the general steps to use a sliding window:

1. Define the size of the window: Determine the size of the window that will be used to traverse the array or matrix. This will depend on the specific problem we are trying to solve.
2. Initialize the window: Define the initial position of the window. This will typically be at the first element of the array or matrix.
3. Process the subarray or submatrix: Use the values within the window to perform the desired operation, such as calculating the sum, finding the maximum or minimum value, or performing some other computation.
4. Move the window: Slide the window to the next position in the array or matrix, typically by shifting it by one element.
5. Repeat steps 3 and 4: Continue processing the subarrays or submatrices until the window has reached the end of the array or matrix.
6. Return the result: Return the result of the computation performed on the subarrays or submatrices.

Example:

• Given a matrix and a window size of k, output the maximum/minimum value in the 2D sliding window with a k by k window size.

public static int[][] slidingWindowMax(int[][] matrix, int k) {
    int numRows = matrix.length;
    int numCols = matrix[0].length;
    int[][] result = new int[numRows - k + 1][numCols - k + 1];

    for (int i = 0; i <= numRows - k; i++) {
        for (int j = 0; j <= numCols - k; j++) {
            int maxVal = Integer.MIN_VALUE;
            for (int x = i; x < i + k; x++) {
                for (int y = j; y < j + k; y++) {
                    maxVal = Math.max(maxVal, matrix[x][y]);
                }
            }
            result[i][j] = maxVal;
        }
    }

    return result;
}

public static int[][] slidingWindowMin(int[][] matrix, int k) {
    int numRows = matrix.length;
    int numCols = matrix[0].length;
    int[][] result = new int[numRows - k + 1][numCols - k + 1];

    for (int i = 0; i <= numRows - k; i++) {
        for (int j = 0; j <= numCols - k; j++) {
            int minVal = Integer.MAX_VALUE;
            for (int x = i; x < i + k; x++) {
                for (int y = j; y < j + k; y++) {
                    minVal = Math.min(minVal, matrix[x][y]);
                }
            }
            result[i][j] = minVal;
        }
    }

    return result;
}

Here, the slidingWindowMax function takes in a 2D array matrix and a window size k, and returns a new 2D array containing the maximum value in each k x k submatrix of the input array. The slidingWindowMin function does the same thing but returns the minimum value instead.

• The function iterates through all potential starting indices of the k x k submatrices in the input array using two nested loops.
• Two nested loops are utilized for each beginning index to iterate over the submatrix components and obtain the maximum/minimum value using the Math.max or Math.min functions.
• The resulting maximum/minimum value is then stored in the relevant location in the output 2D array result.

• Given a string s consisting only of characters a, b and c. Return the number of substrings containing at least one occurrence of all these characters a, b and c.

public static int countSubstrings(String s) {
    int left = 0, right = 0;
    int count = 0;
    int[] freq = new int[3];
    int n = s.length();

    while (right < n) {
        freq[s.charAt(right) - 'a']++;

        while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
            count += n - right;
            freq[s.charAt(left) - 'a']--;
            left++;
        }

        right++;
    }

    return count;
}

To represent the beginning and finish of the window, we used two pointers to the left and right, respectively. We also use a three-dimensional array freq to keep track of the frequency of each character in the current window.

• Both pointers are initially set to 0, and the frequency array is initialized to all zeros.
• The right pointer is then moved to the right until we discover a substring that contains all three characters.
• When we find a substring that has all three characters, we can move the left cursor to the right until we no longer have a substring that contains all three characters.
• At this point, we multiply our count by the number of substrings that finish at the current right pointer, which is equal to the length of the substring from right to the end of the string.
• We then move the right pointer to the right and repeat the operation until the full string has been processed.

Note: also read about DSA: 2D Array

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py