Elegant way to find contiguous subarray within an array in JavaScript?

Question

I wanted to write a function to find a contiguous subarray within a given array from a given starting index and return the index of the subarray within the array if it's found, and -1 if it's not found. This is similar to String.indexOf, but for arrays and subarrays instead of strings and substrings.

This is my working code:

var find_csa = function (arr, subarr, from_index) {
    if (typeof from_index === 'undefined') {
        from_index = 0;
    }

    var i, found, j;
    for (i = from_index; i < 1 + (arr.length - subarr.length); ++i) {
        found = true;
        for (j = 0; j < subarr.length; ++j) {
            if (arr[i + j] !== subarr[j]) {
                found = false;
                break;
            }
        }
        if (found) return i;
    }
    return -1;
};

And these are my tests and their expected values:

console.log(find_csa([1, 2, 3, 4, 5], [2, 3, 4]) === 1);
console.log(find_csa([1, 2, 3, 4, 5], [5]) === 4);
console.log(find_csa([1, 2, 3, 4, 5], [1, 3]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], [42]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], []) === 0);
console.log(find_csa([3, 4, 3, 4, 3, 4], [3, 4, 3], 1) === 2);
console.log(find_csa([6, 6, 6, 7], [6, 6, 7]) === 1);
console.log(find_csa([12, 9, 16, 42, 7, 866, 3], [16, 42, 7, 866]) === 2);

My code passes the tests, but as you can see, it uses a boolean value found in the inner loop which is just my messy, ad-hoc way of continuing an outer loop from a nested loop. is there a cleaner way of writing it? I looked into Array.prototype.findIndex but it is an experimental technology at the moment so I can't use it. I want a method that works in most browsers. I know there is a "polyfill" code snippet written on the Mozilla page, but that is even longer than my current code and it will be slower due to the function calls, so I'd rather avoid it.

My primary goal for this function is performance (the subarrays will be very small, so I believe that using Boyer-Moore string search algorithm or tries is a tad overkill), and then my secondary goal is elegance of my implementation. With those two goals in mind, I would like to know if there is a better way of writing this code, or if there are any JavaScript features or functions that I'm missing that could help me avoid the found boolean.

JSFiddle if it helps anyone: http://jsfiddle.net/qc4zxq2p/

Answer 1

Are there any JavaScript features or functions that I'm missing that could help me avoid the found boolean

Yes, you can use a label on your outer loop:

function find_csa(arr, subarr, from_index) {
    var i = from_index >>> 0,
        sl = subarr.length,
        l = arr.length + 1 - sl;

    loop: for (; i<l; i++) {
        for (var j=0; j<sl; j++)
            if (arr[i+j] !== subarr[j])
                continue loop;
        return i;
    }
    return -1;
}

Answer 2

This is the same as yours, just prettified a bit (at least to my aesthetics):

var find_csa = function (arr, subarr, from_index) {
    from_index = from_index || 0;

    var i, found, j;
    var last_check_index = arr.length - subarr.length;
    var subarr_length = subarr.length;

    position_loop:
    for (i = from_index; i <= last_check_index; ++i) {
        for (j = 0; j < subarr_length; ++j) {
            if (arr[i + j] !== subarr[j]) {
                continue position_loop;
            }
        }
        return i;
    }
    return -1;
};

Answer 3

The inner loop can be reduced to a single line using the array method every:

if(subarr.every(function(e, j) { return (e === arr[i + j]); })
    return i;

or (ES6 proposal):

if(subarr.every( (e, j) => (e === arr[i + j]) ))
    return i;

But this may be just a curiosity or educational example, unless you don't care about performance.

Answer 4

Inside your loop, you can eliminate the found variable and avoid continue like this:

for (j = 0; j < subarr.length; ++j) {
    if (arr[i + j] !== subarr[j]) break;
}
/*
 * the above loop breaks in two cases:
 * normally: j === subarr.length
 * prematurely: array items did not match
 * we are interested in kowing if loop terminated normally
 */
if (j === subarr.length) return i;

---

Having said that, here is my solution using Array.join and String.indexOf. This is only good for array of Numbers:

function find_csa(arr, subarr, from_index) {
    from_index |= 0;
    if (subarr.length === 0) {
        return from_index;
    }
    var haystack = "," + arr.slice(from_index).join(",") + ",",
        needle = "," + subarr.join(",") + ",",
        pos = haystack.indexOf(needle);
    if (pos > 0) {
        pos = haystack.substring(1, pos).split(",").length + from_index;
    }
    return pos;
}
console.log("All tests should return true");
console.log(find_csa([1, 2, 3, 4, 5], [1, 2, 3]) === 0);
console.log(find_csa([1, 2, 3, 4, 5], [2, 3, 4]) === 1);
console.log(find_csa([1, 2, 3, 4, 5], [5]) === 4);
console.log(find_csa([1, 2, 3, 4, 5], [6]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], [1, 3]) === -1);
console.log(find_csa([6, 6, 6, 7], [6, 6, 7]) === 1);
console.log(find_csa([1, 2, 3, 4, 5], []) === 0);
console.log(find_csa([3, 4, 3, 4, 3, 4], [3, 4, 3], 1) === 2);
console.log(find_csa([1, 2, 3, 4, 5], [], 1) === 1);

Answer 5

Reading initial discussion based on zerkms proposition, I was interested to try a solution using JSON.stringify, despite the unfavorable opinions.

Then I finally got a solution, which passes all tests properly.
Probably not the faster method, but surely the shortest one:

var find_csa = function (arr, subarr, from_index) {
  var start=from_index|0,
      needle=JSON.stringify(subarr),
      matches=JSON.stringify(arr.slice(start)).
      match(new RegExp('^\\[(.*?),?'+
        needle.substr(1,needle.length-2).replace(/([\[\]])/g,'\\$1')
      ));
  return !!matches?(matches[1].length?matches[1].split(',').length:0)+start:-1;
}

The above code accepts arrays of arrays, as suggested by Shashank, but fails to process items containing commas.

So I developped another solution which also accepts commas (thanks to Steven Levithan for the elegant tip about while(str!=(str=str.replace(regexp,replacement)));).

But it is only for fun, since:

• the code is not so short, now... Sigh!
• it probably consumes a lot of CPU time
• it doesn't properly work with empty items (they are ignored)
• I suspect (and didn't dig deeper :-) it might fail with complex objects as items

Anyway, here is it:

var find_csa = function (arr, subarr, from_index) {
  var start=from_index|0,
      commas=new RegExp('(?:(\')([^,\']+),([^\']+)\'|(")([^,"]+),([^"]+))"'),
      strip_commas='$1$2$3$1$4$5$6$4',
      haystack=JSON.stringify(arr.slice(start)),
      needle=JSON.stringify(subarr).replace(/^\[(.*)\]$/,'$1');
  while(haystack!=(haystack=haystack.replace(commas,strip_commas)));
  while(needle!=(needle=needle.replace(commas,strip_commas)));
  matches=haystack.match(new RegExp('^\\[(.*?),?'+needle.replace(/([\[\]])/g,'\\$1')));
  return !!matches?(matches[1].length?matches[1].split(',').length:0)+start:-1;
}

Answer 6

i fixed this question with this code:

 getCount(arr)
{
  const chunked = [];

  for(let i=0; i<arr.length; i++) chunked[i] = [];
  let sub = 0;
  for (let i = 1;  i < arr.length; i++) {
    if (arr[i]>arr[i-1]) {
      chunked[sub].push(...[arr[i-1],arr[i]]);
    } else {
      sub++
    }
  }
  const chunked2 = [...chunked.filter(k=>k.length).map(k => [...new Set(k)])];

  for (let i = 0; i < chunked2.length; i++) {
    if (chunked2[i+1])
    if( chunked2[i][chunked2[i].length - 1] > chunked2[i+1][0]) {
      chunked2[i+1].shift();
    }
  }
  return [].concat.apply([], chunked2).lenght;
}

Answer 7

I handle the outlier instances at the top and only looped once, checking to see if the current element was the same as the first element of the subarr.

If it was, I created a subarray to match the length of subarr, starting with the current index. I then used stringify to check if my created subarray matched subarr. If it did or the length was only 1 (which was already confirmed to match above), I returned the current index.

If no match was found -1 was returned.

function find_csa(arr, subarr, from_index) {
    
    if (typeof from_index === 'undefined') {
        from_index = 0;
    }
    if (subarr.length == 0) {
            return 0
    }

    
    for (let i = from_index; i < arr.length; i++) {
        if (arr[i] == subarr[0]) {
            if (subarr.length == 1 
                    || JSON.stringify(arr.slice(i, i + subarr.length))===JSON.stringify(subarr)) {
                return i
            }
        }
    }
    return -1
}