22
\$\begingroup\$

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]
\$\endgroup\$
5
  • \$\begingroup\$ Will there be any languages that an implementation of \$o(n^2)\$ algorithm is shorter than using \$\Omega(n^2)\$ algorithms? \$\endgroup\$
    – tsh
    Jul 19 at 8:55
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – DLosc
    Jul 19 at 19:10
  • \$\begingroup\$ @tsh Yes. \$\endgroup\$
    – Bubbler
    Jul 19 at 23:14
  • \$\begingroup\$ @DLosc Added. Though I don't quite understand how this happened. \$\endgroup\$
    – tsh
    Jul 20 at 1:12
  • \$\begingroup\$ @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].) \$\endgroup\$
    – DLosc
    Jul 20 at 16:34

22 Answers 22

17
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ 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 \$\endgroup\$
    – AShelly
    Jul 19 at 20:13
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jul 19 at 20:26
  • \$\begingroup\$ 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). \$\endgroup\$
    – xnor
    Jul 21 at 3:47
  • \$\begingroup\$ @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 \$\endgroup\$ Jul 21 at 4:05
7
\$\begingroup\$

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.

\$\endgroup\$
1
6
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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[]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Oh, I love the counter-intuitiveness of that ternary trick with the pop! \$\endgroup\$
    – Shaggy
    Jul 22 at 23:24
6
\$\begingroup\$

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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Well that was quick \$\endgroup\$
    – PyGamer0
    Jul 19 at 6:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – tsh
    Jul 19 at 6:33
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – hyper-neutrino
    Jul 19 at 6:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – tsh
    Jul 19 at 6:49
  • 2
    \$\begingroup\$ A Link that does the job in 7 bytes: ẆSÐḟṪȯ$ \$\endgroup\$ Jul 19 at 9:49
6
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ Dang, I had 18 bytes \$\endgroup\$
    – lyxal
    Jul 19 at 6:34
  • 2
    \$\begingroup\$ @lyxal did you manually implement sublist? \$\endgroup\$
    – Underslash
    Jul 19 at 6:35
  • 1
    \$\begingroup\$ Y...yes, I did. \$\endgroup\$
    – lyxal
    Jul 19 at 6:35
  • 2
    \$\begingroup\$ This is the first time I've ever remembered a command that you've forgotten, usually its the other way around. :) \$\endgroup\$
    – Underslash
    Jul 19 at 6:37
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Damn, you beat me to it. \$\endgroup\$
    – xigoi
    Jul 20 at 21:53
4
\$\begingroup\$

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

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 36 bytes \$\endgroup\$
    – att
    Jul 19 at 20:31
  • 2
    \$\begingroup\$ alternative 36 bytes \$\endgroup\$
    – att
    Jul 19 at 20:40
  • 1
    \$\begingroup\$ 35 bytes \$\endgroup\$
    – att
    Jul 20 at 1:35
  • \$\begingroup\$ @att Neat! I've never used the operator form of Select. \$\endgroup\$
    – theorist
    Jul 20 at 2:24
2
\$\begingroup\$

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

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 85 bytes by switching up the iteration logic to remove the need to find the maximum (and also outputting as start index and length). \$\endgroup\$ Jul 19 at 19:07
2
\$\begingroup\$

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
\$\endgroup\$
2
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ You can save 1 byte by declaring g=length instead of writing out length twice. \$\endgroup\$ Jul 24 at 19:20
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 73 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 26 bytes

F⊕LθF⊕⁻Lθι⊞υ✂θκ⁺κι¹I⊟Φυ¬Σι

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

F⊕LθF⊕⁻Lθι⊞υ✂θκ⁺κι¹

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.

\$\endgroup\$
0
\$\begingroup\$

Haskell, 88 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.