Feature #10: Minimum Variation
Explore how to determine the longest stretch of consecutive days when network traffic variation stays within a defined threshold. Understand how to use two-pointer techniques along with monotonic deques to maintain maximum and minimum values efficiently. This lesson helps you develop the ability to apply these concepts to real-world network billing problems involving minimal traffic fluctuations.
We'll cover the following...
Description
We monitored a network for several days and stored the daily traffic rates the network handled in a list. When billing customers for network traffic, we want to offer a discount to the traffic profiles for which traffic the rate stays more or less constant, meaning it does not vary too much. To this end, we want to find the longest stretch of consecutive days on which the traffic variation was the least on our list. Here, we define variation in a sub-list v[i..j] as the absolute difference between the maximum element and the minimum element in the sub-list, max(t[i..j]) - min(t[i..j]). We will define the threshold minimum value against which the variation will be compared. If the traffic variation is below this threshold (for at least x number of days), we will offer a discount on the bill.
Therefore, we are looking for the days on which traffic variation is less than or equal to the defined threshold. For example, if a customer’s traffic changes by less than or equal to 5 Gbps in a five-day window, then they get a discount.
We’ll be provided with a list of integers representing the traffic while the index will represent the days. An additional threshold value will be provided. We have to return the length of the longest sublist for which traffic variation is less than or equal to this certain threshold.
The following illustration might clarify this behavior:
Solution
Since we need to compute a sub-list, we can use two pointers, start and end_var, to maintain the sublists as we traverse over the list. Using these two pointers, we’ll keep track of the maximum and minimum elements in the sub-list currently being traversed. For each sub-list that comes under the range of the start and end_var ...