Image from techgrabyte.com

This blog is a part of my “15 days cheat sheet for hacking technical interviews at big tech companies”. In this blog, we discuss how sliding window technique can help to simplify the code and reduce the time complexity.

Sample Question 1

Let’s start with the following interview question:

Given an array of integers and a number k.
Return the highest sum of any k consecutive elements in the array.Examples:Input: arr = [1, 5, 2, 3, 7, 1], k = 3
Output: 12 (the sum of subarray [2, 3, 7])Input: arr = [5, -3, 7, -6, 8], k = 2
Output: 4 (the sum of subarray [-3, 7])Input: arr = [5, -3, 7, -6, 8], k = 3
Output: 9 (the sum of subarray [5, -3, 7] or [7, -6, 8])

Brute Force Approach

The most intuitive way is to find all possible consecutive subarray of k elements, sum up and compare them. This method requires nested for loop, the outer for loop iterates through the starting index of the subarray and the nested loop calculates the sum of the subarray.

The time complexity is O(k*n) as it contains two nested loops. It is very inefficient to traverse through subarray each time to calculate the sum, so if we want to improve the performance, we need a quicker method to find the sum.

Sliding Window Approach

A window is formed over some part of data, and this window can slide over the data to capture different portions of it. When a window slides, only two elements change. The oldest one drops off, and the newest one comes into the frame.

In the brute force approach, the inefficient part is that for any two consecutive subarrays of size k, the overlapping part (which contains k-1 elements) is evaluated twice. By using the sliding window approach, we can get rid of that and calculate the sum in O(1) using the sum of previous consecutive subarray.

You can also implement the sliding window approach with two pointers left & right as the following code

The time complexity is now linear, O(n), as we need only one loop.

Sample Question 2

Let’s take a look another question:

Given a string, find the length of the longest substring without repeating characters.
Full description at https://leetcode.com/problems/longest-substring-without-repeating-characters/Examples:Input: "pwwkew"
Output: 3 (the substring "wke" or "kew")Input: "abcabcbb"
Output: 3 (the substring "abc" or "bca" or "cab")Input: "bbbbb"
Output: 1 (the substring "b")

Brute Force Approach

The naive approach is to check all substrings one by one and find the longest one which has all unique characters.

The time complexity is O(n³) as we need O(n²) to list all substrings and for each substring, we need O(n) to check if the characters are all unique or not.

Sliding Window Approach

In the brute force approach, for each substring, we need O(n) to check if the characters are all unique or not. By using a hash map as a window to record the number of occurrences of characters in the substring, we can check the substring Sᵢⱼ by checking if the character at jin the window [i, j-1] or not. And that just needs O(1)

Moreover, we don’t need to check all substrings. We can start from the index 0, sliding to the right as long as the characters in the substring are still unique. If we encounter the repeating character, we can drop off some left characters to make them unique again.

The time complexity is O(2n)=O(n) as in the worst case each character will be visited twice by left and right.

Recommended questions

You can practice the sliding window technique with the following questions:

Conclusion

The power of the sliding window algorithm is to prevent unnecessary iterations over a collection. When you are asked to find or calculate something among all the contiguous subarrays (or sublists), it is the hint for using sliding window technique. In some problems, the size of the sliding window is not fixed (such as sample question 2), and you have to expand or shrink the window based on the problem constraints.

The abstract code of sliding window approach can be summarised as the following:

left = 0
right = 0while right < n:
    window.add(s[right])
    right += 1    while (condition):
        window.remove(s[left])
        left += 1