The link to the problem : https://www.codechef.com/problems/MINSUBAR
Solution
First of all we will take the prefix sum of the array.
eg:- Consider array 4 5 3 -2 -1 4
Prefix array 4 9 12 10 9 13
Now, to find sum of a subarray from index j+1 to i we will do
prefixArray[i]-prefixArray[j]
Now we know that we require prefixArray[i]-prefixArray[j] >= d
Hence, prefixArray[i]-d >= prefixArray[j]
Now, we will maintain a temporary array(map) containing index and prefix sum at the index.
In our example consider i=6. From above relation we can see that if for j=3 relation is satisfied then it will be satisfied for j=4 and j=5 i.e. as we encounter small values we can remove previous values bigger than the current value. Keep in mind that this won’t be true for increasing values.
Hence, we can make our temporary array keeping the above statement in mind.
Temporay array shall be build like
(4,1)
(4,1), (9,2)
(4,1), (9,2), (12,3)
(4,1), (9,2), (10,4)
(4,1), (9,5)
(4,1), (9,5), (13,6)
Hence, our array would be an increasing array and so we can apply binary search for value prefixArray[i] – d and if value won’t be present it shall give us insertion point from where we can move backward one index(if exists).
Now we will simply subtract the indices of two and store it in a variable. For every ith index we will check the minimum value of current value and our variable.
After n iterations we will print the variable if answer exists or -1.
Time Complexity
The time complexity of above solution will be O(nlogn)
Competitive Programming 