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

Javascript – Find Repeat Sequence in an Array

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

Tags:

2

Answers


  1. 0

    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]));
    Login or Signup to reply.
  2. 0
    1. Convert the array to a linked list and collect nodes as starting points for comparison grouped into arrays by the start node value
    2. Iterate node groups and find the lonest linked chain starting with the same value

    I’ve compared to Nina’s solution. While with small arrays Nina’s solutions wins because there’s nothing to initialize. But with increasing number of elements and repeated parts my algorithm get more faster due the linked list optimization. I even think there’re even some more optimization possible.

    ` Chrome/120
------------------------------------------------------
Alexander   1.00x  |  x100000  107  117  118  124  132
Nina        1.43x  |  x100000  153  158  163  166  168
------------------------------------------------------
https://github.com/silentmantra/benchmark `

    // 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) {

  const nums = {};
  let next;
  for(let i=arr.length-1;i>0;i--){
    (nums[arr[i]]??=[]).push (next = {val:arr[i], next});
  }

  let maxRoot, maxCount = 0;
  for(const n in nums){
    const nodes = nums[n];
    
    if(nodes.length<2) continue; // skip unique numbers

    for(let i=0;i<nodes.length-1;i++){
      for(let j=i+1;j<nodes.length;j++){
        const root = nodes[i];
        let count = 1;
        let a = root.next;
        let b = nodes[j].next;
        while(a && b && a.val === b.val){
          count++;
          a = a.next;
          b = b.next;
        }
        if(maxCount < count){
          maxRoot = root;
          maxCount = count;
        }
      }
    }
    
  }
  const result = [];
  
  while(maxCount--){
    result.push(maxRoot.val);
    maxRoot = maxRoot.next;
  }
  return result;
}

const arr = [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];

// @benchmark Nina
longest(arr);

// @benchmark Alexander
longest2(arr);

/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search