Question 325038 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Longest Repeating Subarray (With Overlapping)

Greetings fellow users and i hope your having a nice day. I have a doubt.

Given an array of arbitrary numbers, i am looking to quickly [with time and space complexity lower than O(n²) at minimum, n = length of array] find the longest subarray (a contigous segment of elements within array) that is repeated (appears more than once, or at least twice). Please don’t assume any bounds on the numbers in the array apart from all the values are valid JavaScript numbers and isFinite is true for every number in the array

overlaping is allowed, that is partial occurences 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

The two occurences overlap, but that is a-ok as long as the two occurence differ in either starting or ending index.

In case there are multiple distinct repeated subarrays that all have the longest length, the answer can be any of them. However, I suspect that any way that can find one answer can find all of them with the same ease.
A sample for this scenario is the array [1, 1, 2, 2]. The subarray [1] and [2] both appear twice. Either of those may be returned as the result.

Finally, if no subarray occurrs more than once, the answer is [] (the empty array).

i recently came across the question Find Repeat Sequence in an Array but all the answers there are ridiculously slow. Everyones using o(n³) solutions, with only one answer in o(n²). I’m seeking a method that can handle arrays with length up to a couple hundred thousand (100,000) in a few seconds. Sub quadratic time complexity at least.

Sorry for the long question, let me know if anything is unclear. If you have an idea but not a full solution just drop it in the comments, it can still be helpful to me. Thank you all in advance

I made some more examples if it helps:

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]

Here’s a function to generate large test case with array size 100,000 for reference, 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;
}
Tags:

2

Answers


  1. 0

    Looks pretty simple, u can achieve with some loops. This is untested but should works

    var solve = (input) => {
    var ans, s, s2, ii, _ans
    s = 0
    ans = []
    while (s < input.length) {
    s2 = s + 1
    while (s2 < input.length) {
    ii = 0
    _ans = []
    while (ii + s2 < input.length) {
    if (input[s+ii] != input[s2+ii]) {
    break
    } else {
    _ans.push(input[s+ii])
    ii++
    }
    }
    if (ii > ans.length) {
    console.log(s, s2, ii, _ans)
    ans = _ans
    }
    s2++
    }
    s++
    }
    return ans
    }

    hth

    Login or Signup to reply.
  2. 0

    We can iterate an array and remember in an object which values are at which indices (in an array).

    So when we encounter the same value we can quickly check the array iterating from the remembered indices.

    That would give a quite performance boost with long arrays since we need to check only limited set of indices:

    console.log(...longest([9, 7, 0, 1, 6, 3, 6, 5, 2, 1, 6, 3, 8, 3, 6, 1, 6, 3]));
console.log(...longest(make_case()));
function longest(arr) {
  
  let maxRoot, maxCount = 0; // the index from which the repeated sequence starts and its length;
  
  const nums = {[arr[0]]:[0]}; // init the index map with the first element
  
  for(let i=1;i<arr.length-1;i++){ // iterate from the second element
    const n = arr[i];
    const nodes = nums[n];
    if(nodes){ // there's already the same value encountered previously
     for(let j=0;j<nodes.length;j++){ // iterate from this value at the remembered indices
        let count = 0, a = nodes[j], b = i; // iterate from the current and remembered indices
        while(a < arr.length && b < arr.length && arr[a++] === arr[b++]) count++; // loop from the index, break when values don't match
        if(maxCount < count){ // if count of the repeating values bigger than previous, overwrite
          maxRoot = nodes[j]; // index from which the max repeat sequence is found
          maxCount = count;
        }
      }     
    }
    (nums[n]??=[]).push(i); // remember the current value in the index map
  }


  return arr.slice(maxRoot, maxRoot + maxCount); // get a slice from the array with the found index and length
}
    <script>
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;
}
</script>
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search