Problem Understanding

The problem asks for the longest contiguous subarray (interval) in a given sequence of frequencies such that the difference between the maximum and minimum frequency in that subarray is exactly $k$. In other words, if we denote the subarray as $A[l \dots r]$, then we need:

$\text{max}(A[l \dots r]) - \text{min}(A[l \dots r]) = k.$

If there is no contiguous subarray that satisfies the above condition, the answer must be $-1$. Note that the subarray must be contiguous and the difference must be exactly $k$, not less or greater.

Solution Analysis

A very efficient way to solve this problem is by using a sliding window approach combined with data structures that help quickly retrieve the minimum and maximum elements in the current window. Here’s a breakdown of the approach:

1. Sliding Window Framework:
   Use two pointers (or indices) to represent the current subarray (window). Let the left pointer be left and the right pointer be right, initially both set to the beginning of the array.

2. Maintaining the Maximum and Minimum:
   To efficiently track the maximum and minimum elements within the current window, use two double-ended queues (deques):

   • Max deque: Maintains the elements of the current window in decreasing order. The front of this deque always contains the maximum element.
   • Min deque: Maintains the elements of the current window in increasing order. The front of this deque always holds the minimum element.

   When a new element is added as you expand the window with the right pointer, update both deques by removing elements that would no longer be useful:

   • Remove all elements from the back of the max deque that are less than the current element.
   • Remove all elements from the back of the min deque that are greater than the current element.

3. Expanding and Contracting the Window:

   • With each new element added (moving the right pointer), update the two deques.

   • Check the difference using the front elements of the two deques:

     $\text{currentDiff} = \text{max} - \text{min}$

     where max is the element at the front of the max deque and min is the element at the front of the min deque.

   • If $\text{currentDiff} > k$:
     The current window exceeds the desired difference. In this case, move the left pointer to the right (i.e., shrink the window) until the condition is satisfied (i.e., until $\text{currentDiff} \leq k$). While doing so, ensure that the corresponding elements are removed from the deques if they fall out of the window.

   • If $\text{currentDiff} = k$:
     The current window is harmonious. Record the length of this window as a candidate for the answer. Continue expanding the window to see if a longer harmonious subarray exists.

   • If $\text{currentDiff} < k$:
     This window does not yet satisfy the condition, in which case simply continue expanding the window by moving the right pointer.

4. Result Computation:
   Keep updating the maximum length from all windows that satisfy the harmony condition until the end of the array is reached. If no window meets the condition, return $-1$.

Time and Space Complexity Analysis

• Time Complexity:
  The sliding window technique ensures that each element is processed at most twice (once when the right pointer is expanded and possibly once when the left pointer is moved). The operations on the deques (pop from the back/front) are amortized $O(1)$ per element. Therefore, the overall time complexity of the solution is $O(n)$.

• Space Complexity:
  The space used by the deques is at most $O(n)$ in the worst-case scenario if all elements are either in increasing or decreasing order. Thus, the overall space complexity is $O(n)$.