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]

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...

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.

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[]

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

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.

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!

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

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

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

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!

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

Ṣᶻ∑

Try it Online!

filter by falsy my beloved

Answer 22

Charcoal, 26 bytes

Ｆ⊕ＬθＦ⊕⁻Ｌθι⊞υ✂θκ⁺κι¹Ｉ⊟Φυ¬Σι

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

Ｆ⊕ＬθＦ⊕⁻Ｌθι⊞υ✂θκ⁺κι¹

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

Ｉ⊟Φυ¬Σι

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!