Can we find the length of the longest subarray with sum>k efficiently?

general
, ,
1

Here, ‘k’ can be any integer.

My O(nlogn) solution is as follows :- https://ideone.com/Ff3CcO

Is there any O(n) algorithm for above?

Thanks.

Note:-
1)I’ve done my research.
2)No, this problem does not belong to any ongoing contest in the world :slight_smile:

1 Like
2

try variant of Kadane algorithm.

3

DOES NOT WORK

4

Yes, we can! :slight_smile:

Precalc prefix and suffix negative sums sorted by sum and length. It can be done at O(n), because we add new sum to already sorted array only if this one is smaller than last.

Use two pointers technics to parse all pretenders and choose the longest.

5

can u please send the link of the question : )

6

Question is:-https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/
But after we reach the last step of the solution we realize that we have to find the length of the longest sub-array with sum>-2