serpent54's blog

By serpent54, history, 14 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?
»
14 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?

»
14 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.

»
14 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)$$$.

code
  • »
    »
    14 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$$$.

    Code
    Run results

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