serpent54's blog

By serpent54, history, 16 months ago, In English

How to think about to write code of finding the longest subarray with sum greater than or equal to k in O(nlogn).

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand your question. if the sum needs to be greater or equal to $$$k$$$, can't you just choose all of the elements in the array?

16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Put all negative integers into an array. Greedily choose all positive integers. Sort negative array by least value. Greedily choose minimum negative integer until you can't anymore.

16 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

We will call our array $$$a$$$, for every $$$0 \leq i \leq n - 1$$$ we keep a number $$$ps_i = a_0 + a_1 + \dots + a_i$$$.

For any $$$0 \leq l \leq r \leq n - 1$$$ we can find $$$a_l + a_{l + 1} + \dots + a_r$$$ in $$$O(1)$$$ using the fact that its value is equal to $$$ps_r - ps_{l - 1}$$$ (if $$$l = 0$$$ we dont include $$$ps_{l - 1}$$$)

Using this we write a function $$$check(s)$$$ which will heck all subarrays of size $$$s$$$, if there is at least one with sum greater or equal to $$$k$$$ it returns 1 and otherwise 0. this will work in $$$O(n)$$$.

Now we can just do a binary search on the size of the subbarray. thus the time complexity is $$$O(n \log n)$$$.

  • »
    16 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Binary search doesn't work. You're incorrectly assuming that if there exists no good subarray of length $$$m$$$, there cannot exist a good subarray with length $$$\ge m$$$. This is just not true.

    Consider the following example: $$$n = 5$$$, $$$k = 50$$$, $$$a = [10, 10, 10, 10, 10]$$$. There exists a single good subarray $$$a[1:5]$$$ with length $$$5$$$, but your binary search won't find it.

    Run results

    I'll give you another example. Let $$$n = 12$$$, $$$k = 60$$$, $$$a = [-10, -10, 10, 10, 10, 10, 10, 10, -10, 10, -10, -10]$$$. There are two good subarrays, $$$a[3:8]$$$ and $$$a[3:10]$$$ with lengths $$$6$$$ and $$$8$$$, but your binary search will "skip over" the one with length $$$8$$$ and only return $$$6$$$.

    Run results

    Let's actually prove that the problem can't be solved with binary search (at least in the way you did it). Consider the last example I gave. I'll modify your program to print the result of $$$check(s)$$$ for all possible $$$s$$$.

    Run results

    If you anything about binary search, you can see that the function $$$check(s)$$$ is not binary searchable.