I don't remember the exact wording but it was a story about amazon delivery which was a wrapper around the question, I have phrased the question myself.
Question 1
Given an array of integers and an integer k, count the number of subarrays such that min and max in the subarrays should not have difference of more than k.
Example 1
Input : [1,3,6] k = 3
Output : 5
Explanation :
[1] min = 1 max = 1 difference = 0 (Valid)
[1,3] min = 1 max = 3 difference = 2 (Valid)
[1,3,6] min = 1 max = 6 difference = 5 (Invalid)
[3,3] min = 3 max = 3 difference = 0 (Valid)
[3,6] min = 3 max = 6 difference = 3 (Valid)
[6,6] min = 6 max = 6 difference = 0 (Valid)
So in total there are 5 valid subarrays. Example 2
Input : [1,5,4] k = 2
Output : 4
Explanation :
[1] min = 1 max = 1 difference = 0 (Valid)
[1,5] min = 1 max = 5 difference = 4 (Invalid)
[5,5] min = 5 max = 5 difference = 0 (Valid)
[5,4] min = 4 max = 5 difference = 1 (Valid)
[4,4] min = 4 max = 4 difference = 0 (Valid)
So in total there are 4 valid subarrays. My Approach (Didn't worked out) : I tried using sliding window with the intuition that if the window is not satisfying the condition given i.e when max - min in subarray > k, then when it satisfied previously that was a valid window, number of subarray possible in window are
(window size * (window size + 1)) / 2.
For instance [1,3,6] does not satisfy the condition so previously when it was satisfied at [1,3] that time the number of subarrays possible where 3, now shrink the window until it again satisfies.
Again when it satisfies at [3,6] the number of subarrays possible are again 3, so in total 6, but there is an overlap of element 3 so by subtracting the count of the number of sub arrays possible of overlapping length i.e 6 - 1 = 5.
Ps : Please let me know if you guys have any other approach or if there is any correction in my approach.
Question 2
Another sliding window question, I didn't remember the question exactly but it was a medium difficulty level standard question of sliding window.