The Problem: Keeping Our Servers Stable

Imagine that you are a software engineer at KodeSword, responsible for a row of servers. Each server operates at a particular voltage, represented by an integer array called voltages.

For safety, a group of neighboring servers is considered stable if the difference between its highest and lowest voltages is at most K.

In simple terms:

maximum voltage - minimum voltage <= K

But there is a twist. You have one voltage regulator that can change the voltage of any one server to any integer value you choose.

Your task is to find the maximum length of a contiguous group of servers that can be made stable using the regulator at most once.

You cannot rearrange the servers or select servers from different parts of the array. The group must remain contiguous.

Example 1: Can We Save the Entire Group?

Without changing anything, the maximum voltage is 15, and the minimum is 2.

The difference is 15 - 2 = 13, which exceeds K = 4. Therefore, the entire group is initially unstable.

But we have a regulator. What if we change the voltage 15 to 4?

Now the minimum is 2, and the maximum is 6.

6 - 2 = 4

The group is stable, and its length is 4. Since the array has only four elements, we cannot obtain a longer group.

Answer: 4

At first glance, this looks like a simple example. But how do we know which server to change when the array contains thousands of values? And how do we find the longest valid group without checking every possible subarray?

That's where the actual problem-solving begins.

Try It Yourself

Before reading the solution, take a moment to think about the problem.

Can you find a way to determine whether a group can be made stable without trying every possible replacement voltage?

Try to design an algorithm that works for an array of up to 100,000 elements.

Start Challenge -: Let's Solve It

Step 1: What Does the Regulator Actually Change?

At first, we might think we need to try many possible replacement values for every server.

For example, if we choose the server with voltage 15, should we change it to 4, 5, 6, or something else?

The key observation is that we do not need to try every possible replacement value.

Suppose we temporarily ignore the server we want to change. If the remaining voltages have a maximum-minus-minimum difference of at most K, we can set the changed server's voltage to a value between their minimum and maximum.

For our example:

The remaining minimum is 2, and the maximum is 6.

Their difference is 6 - 2 = 4, so replacing 15 with any integer between 2 and 6 makes the group stable.

We are not actually deleting a server from the final answer. We are only ignoring its original voltage while checking whether a replacement can work.

This transforms the problem into a simpler question:

What is the longest contiguous subarray whose voltage range becomes at most K after ignoring at most one element?

Step 2: Which Element Should We Change?

Consider this group:

Its range is 18 - 2 = 16.

If K = 4, the group is unstable.

Which element should we change?

Changing a middle value such as 6 will not help because the minimum and maximum remain 2 and 18.

Therefore, if the range exceeds K, we only need to consider two possibilities:

1. Change the minimum voltage.
2. Change the maximum voltage.

If neither the minimum nor the maximum is changed, the range stays exactly the same.

For [2, 6, 15, 18]:

1. Change the minimum: the remaining range is 18 - 6 = 12.
2. Change the maximum: the remaining range is 15 - 2 = 13.

Neither is at most 4, so the group cannot be fixed with one adjustment.

This observation helps us avoid testing every element in the group.

Step 3: What If an Extreme Value Appears Multiple Times?

Consider:

If we change one occurrence of 2, another 2 remains. The minimum does not change.

Similarly, changing one occurrence of a repeated maximum leaves the other occurrence in the group.

Therefore, when the range exceeds K, changing the minimum can help only if the minimum occurs exactly once. The same rule applies to the maximum.

We also need to know the next distinct minimum or maximum after changing a unique extreme.

For example:

If we ignore 2, the next minimum is 6. If we ignore 18, the next maximum is 15.

This is why tracking only the current minimum and maximum is not enough. We also need their frequencies and access to the next distinct values.

Step 4: Use a Sliding Window

We want the longest valid contiguous group, so let's maintain a window with a left boundary and a right boundary.

Start with an empty window. Move the right boundary forward one element at a time, adding each new voltage.

After adding a value, check whether the current window can be made stable.

1. If it can, keep expanding.
2. If it cannot, move the left boundary forward until the window becomes valid again.

For the original example:

The window grows as follows:

1. [2] is valid without any adjustment.
2. [2, 15] can be fixed by changing one of its values.
3. [2, 15, 6] can be fixed by changing 15.
4. [2, 15, 6, 3] can also be fixed by changing 15 to 4.

The final window has length 4.

An important property makes this approach work: if a window is valid, every smaller contiguous window inside it is also valid. We can always keep the same replacement if the changed element remains in the smaller window, or leave the smaller window unchanged if it does not.

This allows us to shrink invalid windows instead of starting over.

Step 5: Maintain the Window With a TreeMap

We need to efficiently track:

1. The minimum voltage.
2. The maximum voltage.
3. The frequency of each extreme.
4. The next distinct minimum and maximum.

Java's TreeMap stores keys in sorted order and keeps a count for each voltage.

For example, the window [2, 6, 6, 15] can be represented as:

The first key is the minimum, and the last key is the maximum.

The higherKey() method retrieves the next distinct key above a given value. The lowerKey() method retrieves the previous distinct key below a given value.

Whenever a voltage enters or leaves the window, we update its count. If its count becomes zero, we remove that key from the map.

This gives us the information required to check whether the window is valid.

Java Solution

The method name maxStableGroup is specific to this custom problem. If you use the solution on a platform that requires a particular method signature, adjust the name and parameters accordingly.

Additional Test Cases: Can You Predict the Output?

Try these examples before reading their explanations. They cover a single extreme value, decreasing values, an already-stable array, and repeated spikes.

Test Case 2: One Extreme Voltage Surge

The value 100 creates a range that is too large. But we can change that single value to 12:

The maximum is 13, and the minimum is 10.

13 - 10 = 3

The entire array is stable, so the answer is 5.

Think about it: What makes this case easier than the next one? There is only one extreme value that needs to be corrected.

Test Case 3: Decreasing Voltages

Consider the first three elements:

Their range is 50 - 30 = 20, which exceeds 15.

We can change 50 to 35, giving:

Now the range is 40 - 30 = 10, which is valid. The group has length 3.

We can also select [40, 30, 20] or [30, 20, 10], each of which has a range of 20. Changing one extreme can make either group valid.

No group of length 4 can be made stable with just one adjustment, so the answer is 3.

Think about it: The values are already ordered. Does that mean we can skip checking whether the group is valid? No. We still need to consider the range and the single permitted adjustment.

Test Case 4: No Regulator Needed

The entire array has a minimum of 5 and a maximum of 8.

8 - 5 = 3

Since 3 <= 5, the entire array is already stable. We don't need to use the regulator.

The answer is 6, the full array length.

Think about it: The regulator is available, but does that mean we must use it? No. The problem allows us to use it at most once.

Test Case 5: Alternating Voltage Spikes

Consider the first three elements:

We can change 20 to 2, giving:

The range is 2 - 1 = 1, which is valid. Therefore, a group of length 3 is possible.

Now consider a window of length 4:

There are two occurrences of 20. Changing only one of them leaves the other 20 in the group, and the range remains too large.

No length-four window in this array can be made stable with one adjustment. Therefore, the maximum length is 3.

Think about it: Why does the regulator fail here even though the array contains a fixable three-element group? Because one adjustment cannot eliminate two extreme spikes.

Complexity Analysis

Let N be the length of the array.

Time complexity: O(N log N)

Each element enters the sliding window once and leaves it at most once. Updating the TreeMap takes O(log N) time, and checking the window's validity also takes O(log N) time.

Therefore, the overall time complexity is O(N log N).

Auxiliary space complexity: O(N)

In the worst case, the TreeMap can store up to N distinct voltage values.

Final Takeaway

The most important part of this problem is understanding what the regulator can actually fix.

If the range is already within K, we keep the window. Otherwise, changing a middle value cannot reduce the range. We need to check whether changing the unique minimum or maximum makes the remaining range valid.

A TreeMap helps us track those extreme values, while a sliding window lets us find the longest valid contiguous group efficiently.

The broader lesson is simple: when a problem allows one modification, first ask which part of the condition that modification can affect. A good observation can eliminate a huge number of unnecessary possibilities.