Find Repeat Sequence in an Array

Question

I encountered a problem and have tried many solutions, but none have worked. Given an array of numbers [3, 2, 16, 16, 15, 1, 2, 16, 16, 16, 15, 1, 2], I would like to discover the repeated sequence in this array.

The expected output should be [16, 16, 15, 1, 2].

Skin

please ad at least one of your attempt. – Loyce

Welcome to StackOverflow! Please visit the Help Center and take the tour. I think you're going to need to explain a bit what makes for your repeated sequence. Because there are other candidates ([2, 16, 16] or [16, 15, 1, 2].) Are you looking for the longest one? The one repeated most often? Some combination of these? Something else? – Elouise

What you're describing is a task, not a problem. What have you done to attempt to solve your task? – Arad

Please provide enough code so others can better understand or reproduce the problem. – Informant

@ScottSauyet this totally ok, the first 16 is discarded in the second string – Memorize

The question is unclear -- are we looking for a cycle or subarray repetition at any position? Are we looking for the longest or the most repetitions? Etc. – Banns

Answer 1

You could take two nested loops and check the first and second same values with an offset for a sequence.

function longest(array) {
   let result = [];
   for (let i = 0; i < array.length - 1; i++) {
       for (let j = i + 1; j < array.length; j++) {
           let offset = 0;
           for (; offset + j < array.length; offset++) {
               if (array[i + offset] !== array[j + offset]) break;
           }
           if (result.length < offset) result = array.slice(i, i + offset);
       }   
   }
   return result;
}

console.log(longest([3, 2, 16, 16, 15, 1, 2, 16, 16, 16, 15, 1, 2]));

Loyce

Note that this solution is O(n^3). According to Wikipedia a clearly related problem can be solved in O(n). I'm pretty sure that a similar solution can be offered for an array of arbitrary numbers as for a string of fixed-alphabet characters. But I don't have time to try right now. – Elouise

@ScottSauyet could you check my answer and tell its complexity? i guess it's O(n^3) also. though big O doesn't always reflect performance. for the original array my func has the same speed as Nina's. the bigger array the bigger speed difference to my advantage. I guess the wikipedia's referenced O(n) algo isn't so fast due excessive tree parsing and traversing github.com/Daniel-Hug/longest-repeated-substring/blob/master/js/… – Memorize

@AlexanderNenashev: I'm not particularly good at that. Nina's answer was obvious, with three nested loops, each going to array.length. If I find time, I will try to look into this, but that's not likely for many hours, or maybe days. And there's no guarantee that I would find the complexity. But it looks like you also have a triple nested loop, so O(n^3) seems a likely minimum. – Elouise

Answer 2

Iterate elements and remember their indices in a map, when encountering a new element check whether it exists in the map and try to compare array parts from both indices:

` Chrome/120
-----------------------------------------------------------------
small original array
    Alexander     1.00x  |  x1000000  196  197  205  213  243
    Nina          1.05x  |  x1000000  206  207  208  214  217
    Unmitigated   6.02x  |   x100000  118  118  119  121  131
bigger array
    Alexander     1.00x  |  x1000000  531  542  549  553  559
    Nina          3.01x  |   x100000  160  162  162  163  164
    Unmitigated   8.98x  |   x100000  477  477  481  483  499
zero array with 1000 elements
    Alexander          1.00x  |  x100000  155  155  157  160  162
    Unmitigated     2206.45x  |     x100  342  345  348  350  351
    Nina          159354.84x  |       x1  247  249  250  250  250
-----------------------------------------------------------------
https://github.com/silentmantra/benchmark `

// Unmitigated
function longestRepeated(arr) {
  const len = Array.from({ length : arr.length + 1 }, 
                          _ => Array(arr.length + 1).fill(0));
  let maxLen = 0, end = 0;
  for (let i = 1; i < arr.length; i++)
    for (let j = i + 1; j <= arr.length; j++)
      if (arr[i - 1] == arr[j - 1]) {
        // to avoid overlapping, add check for j - i > len[i - 1][j - 1]
        len[i][j] = len[i - 1][j - 1] + 1;
        if (len[i][j] > maxLen) maxLen = len[i][j], end = i;
      }
  return arr.slice(end - maxLen, end);
}

// Nina
function longest(array) {
   let result = [];
   for (let i = 0; i < array.length - 1; i++) {
       for (let j = i + 1; j < array.length; j++) {
           let offset = 0;
           for (; offset + j < array.length; offset++) {
               if (array[i + offset] !== array[j + offset]) break;
           }
           if (result.length < offset) result = array.slice(i, i + offset);
       }   
   }
   return result;
}
// Alexander
function longest2(arr) {
  
  let maxRoot, maxCount = 0;
  
  const nums = {[arr[0]]:[0]};
  
  for(let i=1;i<arr.length-1-maxCount;i++){
    const n = arr[i];
    const nodes = nums[n];
    if(nodes){
     for(let j=0;j<nodes.length;j++){
        let count = 0, a = nodes[j], b = i;
        while(a < arr.length && b < arr.length && arr[a++] === arr[b++]) count++;
        if(maxCount < count){
          maxRoot = nodes[j];
          maxCount = count;
        }
      }     
    }
    (nums[n]??=[]).push(i);
  }


  return arr.slice(maxRoot, maxRoot + maxCount);
  
}
const arr =  [3, 2, 16, 16, 15, 1, 2, 16, 16, 16, 15, 1, 2];
const bigArr = [16, 15, 1, 2, 1, 2, 33, 4, 3, 2, 16, 16, 15, 1, 2, 4, 2, 2, 3, 4, 5, 6, 9, 16, 16, 16, 15, 1, 2, 3, 2, 4, 11, 40, 0, 2, 16, 15, 1, 2];
const zeroArray = Array(1000).fill(0);

// @group small original array
// @benchmark Unmitigated
longestRepeated(arr);

// @benchmark Nina
longest(arr);

// @benchmark Alexander
longest2(arr);

// @group bigger array
// @benchmark Unmitigated
longestRepeated(bigArr);

// @benchmark Nina
longest(bigArr);

// @benchmark Alexander
longest2(bigArr);

// @group zero array with 1000 elements
// @benchmark Unmitigated
longestRepeated(zeroArray);

// @benchmark Nina
longest(zeroArray);

// @benchmark Alexander
longest2(zeroArray);

/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));

Memorize

Answer 3

Simple dynamic programming yields a solution with O(n^2) time complexity.

function longestRepeated(arr) {
  const len = Array.from({ length : arr.length + 1 }, 
                          _ => Array(arr.length + 1).fill(0));
  let maxLen = 0, end = 0;
  for (let i = 1; i < arr.length; i++)
    for (let j = i + 1; j <= arr.length; j++)
      if (arr[i - 1] == arr[j - 1]) {
        // to avoid overlapping, add check for j - i > len[i - 1][j - 1]
        len[i][j] = len[i - 1][j - 1] + 1;
        if (len[i][j] > maxLen) maxLen = len[i][j], end = i;
      }
  return arr.slice(end - maxLen, end);
}
console.log(longestRepeated([3, 2, 16, 16, 15, 1, 2, 16, 16, 16, 15, 1, 2]));

Unread

strange, but it's slower than Nina's solution. Though with an array of 1000 zeroes, your O(n^2) becomes obvious. I've improved my solution and it really boosted. I'm bad at estimating time complexity I guess it's still O(n^3). Could you help with that? And how it's possible that O(n^3) beats O(n^2) seemingly in all test cases? Seem like language specific performance on read/writes in a particular algorithm. Also benchmarked it against your suffix tree approach here: #77857131 – Memorize