Dsa
Sliding Window
Medium
Smooth Path Hunting
You are analyzing a drone's altitude data. To ensure stable flight, you need to find the longest contiguous sequence of readings where the 'Total Variation' is within a budget V. Total Variation is defined as the sum of the absolute differences between all adjacent pairs in the window.
Input Format:
- The first line contains an integer V (the maximum variation budget).
- The second line contains a space-separated sequence of integers representing altitude readings.
Output Format:
- A single integer representing the length of the longest such window.
Example:
Input:
3
1 4 5 5 7
Output:
4
(Explanation: Window [1, 4] variation is 3. Window [4, 5, 5, 7] variation is |5-4| + |5-5| + |7-5| = 1 + 0 + 2 = 3. Length is 4.)
Key concepts
sliding_windowdifference_array
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now