Sliding window

4 minute read

The Problem

Find subarray with given sum (Nonnegative Numbers): Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

Input: arr = [1, 4, 20, 3, 10, 5], n = 33
Output: Sum found between indexes 2 and 4
Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33

The Solution

Since a continuous sub array is defined between a start and end index, we can find all subarray and calculate the sum.

for each start index
	for each end index from start to length(arr)
		calculate sum of arr[start:end]

The complexity will be quadratic. We can in fact do better. We observe that:

  1. At every start and end indexes, if the sum of arr[start:end] < n, we obviously need to move the end index forward.
  2. However, if the sum of arr[start:end] > n, then there is no point to calculate the sum of arr[start:end+1], arr[start:end+2], etc. What we should do is to move the start index forward.

sliding-window

For example, in the example above, we keep moving end index in step 1,2,3,4 since the sum is less than 33. At step 5 and 6, the sum is more than 33 and so we move the start index. Finally at step 7, we found the desired subarray. It seems that what we need is 2 variable “start” and “end” for this technique.

def find_subarray(nums, n):

	current_sum = 0
	start = 0
	for end in range(len(nums)):
		current_sum += nums[end]
		while current_sum > n and start < end and start < len(nums):
			current_sum -= nums[start]
			start += 1
		if current_sum == n:
			return [start,end]

	return None
func findSubarray(nums []int, n int) (int,int,bool) {
	var start, end int
	currentSum := 0
	start = 0
	for end, _ = range nums {
		currentSum += nums[end]
		for currentSum > n && start < end && start < len(nums) {
			currentSum -= nums[start]
			start += 1
		}
		if currentSum == n {
			return start, end, true
		}
	}

	return 0, 0, false
}

The Analysis

Since the 2 pointers start and end move at most once, the worst complexity is O(2*n) = O(n). The challenge of this algorithm is to recognize the pattern and to implement the sliding window.

String problems and implementation pattern

The implementation of sliding window is not always straightforward, especially when it is involved strings.

Let’s look at Leetcode 438 - Find All Anagrams in a String: Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

The question is an application of sliding window technique at medium level.

def all_anagrams(s, p):

	#define hashmap
	hm = {}
	for c in p:
		hm[c] = hm.get(c, 0) + 1
	
	# define counter, staer and end pointers
	counter, start, end = 0, 0, 0
	# result array
	res = []

	while end < len(s):
		c = s[end]
		if c in hm:
			hm[c] -= 1
			# counter per character, since we can have duplicates
			if hm[c] == 0:
				counter +=1 
		end += 1
		#increase start when condition meets, different question will have different condition
		while counter >= len(hm):
			start_char = s[start]
			if start_char in hm:
				hm[start_char] = hm.get(start_char, 0) + 1
				if hm[start_char] > 0:
					counter -= 1

			# update result here based on condition - we can put this anywhere in code depending on question 
			if counter == len(hm):
				res.append(start)

			start += 1
		
		return res

Leetcode 567 - Permutation in String: Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False
def checkInclusion(s1: str, s2: str):
    if len(s1) > len(s2):
        return False
    s1_map = {}
    for c in s1:
        s1_map[c] = s1_map.get(c, 0) + 1 
        
    start, end, total = 0, 0, 0

    while end < len(s2):
        c = s2[end]
        if c in s1_map:
            if s1_map[c] > 0:
                total += 1
            s1_map[c] -= 1
        end += 1      
        
        if total == len(s1):
            return True 
        
        while end-start >= len(s1):                
            c = s2[start]
            if c in s1_map:
                if s1_map[c] >= 0:
                    total -= 1
                s1_map[c] += 1
            start += 1
            
    return False	

String problems

Updated:

Leave a comment