How to think about to write code of finding the longest subarray with sum greater than or equal to k in O(nlogn).
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
How to think about to write code of finding the longest subarray with sum greater than or equal to k in O(nlogn).
Name |
---|
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?
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.
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)$$$.
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.
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$$$.
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$$$.
If you anything about binary search, you can see that the function $$$check(s)$$$ is not binary searchable.