avatarTuan Nhu Dinh

Summary

The article discusses the sliding window technique as an efficient approach for solving coding interview questions involving arrays and strings, such as finding the highest sum of any k consecutive elements or the length of the longest substring without repeating characters.

Abstract

The article is part of a "15 days cheat sheet for hacking technical interviews at big tech companies" and focuses on the sliding window technique, a method to optimize code and reduce time complexity. It contrasts the brute force approach with the sliding window approach for two sample coding interview questions. The first question involves finding the highest sum of k consecutive elements in an array, where the sliding window technique improves the time complexity from O(k*n) to O(n). The second question asks for the length of the longest substring without repeating characters, where the sliding window approach reduces the time complexity from O(n³) to O(n). The article also provides code examples and recommends additional problems to practice the technique, emphasizing the sliding window's ability to prevent unnecessary iterations and its adaptability to variable window sizes.

Opinions

  • The author believes that the sliding window technique is crucial for improving performance in coding problems involving contiguous subarrays or substrings.
  • The brute force approach is deemed inefficient due to its higher time complexity and redundant calculations.
  • The sliding window approach is presented as a more efficient and elegant solution to such problems.
  • The article suggests that familiarity with the sliding window technique can be a significant advantage in technical interviews.
  • The author endorses ZAI.chat as a cost-effective AI service alternative to ChatGPT Plus (GPT-4), indicating a belief in its performance and value for money.

Using sliding window technique to solve coding interview questions.

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 j in 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 = 0
while right < n:
    window.add(s[right])
    right += 1
    while (condition):
        window.remove(s[left])
        left += 1
Coding Interviews
Sliding Window Algorithm
Algorithms
Computer Science
Coding
Recommended from ReadMedium