Problem Link:
Practice
Contest
Author: murugappan_s
Testers: sdssudhu,msv99999
Editorialist: murugappan_s
DIFFICULTY: Medium-Hard
PREREQUISITES: Binary Search
PROBLEM:
You are given an integer array( A ) of size N and an integer value K. Find the number of sub-arrays of A, such that the difference between maximum value and minimum value in the sub array is less than or equal to K.
Sub-array is a contiguous portion of an array and two sub-arrays are different if their starting index or ending index is not same.
CONSTRAINTS:
- 1≤N≤100000
- 0≤K,A[i]≤10^9
SOLUTION:
Let us consider some sub-array from the array A with the index range [l,r], let the corresponding range minimum and maximum be MINI and MAXI respectively.
Claim 1: If MAXI-MINI > K for the given range [l,r], then for any range [l,r+d] for any positive value for d, the difference between its range maximum and minimum is greater than K.
Proof:
Given MAXI and MINI are range maximum and range minimum for the range [l,r].
When the range is extended towards the right the new maximum is guaranteed to be greater than or equal to the old maximum and new minimum is guaranteed to be lesser than or equal to the old minimum, which implies that the difference can only increase and cannot decrease. So our claim holds.
Claim 2: If MAXI-MINI <= K for the given range [l,r], then for any range [l,r-d] for any d in [0,r-l], the difference between its range maximum and minimum is lesser than or equal to K.
Proof:
Given MAXI and MINI are range maximum and range minimum for the range [l,r].
When the range is shorted from right the new maximum is guaranteed to be lesser than or equal to the old maximum and new minimum is guaranteed to be greater than or equal to the old minimum, which implies that the difference can only decrease and cannot increase. So our claim holds.
So for each sub-array starting point l in [1,N] find out the largest r in [l,N] such that the MAXI-MINI in [l,r] is lesser than or equal to K and add r-l+1 to the answer as the ranges [l,l],[l,l+1],[l,l+2],......,[l,r-1],[l,r] satisfy the condition.
r can be found through binary search and range minimum query can be done through sparse table in O(1) or through segment tree in O(log(RangeSize))
Time Complexity: O(NlogN) (sparse table) or O(Nlog^2N) (segment tree)
Space Complexity: O(NlogN) (sparse table) or O(N) (segment tree)