Overview

This problem asks you to find the interval of consecutive points that contains the fewest points, among all intervals where the sum of absolute differences in elevation between adjacent points (total elevation change) is at least \(K\).

Analysis

First, since this problem deals with “elevation differences between adjacent points,” it becomes clearer if we precompute the elevation differences for each pair of adjacent points and create a new array. Specifically, consider an array \(D\) of length \(N-1\) where \(D_i = |A_{i+1} - A_i|\). Then, this problem can be rephrased as “Find the shortest length of a contiguous subarray of array \(D\) whose sum of elements is at least \(K\).”

If we consider a naive approach (brute force) that tries all combinations of start point \(l\) and end point \(r\), the number of combinations is approximately \(N^2 / 2\). Given the constraint \(N \le 2 \times 10^5\), the number of computations would reach tens of billions, exceeding the time limit (TLE).

Here, we note that the elements of array \(D\) are all non-negative. If all elements are non-negative, extending the interval to the right (shifting the end point rightward) monotonically increases the sum, and shrinking the interval from the left (shifting the start point rightward) monotonically decreases the sum. When such a property holds, we can use a technique called “Two Pointers” to eliminate unnecessary searches and find the answer in a very fast \(O(N)\) time.

Algorithm

1. Handling corner cases When \(N = 1\), no movement is possible, so the total elevation change is always \(0\). Since \(K \ge 1\), the condition can never be satisfied. Immediately output -1.
2. Creating the difference array Create an array \(D\) of length \(N-1\). Set \(D_i = |A_{i+1} - A_i|\).
3. Search using two pointers Initialize a variable left representing the left end of the interval to \(0\), a variable current_sum managing the interval sum to \(0\), and a variable min_length recording the minimum interval length to a very large value (infinity). Move the right end right from \(0\) to \(N-2\) in order, performing the following operations:
   • Add \(D[right]\) to current_sum.
   • While current_sum \ge K is satisfied, repeat the following:
     • Update min_length with the current interval length (right - left + 1) if it is smaller.
     • To shorten the interval as much as possible while still satisfying the condition, subtract \(D[left]\) from current_sum and increment left by \(1\) to shrink the left end.
4. Outputting the answer After all searches are complete, if min_length remains at its initial value, no route satisfying the condition exists, so output -1. If it has been updated, since what we want is the “number of points,” output min_length + 1, which is the interval length (number of differences) plus \(1\).

Complexity

• Time complexity: \(O(N)\) Creating the difference array \(D\) takes \(O(N)\). In the two pointers method, right and left each move rightward at most \(N-1\) times, so the total number of operations in the loop is also \(O(N)\). Therefore, the overall time complexity is \(O(N)\).
• Space complexity: \(O(N)\) Since we store the input array \(A\) and the difference array \(D\), we use \(O(N)\) memory.

Implementation Notes

• Be careful about the difference between “number of differences” and “number of points” Since array \(D\) represents “gaps between points,” an interval of length \(L\) contains \(L + 1\) points. Make sure not to forget the + 1 when outputting the final answer.

• The while loop in the two pointers method When advancing right satisfies the condition (the sum becomes at least \(K\)), writing a while loop that advances left to shrink the interval “until the condition is no longer satisfied” is the standard pattern for the two pointers technique and the simplest way to implement it.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:N+2]]
    
    if N == 1:
        print(-1)
        return
        
    D = [abs(A[i+1] - A[i]) for i in range(N-1)]
    
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(N-1):
        current_sum += D[right]
        while current_sum >= K:
            if right - left + 1 < min_length:
                min_length = right - left + 1
            current_sum -= D[left]
            left += 1
            
    if min_length == float('inf'):
        print(-1)
    else:
        print(min_length + 1)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.