Sliding Window

In technical problems, we usually find ourselves need to iterate an array to find an information; we scan each array member one by one. The problem is sometimes the information we want is not in the array member we scan. Maybe we need to compare the current value and previous value.

The obvious answer to that problem is that we take two value array at once and evaluate it in each loop then we move it one by one like in the original loop. We call it two member sliding window. The original for loop is one member sliding window.

Our goal is how we create a program that able to handle n-member sliding window.

This approach have interesting properties that the length of the scan is different. One sliding window have length same as array length. Two slidng window on the other hand have array length minus one length. For example, let's say we have four lenght array with member [1,2,3,4]. If we use one member sliding window we will have 1, 2, 3, 4; like in normal for loop. If we use two member sliding window, we will have 1,2, 2,3, 3,4; which generate three member. Let's create our program

Base Function

func slidingWindow(input []int, member int) [][]int {
    return [][]int{}
}

Above is the base function of the sliding window.

• input represent member we want to convert to sliding window.
• member represent n in n-member sliding window; how much member in one window.
• [][]int is the output. Each of array member should have number of member

Validation

First, we need to check whether the member is larger that input. We can took two approach here, we can make it error if member is larger than len(input) or we can make it equal to len(input). We took the later approach because we dont have room for error type in slidingWindow base function.

func slidingWindow(input []int, member int) [][]int {
    if member > len(input) {
        member = len(input)
    }
    return [][]int{}
}

Preparation

Second, now we want to fill the window. We can create our empty array

func slidingWindow(input []int, member int) [][]int {
    if member > len(input) {
        member = len(input)
    }
    totalMember := len(input) - (member - 1)
    final := make([][]int, totalMember)
    return [][]int{}
}

The part len(input) - (member - 1) is decide how many sliding window member we have. For example, if we have four member with two member sliding window, we would have $4 - (2 - 1)$ which equal to $3$; same as my previous example.

Filling Window

Third, we want to fill the array

func slidingWindow(input []int, member int) [][]int {
    if member > len(input) {
        member = len(input)
    }
    totalMember := len(input) - (member - 1)
    final := make([][]int, totalMember)
    for i:=0;i<totalMember;i++ {
        final[i] = input[i:i+member]
    }
    return final
}

We loop using totalMember for the boundaries so it wont out of bond when we fill final. Golang have slicing similar to Python which use [n:m] notation. n represent the first member we want to take. m represent the end of array we want to take but it wont take it as an array member.

For example, an array [1,2,3,4] and [0:2] would have result [1,2]. Another example is if we take [2:4], it would have result [3, 4].

The totalMember have -1 so then input[i:i+member] would never out of bound because i largest possible number is totalNumber minus one and totalNumber add with member would only equal len(input) - 1 which is last position index of input.

Generalization

The sliding windows should be applicable to all type as long as it is come in form of an array. We can generalize the sliding window function as

func slidingWindow[T comparable](input []T, member int) [][]T {
	if member > len(input) {
		member = len(input)
	}
	totalMember := len(input) - (member - 1)
	final := make([][]T, totalMember)
	for i := 0; i < totalMember; i++ {
		final[i] = input[i : i+member]
	}
	return final
}

By using generics, we can input any array and generate a sliding window array with it.

Conclusion

The downside of this algorithm is that we end up with two array that convey same information which is take memory space. From speed perspective, we only have one loop that decided by member and input. The lowest possible number of member would generate most loops because total member--which govern the loop--depends on minus value of member. So we can safely assume that worst possible scenario for this algorithm is $O(n)$ where $n$ is total member of input.