# 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)$.