Longest Zero Sum Sub-array

Question

Given an array of integers. Find out its longest sub-array (contiguous subsequence) whose sum is 0.

The sub-array for output may be an empty array.

Input

Input an array of integers.

Output

Output the longest zero sum sub-array. If there are multiple such arrays, output any one of them.

Output Format

You may output in one of following acceptable format:

1. Output an array of integers;
2. Output the index of first (inclusive) and last (inclusive) element of sub-array;
   • Output (last = first - 1) for empty sub-array
3. Output the index of first (inclusive) and last (exclusive) element of sub-array;
4. Output the index of first (inclusive) element and length of sub-array;

You may choose 0-indexed or 1-indexed value for 2~4 options. But your choices should be consistent for both first and last element.

Rules

• This is code golf, shortest codes win.
• As usual, standard loopholes are forbidden.
• Your program may fail due to integer overflow (as long as this not trivialize this challenge, which is a standard loophole).
• This is code golf. We don't care the performance of your algorithm / implementation.

Testcases

Input -> Output
[] -> []
[0] -> [0]
[1] -> []
[-1,1] -> [-1,1]
[-1,1,2] -> [-1,1]
[-2,-1,1,2] -> [-2,-1,1,2]
[1,2,3,4,5] -> []
[1,0,2,0,3,0] -> [0]
[1,2,-2,3,-4,5] -> [1,2,-2,3,-4]
[1,2,3,4,5,-4,-3,-2,-1,0] -> [4,5,-4,-3,-2]
[0,1,0,0,0,1] -> [0,0,0]
[0,0,0,1,0,0,1] -> [0,0,0]
[0,0,0,1,0,0,-1] -> [0,0,0,1,0,0,-1]
[-86,14,-36,21,26,-2,-51,-11,38,28] -> [26,-2,-51,-11,38]
[0,70,65,-47,-98,-61,-14,85,-85,92] -> [0,70,65,-47,-98,-61,-14,85]
[4,-4,2,0,4,-2,-2,1,0,1,-4,0,-2,2,2,-4,0,-1,2,1,-4,-2,3,4,3,0,3,2,-4,2,3,3,1,2,3,-3,-4,3,-4,4,0,-3,-1,-5,-4,1,-3,4,-4,2,-1,-4,0,2,-5,-5,2,1,-4,0,-1,4,3,3,-5,-4,-5,3,-3,-1,-5,1,-2,3,0,3,-4,1,-5,-1,4,-5,2,1,-3,4,4,1,-1,-5,-5,-2,4,0,-3,4,1,-3,0,-3] -> [4,-4,2,0,4,-2,-2,1,0,1,-4,0,-2,2,2,-4,0,-1,2,1,-4,-2,3,4,3,0,3,2,-4,2,3,3,1,2,3,-3,-4,3,-4,4,0,-3,-1,-5,-4,1,-3,4,-4]

• tsh: Will there be any languages that an implementation of \$o(n^2)\$ algorithm is shorter than using \$\Omega(n^2)\$ algorithms?
• DLosc: Suggested test case: [0,1,0,0,0,1] -> [0,0,0]. My initial attempt in Brachylog passed all existing test cases but failed this one.
• Bubbler: @tsh Yes.
• tsh: @DLosc Added. Though I don't quite understand how this happened.
• DLosc: @tsh Brachylog's contiguous-sublist builtin generates all sublists starting with the first item, then all sublists starting with the second item, etc. In other words, it finds the leftmost sublist before it finds the longest sublist. In all the original test cases, the longest sublist was also the leftmost, and so it didn't make a difference. In [0,1,0,0,0,1], the leftmost zero-sum sublist is [0], different from the longest sublist [0,0,0]. (A shorter example, which I thought of later, is [0,2,-1,1].)

Answer 1

Python 3, 47 bytes

f=lambda x,*a:f(*a,x[1:],x[:-1])if sum(x)else x

Try it online!

It's simple breadth-first search, implemented recursively. The if...else is slightly bothering me; it feels like there is an improvement somewhere...

• AShelly: on the if..else, I think you can use short-circuiting to save a single char with ...:sum(x)and f(*a,x[1:],x[:-1])or x
• dingledooper: @AShelly Unfortunately that won't work when the answer is an empty list. An empty list is Falsy so it would trigger the or x at the wrong time.
• xnor: That's a really golfy and clean way to do BFS recursively! It looks like this would save bytes on a lot of challenges where the current solution makes a recursive call like max(...,key=len).
• dingledooper: @xnor Thanks! I think I saw this "trick" from one of tsh's answers, although I don't remember which one it is. Credit to them for this one :P

Answer 2

05AB1E, 7 bytes

ŒéʒO_}θ

Try it online!

Π# sublists of the input
 é # sort by length
 ʒ } # keep those where:
 O_ # the sum equals 0
 θ # take the last one

The output of Œ doesn't contain the empty list, but if the result of the filter is empty, θ fails and leaves the empty list on the stack.

• Kevin Cruijssen: Same as what I had in mind, except I had the é after the filter, since it's better for performance. ;) Here also a minor 7-byte alternative: ŒéR.ΔO_

Answer 3

K (ngn/k), ^{(削除) 24 (削除ここまで) (削除) 22 (削除ここまで)} 21 bytes

{t@'*<-/t:&x=/:x}0,+\

Try it online!

-1 byte thanks to coltim and Traws

Unfortunately(?), I found a 2-byte golf that bumps the time complexity to \$\mathcal{O}(n^2 \log n)\$ (and space complexity to \$\mathcal{O}(n^2)\$). This one utilizes "equality table" =/: and "deep where" & to extract all pairs of indices that represent zero-sum subarrays. Finding the pair that represents the longest such subarray is algorithmically the same.

---

K (ngn/k), 24 bytes

*<!/1-/'\(*'1|:\)'.=0,+\

Try it online!

Runs in \$\mathcal{O}(n \log n)\$ time and \$\mathcal{O}(n)\$ space. A monadic function train that takes a list of integers and returns [start index (inclusive), end index (exclusive)]. (For reading test case output, !0 and () are notations for empty lists, and ,0 is a notation for the singleton list [0].)

*<!/1-/'\(*'1|:\)'.=0,+\ monadic train; x: integer list
 0,+\ prepend 0 to the cumulative sum of x
 = group; gives a dict of {value:indices}
 . extract values of the dict
 any ordered pair inside each row forms a valid
 (start,end) pair with subarray sum of zero
 (*'1|:\)' for each list, extract (first,last)
 <!/1-/'\ sort this list by ascending order of (first-last)
* extract the first pair

It is actually shorter than a function that generates all contiguous subsequences and operates on them (which is \$\mathcal{O}(n^3)\$ time and space):

K (ngn/k), 26 bytes

{*(0=+/)#,/x{y'x}/:|!1+#x}

Try it online!

Answer 4

Japt -h, 5 bytes

ã k_x

Try it or run all test cases

ã k_x :Implicit input of array
ã :Sub-arrays
 k :Remove elements that return truthy (not 0)
 _ :When passed through the following function
 x : Reduce by addition
 :Implicit output of last element of resulting array (or undefined if empty)

Answer 5

JavaScript (ES6), 60 bytes

f=(b,...a)=>eval(b.join`+`)?f(...a,b.slice(1),b.pop()?b:b):b

Try it online!

Commented

f = ( // f is a recursive function taking:
 b, // b[] = next array
 ...a // a[] = list of all other arrays
) => //
 eval(b.join`+`) ? // if the sum of b[] is not zero:
 f( // do a recursive call:
 ...a, // first try with the other arrays that were
 // already passed to this iteration
 b.slice(1), // then try with b[] without the leading term
 b.pop() ? b : b // and finally with b[] without the trailing term
 // NB: we don't mind modifying b[] at this point,
 // and this is shorter than b.slice(0, -1)
 ) // end of recursive call
 : // else:
 b // success: return b[]

• Shaggy: Oh, I love the counter-intuitiveness of that ternary trick with the pop!

Answer 6

Jelly, 7 bytes

ẆSÐḟṪȯ$

Try It Online!

Converted from a full program to a link for the same byte-count thanks to Jonathan Allan.

ẆSÐḟṪȯ$ Main Link
Ẇ Get all sublists (unfortunately excludes the empty sublist)
 Ðḟ Filter to remove elements with a non-falsy/non-zero
 S sum
 $ Apply monadically to the resulting list of sublists:
 Ṫ - take the last one (returns zero if the list is empty)
 ȯ - logical OR; if 0 was returned, instead return the list
 of sublists, which is the empty list

• zoomlogo: Well that was quick
• tsh: Your output for [1,2,3] and [0,1,2,3] are both 0. Although it is arguable if represent an empty array with 0 is acceptable. I don't think that using 0 for both empty array and an array of single 0 should be allowed.
• hyperneutrino: @tsh one of them is the number 0 and one of them is a singleton list 0 (Jelly displays both the same way) - is that acceptable? if not, I will add an edge case
• tsh: Could this be fixed by using function submission with format the output using different way outside the function? If this is a whole program, user cannot guess which output it is currently. And therefore it seems to be invalid to me.
• Jonathan Allan: A Link that does the job in 7 bytes: ẆSÐḟṪȯ$

Answer 7

Risky, 12 bytes

{_*_1?+?:_0{_-+_0+_0+_0

Try it online!

Explanation

Here's a rough tree diagram of how the program parses:

 {
 ? +
 * : + +
{ _ + _ _ _ _ _
 _ 1 ? 0 - 0 0 0

The left half generates a list of all sublists that sum to zero:

{_ List of sublists of the input (ordered shortest to longest)
 *_1 Repeat 1 time (no-op)
 ? Filter by this function:
 +? The sum of the input
 : Equals
 _0 Zero

The right half, using a ton of no-ops to balance the parse tree, evaluates to -1. Finally, { gets the element of (left half's result) at index (right half's result): i.e. the last and therefore longest sublist.

• Adamátor: Damn, you beat me to it.

Answer 8

Vyxal, 7 bytes

ÞS'∑¬;t # main program

ÞS # sublists
 '∑¬; # filter
 ∑¬ # by the negated sum
 t # take the tail

Similar to @hyper-neutrino's answer.

Try it Online!

• lyxal: Dang, I had 18 bytes
• Underslash: @lyxal did you manually implement sublist?
• lyxal: Y...yes, I did.
• Underslash: This is the first time I've ever remembered a command that you've forgotten, usually its the other way around. :)

Answer 9

J, 28 bytes

<\\.;@{.@(\:#&>)@#~&,0=+/\\.

Try it online!

• <\\....#~&,0=+/\\. All boxed sublists <\\. filtered by those with 0 sum #~ 0=+/\\. after flattening both &,.
• (\:#&>)@ Sort down by length
• ;@{.@ And open the first element.

Answer 10

Factor + math.unicode, 64 bytes

[ [ "1"] when-empty all-subseqs [ Σ 0 = ] filter ?last >array ]

Try it online!

• [ "1"] when-empty Unfortunately necessary to handle the empty sequence. all-subseqs blows up otherwise. "1" is simply the shortest thing you can stick in there that ultimately produces the empty sequence.
• all-subseqs Get every subsequence of a sequence.
• [ Σ 0 = ] filter Select the ones that sum to 0.
• ?last >array Take the last (also longest) element (or f if the sequence is empty) and then convert it to a sequence. Necessary because the filter can return an empty sequence.

Answer 11

Wolfram Language (Mathematica), (削除) 37 (削除ここまで) 36 bytes

Last@*Select[Tr@#==0&]@*Subsequences

-1 byte from att using function composition

Try it online!

Subsequences generates all contiguous subsequences, sorted by length; Select[Tr@#==0&] selects those whose trace (total) is 0; Last selects the last, and thus longest, of these subsequences.

att also shows, in the comments, a different approach from mine that is 35 bytes:

Last@Pick[#,Tr/@#,0]&@*Subsequences

• att: 36 bytes
• att: alternative 36 bytes
• att: 35 bytes
• theorist: @att Neat! I've never used the operator form of Select.

Answer 12

Python 3, 85 bytes

lambda a:[(s,l)for l in range(len(a))for s in range(len(a)-l)if 0==sum(a[s:s+l])][-1]

Try it online!

-5 bytes thanks to totallyhuman

• totallyhuman: 85 bytes by switching up the iteration logic to remove the need to find the maximum (and also outputting as start index and length).

Answer 13

Brachylog, (削除) 13 (削除ここまで) 9 bytes

-4 bytes thanks to a clever trick from Unrelated String

⊇.+0&s.∨Ė

Try it online! (Note that negative numbers in the input must be indicated with underscores rather than minus signs.)

Explanation

It would have been nice to use this 6-byte solution:

s.+0∨Ė
s. A contiguous sublist of the input is the output
 +0 and its sum is zero
 ∨ Or, if it is impossible to satisfy those conditions...
 Ė the output is the empty list

Unfortunately, the order in which the s predicate tries sublists is ordered by start index, not by length. However, the ⊇ predicate, which gives not-necessarily-contiguous sublists, is ordered by length. So we can start by getting the longest sublist and then afterwards check that it's contiguous:

⊇.+0&s.∨Ė
⊇. A sublist of the input is the output
 +0 and its sum is zero
 & and furthermore
 s. the output is a contiguous sublist of the input
 ∨ Or, if it is impossible to satisfy those conditions...
 Ė the output is the empty list

• Unrelated String: The trick when you need the longest contiguous sublist is you get the longest sublist then you check that it's contiguous
• DLosc: @UnrelatedString Ah, clever. Post that to the tips question and I'll upvote it!

Answer 14

Haskell, 64 bytes

k=length
f l|sum l==0=l|h:t<-l=f t#(f.init)l
a#b|k a>k b=a|1>0=b

Try it online!

• f return longest sublist by checking if list sum is 0 or choosing the best result coming from recursively inspecting tail and init
• a# b used by f to choose longest result

Answer 15

Haskell, (削除) 75 (削除ここまで) 73 bytes

-2 bytes thanks to Joseph Sible.

f i|e<-length i=last[(s,l)|l<-[0..e],s<-[0..e-l],0==sum(take l$drop s i)]

Try it online!

• Joseph Sible-Reinstate Monica: You can save 1 byte by declaring g=length instead of writing out length twice.

Answer 16

Clojure, 98 bytes

#(or(first(for[n[(count %)]i(range n)j(range n i -1):when(=(apply +(subvec % i j))0)][i j]))[1 0])

Returns an exclusive range, or [1 0] if no such range is found. For example:

[1,2,3,4,5,-4,-3,-2,-1,0] -> [3 8]

Answer 17

Perl 5, 73 bytes

sub{(sort{@$b-@$a}grep!sum(@$_),map[@_?@_[$_/@_..$_%@_]:()],0..@_**2)[0]}

Try it online!

Answer 18

Desmos, (削除) 154 (削除ここまで) (削除) 139 (削除ここまで) 137 bytes

Thanks @fireflame241 for helping me golf a couple of bytes (on Discord)

A=length(l)
B=[1...A-f]
Z=[0...A]
h(a,b)=\{\sum_{C=a}^bl[C]=0,0\}
f=\max((Z+1)\sign(\sum_{n=1+Z}^Ah(n-Z,n)))
g(l)=[f,\max(Bh(B,[f...A]))]

Uses Output Format #4. The first element in the outputted list is the length of the subarray, while the second element is the starting index of the subarray in respect to the inputted array.

Try It On Desmos!

Try It On Desmos! - Prettified(and a more verbose version)

Answer 19

PHP, (削除) 101 (削除ここまで), (削除) 99 (削除ここまで), 90

for(;$argc>$j=++$i;)for(;$j;)array_sum(array_slice($argv,$j--,$l=$argc-$i))||die("$j,$l");

Try It Online

Input is array elements as the command line argument list. Outputs the zero based start position and length of sub array. Does not output anything for the null case.

Answer 20

jq, 53 bytes

[.[keys[]:keys[]+1]|select(add==0)]|max_by(length)//.

Try it online!

Explanation:

[
 .[keys[]:keys[]+1] #calculates all subarrays
 |select(add==0) #selects these which add up to 0
]
|max_by(length) #picks the longest one
//. #if there is no such subarray returns an empty array

Answer 21

Vyxal 3 G, 3 bytes

Ṣz∑

Try it Online!

filter by falsy my beloved

Answer 22

Charcoal, 26 bytes

F⊕LθF⊕−Lθι⊞υ✂θκ+κι1I⊟Φυ¬Σι

Try it online! Link is to verbose version of code. Explanation:

F⊕LθF⊕−Lθι⊞υ✂θκ+κι1

Carefully list the subsequences of the input in ascending order of length.

I⊟Φυ¬Σι

Get those with a zero sum (or no sum at all, in the case of the empty subsequences) and output the last i.e. the longest.

Answer 23

Haskell, 88 bytes

f=head.filter((0==).sum).concat.iterate(concat.zipWith map[tail,init].replicate 2).(:[])

Try it online!