How to find subsequences of identical elements in an array

I am looking for an algorithm for my hobby task.

For example we have test data cases:

var case1 = ['green', 'red', 'red', 'blue', 'green', 'green', 'green'];
var case2 = ['blue', 'blue', 'green', 'yellow', 'blue', 'orange', 'green', 'green', 'green', 'green'];
var case3 = ['purple', 'blue', 'blue', 'blue', 'red'];

Output:

var result1 = ['red', 'red', 'green', 'green', 'green'];
var result2 = ['blue', 'blue', 'green', 'green', 'green', 'green'];
var result3 = ['blue', 'blue', 'blue'];

Can anybody tell me which algorithm I should use? The classic way with duplicates - not like I looking.

2 answers

  • answered 2021-02-22 22:39 zaitsman

    So in javascript a naive implementation would be:

    function selectSequential(source) {
       var result = [];
       for (let i = 0; i < source.length; i++) {
          if ((i != source.length-1 && source[i+1] === source[i]) 
                || (i != 0 && source[i-1] === source[i])) {
             result.push(source[i]);
          }
       }
       return result;
    }
    

  • answered 2021-02-22 22:52 OmG3r

    Short version

    we can use the .filter function to achieve this behavior.

    .filter((item, i, array) => array[i - 1] == item || item == array[i + 1])
    

    let case1 = ['green', 'red', 'red', 'blue', 'green', 'green', 'green'];
    let case2 = ['blue', 'blue', 'green', 'yellow', 'blue', 'orange', 'green', 'green', 'green', 'green'];
    let case3 = ['purple', 'blue', 'blue', 'blue', 'red'];
    
    let result1 = case1.filter((item, i, array) => array[i - 1] == item || item == array[i + 1])
    let result2 = case2.filter((item, i, array) => array[i - 1] == item || item == array[i + 1])
    let result3 = case3.filter((item, i, array) => array[i - 1] == item || item == array[i + 1])
    
    console.log(result1)
    console.log(result2)
    console.log(result3)

    out of bounds index in javascript will return undefined which will evaluate to false in your comparison