Sliding Window Technique

 

What is the Sliding Window Technique?

The sliding window technique is a method used to solve problems related to sequences or arrays, where you want to process a subset (or window) of elements at a time. This technique involves moving a window of fixed size across the sequence to perform calculations or check for specific conditions efficiently.

 The sliding window technique consists of two key components: window
size and window movement.

1. window size - the number of elements in the array or string that the window encompasses
2. window movement -the number of elements by which the window
   moves after each step.    

One-Dimensional Sliding Window

one-dimensional sliding window is applied on 1D array or string to solve problems in efficiently time and space complexity.

In a one-dimensional array or list, the sliding window technique involves processing a contiguous subarray (window) that slides from the start to the end of the array.

Example: Maximum Sum of Subarray

Imagine you want to find the maximum sum of a subarray of size k in an array arr.

Steps:

1. Compute the sum of the first k elements (initial window).
2.  Slide the window one position to the right: subtract the element that is left out of the window and add the new element that comes into the window.
3.  Keep track of the maximum sum encountered.

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
		return -1
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(n - k):
    	 window_sum = window_sum - arr[i] + arr[i + k]
         max_sum = max(max_sum, window_sum)

    return max_sum

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k = 3
print(max_sum_subarray(arr, k)) 
# Output: 24 (sum of subarray [7, 8, 9])

Two-Dimensional Sliding Window

Definition

In a two-dimensional matrix or grid, the sliding window technique involves processing a submatrix (window) that slides over the matrix.

Example: Sum of Submatrix

Suppose you want to find the sum of a submatrix of size k x k in a matrix matrix.

Steps:

1. Compute the sum of the first submatrix of size k x k 
2. Slide the window right: subtract the elements left out and add the new elements.
3. After finishing a row, move the window down to the next row.

Implementation:

def sum_submatrix(matrix, k):
	rows, cols = len(matrix), len(matrix[0])
	if rows < k or cols < k:
    return -1
    submatrix_sum = sum(matrix[i][j] for i in range(k) for j in range(k))
    max_sum = submatrix_sum
    for i in range(rows - k):
        for j in range(cols - k):
            for x in range(k):
                submatrix_sum -= matrix[i + x][j]
                submatrix_sum += matrix[i + x][j + k]
            max_sum = max(max_sum, submatrix_sum)

        if i < rows - k - 1:
            for j in range(k):
                submatrix_sum -= matrix[i][j]
                submatrix_sum += matrix[i + k][j]
            max_sum = max(max_sum, submatrix_sum)

    return max_sum

matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
k = 2
print(sum_submatrix(matrix, k)) 
# Output: 54 (sum of submatrix [[11, 12], [15, 16]])

Practice Problems:

leetcode:

1652. Defuse the Bomb 

643. Maximum Average Subarray I

3. Longest Substring Without Repeating Characters 

codeforce:

A. Creating Words 

C. Find and Replace