8
\$\begingroup\$

Earlier I asked about this problem on stackoverflow (link), but now I also want to see the golfiest solutions

Problem:

Given an array of arbitrary numbers, what is the longest subarray that is repeated (appears more than once)? In case there are multiple distinct repeated subarrays that all have the longest length, the answer can be any of them. If no subarray appears more than once, the answer is [] (the empty array).

Overlapping is allowed, that is partial occurrences of a subarray within itself is allowed. for ex, in the array [1, 2, 1, 2, 1, 2] the longest repeating subarray is [1, 2, 1, 2]. Look here

[1, 2, 1, 2, 1, 2]
^         ^        occurence #1
       ^        ^  occurence #2

Constraints:

For the sake of code golf simplicity, assume that all values in the array are integers. like a 32bit int data type

The time complexity and the space complexity must be \$O(n^{2 - \varepsilon})\$ where \$n\$ = length of array, for some \$\varepsilon > 0\$.

Test cases:

Array Result
[1, 2, 5, 7, 1, 2, 4, 5] [1, 2]
[9, 7, 0, 1, 6, 3, 6, 5, 2, 1, 6, 3, 8, 3, 6, 1, 6, 3] [1, 6, 3]
[1, 2, 1, 2, 7, 0, -1, 7, 0, -1] [7, 0, -1]
[1, 1, 1, 1] [1, 1, 1]
[1, 1, 1] [1, 1]
[1, 2, 3, 4, 2, 5] [2]
[1, 2, 3, 4, 5] []
[1, 6, 2, 1, 6, 2, 1, 5] [1, 6, 2, 1]

Also this JS code generates a large test case with an array of one hundred thousand elements which your program should be able to handle. The answer is [1, 2, 3, ..., 100] (the 100 consecutive integers from 1 to 100)

function make_case() {
    let array = [];
    let number = 200;
    for (let i = 0; i < 500; i++) {
        array.push(number); array.push(number);
        number++;
    }
    for (let i = 1; i < 101; i++) {
        array.push(i);
    }
    for (let i = 0; i < 1700; i++) {
        array.push(number); array.push(number);
        number++;
    }
    for (let i = 1; i < 101; i++) {
        array.push(i);
    }
    for (let i = 0; i < (100_000 - 500 * 2 - 100 - 1700 * 2 - 100) / 2; i++) {
        array.push(number); array.push(number);
        number++;
    }
    return array;
}
\$\endgroup\$
10
  • \$\begingroup\$ Nice first challenge! Does lower than \$O(n^2)\$ mean strictly lower (\$o(n^2)\$)? You might want \$O(n^{2-\varepsilon})\$, unless you are ok with \$O(\frac{n^2}{\log n})\$. Are hashing-based solutions (which are only correct with high probability) ok? \$\endgroup\$ Jan 22 at 5:45
  • 1
    \$\begingroup\$ @CommandMaster Sorry could you explain what n^(2-epsilon) means there and how the meaning changes? I'm looking for solutions that are accurate, not based on probability, but I'm open to changing that. Thanks for feedback! \$\endgroup\$ Jan 22 at 5:51
  • 1
    \$\begingroup\$ \$n^{2-\varepsilon}\$ means that there must be some \$\varepsilon>0\$ such that the solution is \$O(n^{2-\varepsilon})\$. This is just a bit tighter than \$o(n^2)\$, as it prevents things like \$O(\frac{n^2}{\log n})\$ \$\endgroup\$ Jan 22 at 6:05
  • \$\begingroup\$ @CommandMaster I think I get it, I'll edit \$\endgroup\$ Jan 22 at 6:11
  • 2
    \$\begingroup\$ For complexity reason are all numbers O(n)? \$\endgroup\$
    – l4m2
    Jan 22 at 7:41

1 Answer 1

4
\$\begingroup\$

C++ (gcc), 378 360 359 339 337 bytes, \$O(n \sqrt{n} \log^2 n)\$

#import<bits/stdc++.h>
using V=std::vector<int>;V f(V a){int l=0,r=a.size(),n,j,i=0,m,L=r,s=sqrt(r);std::map<V,int>M;V v(L),x;for(;i+s<L;)v[i++]=M[x]=M[x=V(&a[i],&a[i+s])]?:~i;for(;M.clear(),l<r;l>m?:r=m)for(i=m=l+r>>1;i<=L;i++){V x;for(j=i-m;j<i;j+=j+s<i?s:1)x.push_back((j+s<i?v:a)[j]);l=M[x]++?n=i-m,m+1:l;}return V(&a[n],&a[n-1+l]);}

Try it online!

-3 thanks to @Unmitigated. -1 thanks to @movatica. -11 thanks to @ceilingcat. -2 thanks to @ceilingcat.

Mostly ungolfed:

#include <bits/stdc++.h>
using V=std::vector<int>;
V f(V a) {
    int l=0,r=a.size(),n,j,i,m,b,L=r,s=sqrt(r);
    std::map<V,int> M;
    V v(L);
    for(int i=0;i+s<L;i++) {
        V x(a.begin()+i,a.begin()+i+s);
        v[i]=M[x]=M[x]?M[x]:~i;
    }
    while (l<r) {
        m = (l+r)/2;
        b=0;
        std::set<V> S;
        for (i=m;i<=L;i++) {
            V x;
            for(j=i-m;j<i;j+=j+s<i?s:1)x.push_back((j+s<i?v:a)[j]);
            S.insert(x).second||(n=i-m,b=1);
        }
        b?l=m+1:r=m;
    }
    return V(a.begin()+n,a.begin()+n-1+l);
}

uses binary search, and sqrt decomposition for fast-ish substring comparison.

Takes a few seconds for the \$n=100000\$ case when compiled with -O2.

\$\endgroup\$
3
  • \$\begingroup\$ You can remove a few spaces: #include<bits/stdc++.h> and std::map<V,int>M;. \$\endgroup\$ Jan 22 at 14:13
  • \$\begingroup\$ oh wow I didn't think of square root decomposition would work \$\endgroup\$ Jan 22 at 22:26
  • \$\begingroup\$ Converting the first for loop to while saves another byte: while(i+s<L){V x(&a[i],&a[i+s]);v[i++]=M[x]=M[x]?M[x]:~i;} \$\endgroup\$
    – movatica
    Jan 23 at 16:11

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.