I am trying to solve this problem so many times but I can't figure out how to solve this within 2.00 second(Time limit). I really need help cause I am being frustrated about this problem.

Problem summary : Given an array find the smallest sub-array whose summation is greater or equal than X and output the length of the smallest sub-array.

1 <= Array size <= 500000, -10^9 <= A[i] <= 10^9 and -10^9 <= X <= 10^9.

Can any one give me some hints about how to solve this type of problem less than O(n^2) complexity and within 2.00 second(Time limit).

Thanks in advance. :)

we build the array S with S[i] = sum(A[1], A[2], .. A[i]) then we have S[i] — S[j] = sum(A[j + 1], .., A[i])

then with each S[i], we find the maximum number j such as S[i] — S[j] >= x (j must be maximal so that the sequence length can be minimal)

S[i] — S[j] >= x <-> S[i] — x >= S[j]

here we have the left side can be calculated in O(1), the rest is to find j, O(n ^ 2) is the most simple way but it'd get TLE so u must use some data-structure like fenwick tree, segment tree, etc to do the job :p

"then with each S[i], we find the maximum number j such as S[i] — S[j] >= x (j must be maximal so that the sequence length can be minimal)"

I guess since A[i] can be negative this step is wrong.

You just need to find some j such that S[j] <= S[i] — X.

One way of doing this is using a segment tree (where each node keeps the minimum value of the interval), initially with all nodes equal to INF, and when you are at position i: if value at root is bigger than S[i] — X, then you know that there's no segment (j + 1)..i whose sum is >= X. otherwise you go to the rightmost node where the value of the node is <= S[i] — X, and there you find j.

After processing which position i, you update that position in the segment tree.

If you want, you can check my solution: http://pastebin.com/95uZG0se

How this solution can be passed??? Try This input; 1 3 4 1 2 1

output should be 3 but your code is giving -1

Apparently the testcases were weak and didn't test some corner cases. To correct that bug just need to add the code below checking if ans == INF :

По русски можно?

Thank you all for your reply. :)

can anyone check what is wrong with this idea: I am getting WA. code Thanks.

Check this test case.

`1`

`10 15`

`1 4 -1 -2 6 3 -8 14 -1 1 -1`

Answer should be 4 but your code shows 7.

`6+3+(-8)+14 = 15`

Thanks, got it and it will become O(n^2) when I run for every possible dq position.

Use a priority queue on accumulative sums. First let's build an accumulative array ACC where ACC[i] = ACC[i-1] + arr[i]. Now we want to know for each position i, what's the closest position to it's right j such that ACC[j] — ACC[i] >= X, this can be done with a priority queue.

For a hint on how to implement this you can check my AC solution here http://ideone.com/ELweLn

nice, a very simple solution ^^

Simple implementation using java TreeMap

KNIGHT0X300, could you please explain what is the purpose of removing keys in the TreeMap greater than sum[i] as done by the above code. Ideally as 'put' method replaces previous value and floorKey returns maximum key <= sum[i], i couldn't make out the reason behind this. Other than that the code seems pretty awesome to me :)

thanks man your code helped me in implementing the logic

https://discuss.codechef.com/questions/119992/minsubar-editorial

but this has a problem. when floorKey is null then we check for if sum[i] is our desired value.

Consider

5 9

1 2 3 1 2

Remember we artificially do tm.put(0L, -1); at the beginning. So this will take care of the case you are talking about. If the sum[i] is the desired value (sum[i] — x) = 0, and -1 will show up as the floorKey. Hence the answer would be current 0 based index -(-1), which is (index + 1).

Just asking couldn't it be solved by just 4 variables in O(n) time using a continuously increasing variable keeping the index of latest added element in the sum and another keeping the index of the first element in it and increasing it every time the sum of the elements between them get bigger or equal than X or negative , keeping the minimum lenght found sofar.(similar to the optimal algorithm of the Maximum sub-array problem)

I think we can use the segment tree approach to solve this problem in O(NlogN) time. Just iterate on each element in the array at index i (N times), and find the closest element at index j (this takes logN). Total complexity is O(NlogN)

I believe there is a simple and intuitive solution using binary search that solves in O(N lg N) time.

To answer to query "Does there exist a sub-array of length k which sums to at least X" takes O(N) time with accumulative/prefix sums.

Thus, we can binary search for the smallest value of k, which will take O(lg N) time.

This leads to a total complexity of O(N lg N).

EDIT: Oops.

Are you sure that we can use binary search here? Because function is not monotonous.

Array

has subarray of size 1 with sum >=1, but none of it subarrays of size 2 or 3 have sum >=1.

this is only true if the array elements are non-negative. but

OPsays - 10^{9}≤A_{i}≤ 10^{9}and - 10^{9}≤X≤ 10^{9}.PS: LeBron has provided a case which breaks your idea.

Correct, this is RMQ (range minimum query) issue. That's why we should use other expensive data structure like segment tree to do the query

Problem is easy to solve in O(n) using modification of deque to find minimum element in it.

Code

same problem but your code gives wrong answer. I have solved that problem differently using segment tree.

adamant, I think your solution got AC because of weak tests on UVa, because your same code got WA on the same problem on codechef MINSUBAR

Can someone explain why I am getting WA for this solution My approach is dropping the previous sum if it is less than or equal to 0