**Background**

I came across this interesting stack overflow question:

https://stackoverflow.com/questions/471 ... 3_47111546

**Question**

There is an array n = 1 million in length containing positive integers.

There are also n = 1 million queries, where each query has a value x and wants to know "what is the shortest length of a subarray with total sum greater than x?"

Has any one any idea on how to solve this with better than O(n^2) complexity?

(Note that I don't know what competition the question is from, so it is possible that there were some additional constraints that make the problem easier)

**Thoughts**

My first idea is to try and compute the greatest value achievable for each length of subarray. Once we have this it is easy to answer any query by bisection.

My second idea is to try and solve the problem by divide and conquer. i.e. split the array in half and for each half prepare a list of greatest value for each possible length, then merge the lists together.

The problem with this is that we also need to consider cases when the subarray crosses the border. By preparing a cumulative sum array it is easy to measure the content of any particular subarray in O(1), but there are still O(n^2) crossing cases to consider.

At this point I am stuck - anyone have any bright ideas for making progress? (Feel free to post an answer to the stack overflow question or post here)