Sliding window

Algorithms are the cornerstone of programming, a critical tool that helps us solve complex problems with efficient, structured approaches. Among the broad range of algorithms, the sliding window algorithm stands out as a powerful method for handling array- or list-based problems.

Imagine it as a lens that lets us focus on a particular part of the array, moving smoothly across the entire array to understand the larger data structure. This algorithm is especially powerful for optimizing tasks related to subarrays in a list or array.

In this topic, you'll dive into the details of the sliding window algorithm. You'll learn about the main principles behind this algorithm, its various applications, and how to use it effectively to solve problems quickly and with precision. You'll look at the types of problems this algorithm is best suited for and how to spot them. By the end of this topic, you'll fully understand the sliding window algorithm and how to use it in practice.

Understanding the sliding window concept

The sliding window concept involves looking at a series of objects through a 'window' that moves along the series. In algorithm terms, the 'window' is a part of an array or list, and sliding it means moving this part within the array. The window's size may be fixed, or it might change, based on the problem.

The sliding window algorithm is mainly used to perform tasks on specific parts of the array or list. For example, it can help find a subarray that fits some conditions. This algorithm is great because it is time-efficient. It can often cut down the time complexity from $O(n^2)$ to $O(n)$, which is why many programmers like it.

Let's look at how to use the sliding window algorithm with a simple example: finding the largest sum of $k$ consecutive elements in an array. Here are the steps:

1. Initialize a window: Make a window of size $k$ starting from the first element of the array.

For instance, if you have an array $[2, 3, 5, 3, 8, 1]$ and $k=3$, your first window will be $[2, 3, 5]$.

2. Operate on the initial window: Add up the elements in the first window. This is your starting maximum sum.

If we take our example, the sum $[2, 3, 5]$ is $10$.

3. Slide the window: Move the window one element to the right. This means removing the first element of the window and including the next element of the array.

In our example, the new window is $[3, 5, 3]$.

4. Operate on the new window: Get the sum of the new window by subtracting the element that left and adding the one that came in. If this sum is greater than the previous maximum sum, then this becomes your new maximum sum.

Now, the sum of the new window $[3, 5, 3]$ is $11$, which makes the new maximum sum $11$.

5. Repeat steps 3 and 4 until you cover the whole array.

When the window gets to $[5, 3, 8]$, the sum is $15$, the highest so far; so, the maximum sum is updated to $15$.

By following these steps, you can solve different problems with the sliding window algorithm.

Longest substring without repeating characters

The sliding window concept works well for finding the longest substring without repeating characters in a string. You use a window that moves through the string, expanding when a new character appears and contracting when there's a repeated character. Below is a pseudocode to show this method:

function longestSubstring(s):
    // Create an empty dictionary to remember the last time each character appears
    window = {}

    // Set up two pointers for the start and end of the window
    start = 1
    end = 1

    // Set up maxLength to save the longest substring length without repeats
    maxLength = 0

    // Go through the string
    while end <= length(s):
        // If the character at the end of the window is new or last seen before the current start
        if s[end] is not in window OR window[s[end]] < start:
            // Save the latest appearance of the character
            window[s[end]] = end

            // If the window is wider, update maxLength
            maxLength = max(maxLength, end - start + 1)
        else:
            // If a repeat is found, move the start to one place after the character's last spot
            start = window[s[end]] + 1

        // Move the end of the window one step further
        end++

    // Give back the longest substring length without repeats
    return maxLength

In this pseudocode, $\text{start}$ and $\text{end}$ show the window's current beginning and end. $\text{window}$ keeps track of each character's last appearance. If a character repeats, you move the start of the window beyond the last location where this character showed up. This way, the window always has a part of the string with no repeats. You keep updating the longest non-repeating part and get the length as the final answer.

Maximum sum subarray of size K

The sliding window concept is perfect for solving the problem of finding the maximum sum subarray of size $k$ in an array. We have explained the idea above while talking about the sliding window. Here is the pseudocode:

// Define the function that takes an array and an integer k as input
function maxSumSubarray(array, k):
    // Initialize the start of the window and the sum of the first window
    start = 0, 
    windowSum = sum of first k elements in the array

    // Initialize maxSum to store the maximum sum of a subarray of size k
    maxSum = windowSum

    // Iterate through the array starting from the (k+1)th element
    for end from k to length(array) - 1
        // Calculate the sum of the current window by adding the next element and subtracting the first element of the previous window
        windowSum = windowSum + array[end] - array[start]

        // Update maxSum if the sum of the current window is greater
        maxSum = max(maxSum, windowSum)

        // Move the start of the window to the next element
        start++

    // Return the maximum sum of a subarray of size k
    return maxSum

In this pseudocode, $start$ and $end$ represent the beginning and end of the current window. $windowSum$ keeps track of the sum of elements in the current window. When the window slides, it calculates the sum of the new window by adding the next element and subtracting the first element of the previous window. This method avoids summing $k$ elements each time and reduces the time complexity to $O(n)$. The maximum sum of a subarray of size $k$ is updated when needed and finally returned as the solution.

Minimum window substring

The sliding window concept can be very helpful in finding the smallest window within a string that includes all characters of another string. In this scenario, the 'window' is a section of the first string. It 'slides' to cover different parts of the first string. The window expands until it covers every character of the second string, and then it shrinks from the start as long as it still has all the characters.

// Define the function that takes two strings s and t as input
function minWindow(s, t):
    // Initialize a dictionary to store how often each character appears in t
    mapT = a dictionary with frequency of each character in t

    // Set up two pointers for the start and end of the window
    start = 1 
    end = 1

    // Set up minLength to save the length of the smallest window substring
    minLength = infinity

    // Set up minStart to save the start of the smallest window substring
    minStart = 0

    // Set up counter to count how many unique characters in t are in the window right now
    counter = length(mapT)

    // Go through the string s
    while end <= length(s):
        // If the character at the window's end is in t
        if s[end] is in mapT:
            // Lower its count in mapT
            mapT[s[end]]--

            // If its count in mapT is zero, lower the counter
            if mapT[s[end]] == 0
                counter--

        // When counter is zero
        while counter == 0
            // If the current window is smaller than the smallest window found so far
            if end - start + 1 < minLength
                // Update the smallest window
                minLength = end - start + 1
                minStart = start

            // If the character at the window's start is in t
            if s[start] is in mapT
                // Raise its count in mapT
                mapT[s[start]]++

                // If its count in mapT becomes positive, raise the counter
                if mapT[s[start]] > 0
                    counter++

            // Move the window's start forward one character
            start++

        // Move the window's end forward one character
        end++

    // Give back the smallest window substring
    return s[minStart:(minStart + minLength)]

In this pseudocode, $start$ and $end$ mark the beginning and end of the current window. $mapT$ has the number of times characters in the second string show up. When a character from the second string is found, its count in $mapT$ goes down, and when it's reduced to zero, the $counter$ also goes down. When the $counter$ hits zero, all characters of the second string are in the window, and the window begins to contract from the start while still including all characters. The smallest window substring gets ongoing updates and is finally given as the answer.

Time complexity analysis

The sliding window technique is an efficient way to solve many problems, often enhancing their execution speed. Let's look at the time complexity for the examples we've talked about:

1. Longest substring without repeating characters: Using the sliding window technique, this problem has a time complexity of $O(n)$, where $n$ is the string's length. This is because you only visit each character in the string up to two times: once with the end pointer and once with the start pointer. Without the sliding window technique, a naive approach would be to check all the string's substrings, which would take $O(n^2)$. So, the sliding window technique provides a faster solution.

2. Maximum sum subarray of size K: For this problem, the time complexity is also $O(n)$, where $n$ is the array's size. The sliding window technique lets you find the sum of each window of size $k$ quickly, without adding up $k$ elements every time. Without this technique, you'd need to sum $k$ elements for each of the $(n-k+1)$ windows, leading to a $O(nk)$ time complexity.

3. Minimum window substring: Using the sliding window technique, the time needed is $O(s + t)$, when $s$ and $t$ are the lengths of the two strings. In the toughest scenario, each character in the strings is looked at once by the end pointer and once by the start pointer. Without the sliding window technique, a brute force approach would involve going through all possible substrings of the first string, which could take $O(s^2 * t)$.

In all these cases, the sliding window technique greatly cuts down on time by dodging needless calculations and using results from the previous window. This makes it a very useful tool for fixing array and string problems fast.

Conclusion

The sliding window technique is a robust algorithmic tool that combines efficiency and simplicity to solve a wide range of problems. It is based on the concept of a 'window' moving across a data structure, offering an optimized way to handle issues related to arrays and strings. This technique has real-world uses; for example, it helps smooth out data in data analysis and manage the flow of data packets in computer networks. Thus, the sliding window method is valuable in many various domains.

Through this topic, you've learned about the sliding window technique, looked at its uses, and found out how to make it work well. However, the learning doesn't end here. Keep practicing, take on new challenges, and refine your skills. With a solid understanding of the sliding window technique, you'll be ready to face any coding interview that comes your way.