×

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

 2 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 :-) asked 23 Jan, 12:55 -863●9 accept rate: 0% try variant of Kadane algorithm. (23 Jan, 19:01) DOES NOT WORK (23 Jan, 23:12)

 0 Yes, we can! :) 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. answered 24 Jan, 02:30 126●4 accept rate: 5%
 0 can u please send the link of the question : ) answered 24 Jan, 21:05 30●4 accept rate: 9% 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 (24 Jan, 22:55)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×75
×68
×20