Given a list of lists find the shortest list that is a contiguous sublist of exactly one list.

For example if we had


the shortest contiguous sublist would be [3,4] since it only appears in the second list.

If there is no unique contiguous sublist (this requires at least one duplicate entry), output an empty list. Here is an example


If there are multiple contiguous sublists of minimal size, you may output any one of them or a list containing all of them. For example if the input was


You could output either [1,2], [2,3] or [[1,2],[2,3]]. If you choose to do the latter option you may output singleton lists for the cases where there is only one solution.

The output may occur in the same list more than once as long as it appears in no other list. For example


should output [1,2] because [1,2] is a sublist of the first list but not the second, even though it is a sublist of the first list in two different ways.

You may take as input a list of lists containing any type so long as that type has more than 100 possible values, i.e. no Booleans.

This is so answers will be scored in bytes with less bytes being better.

Test Cases

[[1,1]] : [1]
[[1],[1]] : []
[[1,1],[1]] : [1,1]

8 Answers 8


Husk, 12 14 15 bytes

+3 bytes for case [[1,1]]


Try it online!


          ṁ      -- map and concatenate
           ȯt    --   all but the first
             u   --   unique elements of
              Q  --   contiguous sublist
        ÖL       -- sort by length
Ṡḟ               -- find the first element satisfying this predicate
  ȯ¬€            --   not an element of
     Ṡ-          --   the list of sublists minus
       u         --   its unique elements

Note: Ṡ f g x = f (g x) x and this is hard to explain using the method above.

  • \$\begingroup\$ 14 bytes with a lambda. \$\endgroup\$
    – Zgarb
    Aug 12, 2017 at 23:44
  • \$\begingroup\$ That fails for [[1,1]] \$\endgroup\$
    – H.PWiz
    Aug 12, 2017 at 23:47
  • \$\begingroup\$ Hmm, and fixing that makes it over 15 bytes. Oh well. \$\endgroup\$
    – Zgarb
    Aug 13, 2017 at 1:33

Pyth, 15 bytes


Test suite

First, we generate all substrings of each input list with .:R)Q. Then, we generate all possible orderings, of those substring groups .p.

Now for the tricky part: -M. This folds the - function over each ordering list. It starts with the first substring list, then filters out all occupants of all of the other lists.

Then, the results are concatenated, ordered by length, a [] is appended, and then the first element of the resulting list is extracted with h.

This would be 4 bytes shorter if I could error on no unique sublists rather than output an empty list.

  • \$\begingroup\$ What is your 11-byte version? \$\endgroup\$
    – Leaky Nun
    Aug 12, 2017 at 19:58
  • \$\begingroup\$ @LeakyNun hlDs-M.p.:R is probably what he means. \$\endgroup\$ Aug 12, 2017 at 20:06

Pyth - 20 bytes


Test Suite.

  • \$\begingroup\$ Got 16 bytes, but I'm not sure this is correct. Otherwise it's pretty similar. \$\endgroup\$ Aug 12, 2017 at 19:08
  • \$\begingroup\$ @FryAmTheEggman cool, you should post it. \$\endgroup\$
    – Maltysen
    Aug 12, 2017 at 19:49
  • \$\begingroup\$ Fails for the recently added edge case test [[1,1]]. \$\endgroup\$ Aug 12, 2017 at 20:24

Haskell, 149 128 126 113 bytes

import Data.List
f l=[x|x<-l,sum[1|y<-l,y==x]<2]
i=h.f.sortOn length.(>>=tail.nub.(>>=tails).inits)

Try it online!

Saved 21 bytes thanks to Wheat Wizard, H.PWiz and Bruce Forte.

Saved two more bytes thanks to H.PWiz.

Saved 13 bytes thanks to nimi.

EDIT This was the original explanation:

  • a is a shortcut for joining lists.

  • s computes all the continous sublists (all tails from all inits). Note that nub keeps only the first occurence of each element, so tail will remove the empty list from the sublists.

  • g merges all sublists from all given lists in a big list of sublists, and sort them by length.

  • f f is a filter on elements that appear only once in the big list

  • h is a secure version of head

  • i is the glue

Quite inelegant! There should be a better solution...

  • 2
    \$\begingroup\$ It looks like a couple of your functions could be shorter if written as point-free functions. \$\endgroup\$
    – Wheat Wizard
    Aug 12, 2017 at 23:53
  • 1
    \$\begingroup\$ You also don't have to count the i= at the end of your program because point-free functions do not need to be assigned according to our rules. \$\endgroup\$
    – Wheat Wizard
    Aug 12, 2017 at 23:54
  • 2
    \$\begingroup\$ Is foldl1(++) just concat? \$\endgroup\$
    – H.PWiz
    Aug 12, 2017 at 23:55
  • 2
    \$\begingroup\$ (length$filter(==x)l) could be shorter as length(filter(==x)l) or even shorter as sum[1|y<-l,y==x] \$\endgroup\$
    – Wheat Wizard
    Aug 12, 2017 at 23:58
  • 2
    \$\begingroup\$ @H.PWiz Except for [] it is, but >>=id is even shorter ;) Also @jferard: You can inline a lot of functions (eg. f,g etc.) since you only use them once. \$\endgroup\$ Aug 13, 2017 at 0:02

Java 8, 251 + 19 = 270 bytes

A very gross lambda from, minimally, List<List> to List (best to cast it to Function<List<List<Integer>>, List<Integer>> though). It's a brute force solution that iterates chunk lengths from 1 to the size of the largest list, in each case iterating over every chunk of that length in every list and checking each such chunk against each chunk of equal size in every other list.

Fear me, garbage collector.

import java.util.*;

i->{int x,l=x=0,s,t;for(List z:i)x=Math.max(x,z.size());List r=i;while(l++<=x)for(List a:i)c:for(s=0;s<=a.size()-l;s++){for(List b:i)for(t=0;t<=b.size()-l;)if(b.subList(t,l+t++).equals(r=a.subList(s,s+l))&a!=b)continue c;return r;}return new Stack();}

Ungolfed lambda

i -> {
        l = x = 0,
        s, t
    for (List z : i)
        x = Math.max(x, z.size());
    List r = i;
    while (l++ <= x)
        for (List a : i)
            c: for (s = 0; s <= a.size() - l; s++) {
                for (List b : i)
                    for (t = 0; t <= b.size() - l; )
                        if (b.subList(t, l + t++).equals(r = a.subList(s, s + l)) & a != b)
                            continue c;
                return r;
    return new Stack();

Try It Online

Java 8, 289 + 45 = 334 bytes

This is a more functional approach using streams. If there were a method on Stream to reduce to only elements that appear once, this solution would have beaten the one above. Assign to the same type as above.

import java.util.*;import java.util.stream.*;

l->{List<List>o=l.stream().flatMap(a->IntStream.range(1,a.size()+1).boxed().flatMap(n->IntStream.range(0,a.size()-n+1).mapToObj(k->a.subList(k,k+n)))).collect(Collectors.toList());o.sort((a,b)->a.size()-b.size());for(List a:o)if(o.indexOf(a)==o.lastIndexOf(a))return a;return new Stack();}

Ungolfed lambda

l -> {
    List<List> o = l.stream()
        .flatMap(a -> IntStream.range(1, a.size() + 1)
            .flatMap(n -> IntStream.range(0, a.size() - n + 1)
                .mapToObj(k -> a.subList(k, k + n))
    o.sort((a, b) -> a.size() - b.size());
    for (List a : o)
        if (o.indexOf(a) == o.lastIndexOf(a))
            return a;
    return new Stack();

Try It Online


Jelly, 15 bytes


Try it online!

-3 bytes thanks to Jonathan Allan

  • \$\begingroup\$ Can ċ1 be replaced with S? \$\endgroup\$
    – user72349
    Aug 12, 2017 at 19:02
  • \$\begingroup\$ @ThePirateBay Indeed it can, thanks. I made a different version though. (though it would bring it to the same bytecount) \$\endgroup\$
    – hyper-neutrino
    Aug 12, 2017 at 19:05
  • \$\begingroup\$ Your new solution prints [1, 2, 1] for input [[1,2],[1,2,1],[2,1,1]] while [1,1] is shorter. \$\endgroup\$
    – user72349
    Aug 12, 2017 at 19:10
  • \$\begingroup\$ @ThePirateBay Fixed, thanks. \$\endgroup\$
    – hyper-neutrino
    Aug 12, 2017 at 19:11
  • 1
    \$\begingroup\$ @JonathanAllan oh um. I can't count whoops. :P \$\endgroup\$
    – hyper-neutrino
    Aug 12, 2017 at 20:44

05AB1E, 15 bytes


Try it online!


Pyth, 14 bytes


Try it here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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