Problem Link
Setter: Trung Nguyen
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain
Difficulty
EASY-MEDIUM
Prerequisites
Binary Search, Prefix Sums, Divide and Conquer
Problem
Find the length of the minimum subarray such that the sum of its elements is greater than D.
Explanation
Let us first maintain a prefix sum of the array. Now the problem reduces to the following:
For every index j, find the closest index i less than j, such that \text{Prefix[j]} - \text{Prefix[i]} ≥ \text{d}.
The equation can also be written as \text{Prefix[j]} - \text{d} ≥ \text{Prefix[i]}. To understand the process, let us consider an example. Let array \text{A = } \{2, 4, 3, -2, -5, 1\}.
The prefix array would be \{2, 6, 9, 7, 2, 3\}. Say, we want to find the answer for index j = 6 i.e. we want to find the nearest i such that (3 - d) ≥ prefix[i]. We see that if index 3 satisfies the inequality, so does all the indices with a value less than 9 and ahead of it, i.e. indices 4 and 5 too. Thus, in general, we say that if for index j, say index i satisfy the inequality, all such indices ahead of i and having a value less than or equal to it will also satisfy it. Since we would like to find the closest index i for every j (if it exists), the previous indices having the value greater than current prefix value, although may satisfy the inequality but will never lead to an optimal answer, (meaning smallest subarray size). We thus keep an increasing temporary array, (along with indices) based on the prefix sums. Since, this array is increasing (i.e. monotonic), we can apply binary search on it to find the optimal index. Let us complete this through the example array above.
The temporary index will look as follows:
- T = {$(2, 1)$}. This first part is the prefix value and the second part is the index.
- T = {$(2, 1), (6, 2)$}
- T = {$(2, 1), (6, 2), (9, 3)$}
- T = {$(2, 1), (6, 2), (7, 4)$}. This is because for every inequality which 9 satisfy, 7 will also satisfy and it being closer will lead to optimal answer. So, value 9 was discarded.
- T = {$(2, 5)$}
- T = {$(2, 5), (3, 6)$}
To understand, more about this approach see author’s or tester’s solution below.
Editorialist Approach
Generally, in problems where we need to calculate some function over all subarrays and queries are not involved, divide and conquer seems a good idea assuming merging can be done efficiently. Assume, in the recursive step, we calculate the answer for the left and right halves. To understand the complete solution, we just need to understand the merging part.
We compute all the prefix sums on the right-hand side and store them in a map along with the indices. Now we iterate through all the suffix sums on the left-hand side and try to find the first index on the right side which satisfy this inequality. This can be easily done by applying a “lower_bound” on the map build. The time complexity of this approach will be as follows:
T(N) = 2*T(\frac{N}{2}) + O(N*\log{N})
meaning T(N) = O(N * {\log}^{2}{N}).
For more details, refer to the editorialist solution. The idea is more or less similar to the author’s solution (although less efficient in this case) but can be used in other problems asking us to compute some function over all subarrays. Thus I included this part in the editorial. (Though it is an overkill for the problem).
Time Complexity
O(N * \log{N}), per test case
or O(N * {\log}^{2}{N}), per test case.
Space Complexity
O(N)
or O(N * \log{N})
