### el3el2's blog

By el3el2, history, 7 years ago,

I am trying to find an O(n) solution to this problem:

Given an array, find the subarray with the sum closest to 0.

An O(nlogn) solution is kinda straightforward, but I have read this problem in a textbook in a context suggesting there's a O(n) solution. Any help?

• +9

| Write comment?
 » 7 years ago, # |   +5 i don't know but looks like it's a variant of kadane algorithm
•  » » 7 years ago, # ^ |   0 Not as far as my thought process could go. A variation of Kadane algorithm can be used to find the minimum sum; but could not apply that to a specific sum. The simplest form of this problem I could find is finding the closest two elements in an array (the prefix sums in this problem).
•  » » » 7 years ago, # ^ |   +22 You can't solve this faster than O(n log n) by a reduction from https://en.wikipedia.org/wiki/Element_distinctness_problem
•  » » » » 2 months ago, # ^ |   +3 The element distinctness problem only applies for comparison sorts. This reduces to 2SUM and you can use a hash table to do this, assuming a uniform hash.
•  » » » » » 2 months ago, # ^ |   0 Bro you're a little late...)
•  » » » » » 2 months ago, # ^ |   0 Nice you dug up this ancient post. Go read about necroposting