1

I came across a problem on a coding contest which basically boils down to this.

Given an unsorted array with positive numbers find the length of the smallest subarray which has a sum greater than or equal to an input sum.

For input : [14, 2, 10, 1, 1, 2, 1]

And sum = 10output = 1 [10]

for sum = 13output = 1 [14]

for sum = 15output = 2 [14, 2]

There will be a lot of queries to answer in the range of 1 to 10^5.

My approach.

Build an array of the same length as the input where array[i] will be the maximum sum of a subarray of size i. This can be done in O(N * N) time and O(N) space

So now we have an array with increasing sum so we can use binary search to find the smallest length that can satisfy the particular input sum.

so if there were q queries it would run in O(q * log(N)) time.

I'm not sure how feasible this solution is or if there is a better solution than this. Since I couldn't test it out on that online judge and the problem isn't available now.

Is there a better solution to this in terms of time and space complexity.

Follow up:

What if the given input can be changed later. How do you have such situations where the input can be updated.

thebenman
  • 1,621
  • 14
  • 35
  • According to me that's the optimal approach for this problem, it can't get better than this – zenwraight Jun 10 '18 at 07:01
  • depends on constraints like maximum N, maximum value of each element, if there is a constraint on sum of whole array... – juvian Jun 10 '18 at 07:04
  • This sounds like knapsack https://stackoverflow.com/questions/7949705/variation-on-knapsack-minimum-total-value-exceeding-w – Ruan Jun 10 '18 at 11:19

1 Answers1

0

I'd use prefix array for this.

Prefix array - is additional array for a

pr_a[0] = a[0] pr_a[i] = pr_a[i-1] + a[i]

Prefix array has O(n) precalculation and O(1) calculation.

Write function max_window(pr_a, k), which'd find subarray with maximal sum on it.

def max_w(pr_a, k):
    m = pr_a[k-1]
    for i in range(1, len(pr_a) - k + 1): 
        m = max(m, pr_a[i + k - 1] - pr_a[i-1])
    return m

This will find sum. I think you understand how this function can find indexes.

Then binary search on answer.

And we have O(q * n * log(n))

Actually if you want to change an array after precalculation, you can use Segment Tree

Арсений Щекин
  • 1
  • 1