Sliding Window Algorithms

Posted on by user

The sliding window technique is a method used in algorithm design to efficiently solve problems that involve contiguous subarrays or substrings of a given size or condition. It’s particularly useful when you want to find the best, longest, shortest, or most/least frequent element in a subarray or substring that satisfies certain criteria.

How to Use Sliding Window Technique

  1. Initialization:
    • Start with two pointers or indices, typically called start and end, which initially point to the beginning of the array or string.
    • Initialize any required variable, like a sum for subarray problems or a hash table for substring problems.
  2. Expand the Window:
    • Move the end pointer to the right (increment it) to expand the window until it meets the desired condition (e.g., the sum of elements in the window equals a target value).
  3. Shrink the Window:
    • Once the condition is met or exceeded, move the start pointer to the right (increment it) to shrink the window while maintaining the condition.
    • This step is crucial for optimizing the solution, as it helps to find the minimum/maximum length of the window that satisfies the condition.
  4. Update the Solution:
    • During the expansion or shrinking phase, continually update the solution (like the maximum/minimum length of the window, the sum, etc.).
  5. Termination:
    • The process usually continues until the end pointer has gone through the entire array or string.

Conditions for Using Sliding Window Technique

Problems involving Subarrays or Substrings:

  • The technique is ideal for problems where you need to find or optimize something within a contiguous block (subarray or substring) of elements.

Linear Time Complexity Requirement:

  • It’s useful when the problem requires an efficient solution, typically in linear time.

Non-decreasing Property:

  • In the case of subarrays, the technique is particularly effective when the problem has a non-decreasing property. That is, adding a new element to the window either increases or maintains the property being checked (like sum, product, etc.).

Positive Elements (for certain problems):

  • For some specific problems, especially those involving sum, it’s easier to apply the sliding window technique when all elements are non-negative. Negative elements can complicate the non-decreasing property because adding a negative element can reduce the sum.

Examples

Maximum/Minimum Sum of Subarray of Size K:

  • Find the maximum/minimum sum of all subarrays of a specific size.
  • Maximum Sum of Subarrays of Size K:
    • Initialize a variable to hold the maximum sum and a temporary sum variable.
    • Iterate through the array, adding elements to the temporary sum.
    • Once the window size reaches k, compare the temporary sum with the maximum sum and update if necessary.
    • Slide the window by subtracting the element at the start of the window and adding the next element in the array.
  • Minimum Sum of Subarrays of Size K:
    • This follows the same approach, but you maintain a minimum sum instead of a maximum sum.
// findMaxMinSumSubarrays finds the maximum and minimum sum of all subarrays of size k
func findMaxMinSumSubarrays(arr []int, k int) (int, int) {
    if len(arr) < k {
        fmt.Println("Invalid input: Array size is smaller than the subarray size.")
        return 0, 0
    }

    maxSum, minSum := 0, 0
    windowSum := 0

    for i := 0; i < k; i++ {
        windowSum += arr[i]
    }
    maxSum, minSum = windowSum, windowSum

    for i := k; i < len(arr); i++ {
        windowSum += arr[i] - arr[i-k]
        if windowSum > maxSum {
            maxSum = windowSum
        }
        if windowSum < minSum {
            minSum = windowSum
        }
    }

    return maxSum, minSum
}

Longest Substring with K Distinct Characters:

  • Use a hashmap to keep track of characters and their frequency within the window.
// lengthOfLongestSubstringKDistinct returns the length of the longest substring with exactly k distinct characters
func lengthOfLongestSubstringKDistinct(s string, k int) int {
    if k == 0 {
        return 0
    }

    charMap := make(map[byte]int)
    maxLength := 0
    start := 0

    for end := 0; end < len(s); end++ {
        charMap[s[end]]++
        for len(charMap) > k {
            charMap[s[start]]--
            if charMap[s[start]] == 0 {
                delete(charMap, s[start])
            }
            start++
        }
        if end-start+1 > maxLength {
            maxLength = end - start + 1
        }
    }

    return maxLength
}

Smallest Subarray with a Sum Greater than or Equal to a Given Value:

  • Particularly suited for positive integers, expand the window until the sum meets the condition, then shrink it to find the minimum length.
// findSmallestSubarrayWithTargetSum finds the smallest subarray length with a sum >= target
func findSmallestSubarrayWithTargetSum(arr []int, target int) int {
	minLength := math.MaxInt32
	sum := 0
	start := 0

	for end := 0; end < len(arr); end++ {
		sum += arr[end]

		// Shrink the window as small as possible while the sum is still >= target
		for sum >= target {
			if end-start+1 < minLength {
				minLength = end - start + 1
			}
			sum -= arr[start]
			start++
		}
	}

	if minLength == math.MaxInt32 {
		return 0 // Return 0 if no subarray meets the condition
	}
	return minLength
}

String Permutations:

  • Check if a string contains a permutation of another string using a sliding window with a hashmap.
// checkInclusion checks if s contains a permutation of perm
func checkInclusion(perm string, s string) bool {
	if len(perm) > len(s) {
		return false
	}

	permMap := make(map[rune]int)
	windowMap := make(map[rune]int)

	// Initialize the hashmaps with the frequency of characters in perm and the first window of s
	for _, ch := range perm {
		permMap[ch]++
	}
	for _, ch := range s[:len(perm)] {
		windowMap[ch]++
	}

	// Check if the first window is a permutation
	if equalMaps(permMap, windowMap) {
		return true
	}

	// Start sliding the window
	for i := len(perm); i < len(s); i++ {
		// Add the new character to the window
		windowMap[rune(s[i])]++
		// Remove the character that is no longer in the window
		windowMap[rune(s[i-len(perm)])]--
		if windowMap[rune(s[i-len(perm)])] == 0 {
			delete(windowMap, rune(s[i-len(perm)]))
		}

		// Check if current window is a permutation
		if equalMaps(permMap, windowMap) {
			return true
		}
	}

	return false
}

When Not to Use

  • Arrays with Negative Numbers (for sum problems):
  • As adding a negative number might decrease the sum, the non-decreasing property is violated, complicating the use of a simple sliding window.
  • Non-contiguous Problems:
  • If the problem involves non-contiguous elements or the subproblems are not related to a contiguous block of elements, the sliding window might not be the best approach.

Understanding when and how to apply the sliding window technique comes with practice. It’s often used in conjunction with other data structures like hashmaps or heaps, depending on the problem’s requirements.

Steps to use Sliding Window

The sliding window technique, often implemented using fast and slow pointers, is a powerful method for solving many coding problems, especially those involving arrays or strings. Here’s a general step-by-step approach to use this technique:

1. Understand the Problem

  • Clearly define what the problem is asking.
  • Identify if the problem is about finding a subarray or substring with certain properties (like a maximum sum, minimum length, or a specific number of distinct characters).

2. Decide on Window Type

  • Determine if a fixed-size or variable-size window is needed.
  • Fixed-size window: Used when you’re asked to find something about subarrays or substrings of a specific length.
  • Variable-size window: Used when the size of the subarray or substring isn’t specified and can vary.

3. Initialize Pointers and Other Variables

  • Initialize the start (slow pointer) and end (fast pointer) to the beginning of the array or string.
  • Initialize other necessary variables (like sum, count, hashmap for characters, etc.) based on the problem requirements.

4. Expand the Window

  • Gradually increase the size of the window by moving the end pointer.
  • Update variables (like sum, count, hashmap) with each new element included in the window.

5. Shrink the Window (for variable-size window)

  • Once the condition is met (e.g., sum exceeds a value, the count of distinct characters exceeds a limit), start shrinking the window.
  • This involves moving the start pointer forward (and updating variables accordingly) until the window no longer satisfies the condition.
  • The goal is often to find the optimal window size that meets the problem criteria (e.g., smallest subarray with a sum greater than a target).

6. Update the Solution

  • After each expansion or shrinking, update your solution variable (like max/min length, max sum, or substring itself).

7. Repeat Until the End

  • Continue expanding and/or shrinking the window until the end pointer reaches the end of the array or string.

8. Return the Result

  • After the loop, return the solution variable as the answer.

Tips

  • Be cautious about edge cases (like empty arrays or strings).
  • Pay attention to the initialization and updating of variables.
  • Understand when to use a fixed-size versus a variable-size window.
  • Think about the implications of array/string elements being negative, zero, or positive.
  • Practice different problems to get comfortable with various scenarios and requirements.

Applying the sliding window technique effectively requires both understanding the core concept and practicing a variety of problems to gain familiarity with different use cases and nuances.