Algorithmic Problem Solving Techniques: Part-1, Sliding Window

Generated using deepai.org

This is the first part of a series of articles in which we are going to learn about some data structures and algorithmic techniques that can be used to solve some common problems we encounter during a job interview, competitive programming, or even in daily work.

The first couple of techniques and problems are going to be based on linear data structures like linked lists and arrays.

Disclaimer: These articles aren’t meant to teach you algorithm design in an academic manner. I don’t even have the knowledge to be able to teach that. We are just going to see some common problems and effective solutions and analyze their efficiencies.

Prerequisites

I have assumed that you are familiar with basic data structures like array, dynamic array(list), linked list, stack, queue, …

Some basic data structures you need to be familiar with

You also need to be familiar with the asymptotic notation that we are going to use to describe the running time of an algorithm and the space it consumes. If you are not familiar check this out.

Asymptotic Notation

Sliding Window

Our first technique is called sliding window. Let’s see an example.

Suppose that we are given this array of size n=6

[6, 2, 4, 8, 0, 3]

We are asked to find the maximum sum of contiguous sub-array of size m=3. See it on Leetcode.

The answer is 14. The sub-array: [2, 4, 8]

Naive Approach

In a brute-force approach we can start from the first element, calculate the sum, move forward one step, calculate the sum again, repeat.

Brute-Force solution

Let’s analyze the running time of this algorithm.

There are n items in the array. Sub-array size is m. We need to move forward one step each time until we reach the end so (n-m+1) iterations. In each iteration we need to calculate the sum of m items so (n-m+1)*m = nm -m² + m which results in O(nm). Well, not so good!

Can you see the in-efficiency of this algorithm?

If you pay attention to the diagram above, we are re-calculating some elements each time we move forward. For example in the beginning we have calculated 6+2+4 then we move one step forward and calculate 2+4+8 as you can see 2+4 was already calculated before in the previous iteration. So, we can re-use these calculations from the previous iteration. Let’s see how!

Better Solution

Sliding Window

As you can see in the diagram above, each time we move forward, we can remove the previous element leaving the window and add the element entering the window.

Analysis: It’s pretty obvious that we only need to go through the array once so we have O(n). Nice!

Simple implementation in Golang

func maxSum(nums []int, m int) int {
 var max int
 var currentSum int
 var start int

 for i, n := range nums {
  currentSum += n

  // Don't slide if we haven't reached the window size (first elements).
  if i < m-1 {
   continue
  }

  max = int(math.Max(float64(max), float64(currentSum)))

  // Slide window.
  currentSum -= nums[start]
  start++
 }

 return max
}

Conclusion

In this post we learned how to use a simple trick to avoid re-calculating and to be able to re-use previous results. This simple trick reduced the time-complexity of our solution from O(mn) to O(n) which is pretty interesting!

That’s it! I hope you enjoyed this post. See you in the next one!

Happy creating bugs :D