Javascript array contains/includes sub array

Asked 8/12, 2015 at 9:7 Answered 26/12, 2023 at 13:19

javascript arrays include contains indexof

I need to check if an array contains another array. The order of the subarray is important but the actual offset it not important. It looks something like this:

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 

var sub = [777, 22, 22];

So I want to know if master contains sub something like:

if(master.arrayContains(sub) > -1){
    //Do awesome stuff
}

So how can this be done in an elegant/efficient way?

Witherspoon answered 8/12, 2015 at 9:7 Comment(5)

Before doing it in an elegant way - implement it somehow first. Any thoughts? – Allargando 8/12, 2015 at 9:11

There is no elegant way in JS for your problem. You would better to look at JS libraries such as Underscore – Clearcole 8/12, 2015 at 9:14

"You have to look at libraries" --- that's too pessimistic, really. – Allargando 8/12, 2015 at 9:15

is it rigth, that you want to have in the right order found 777 ... 22... 222 in the master array? – Massey 8/12, 2015 at 9:23

@NinaScholz Yes, the order is important – Witherspoon 8/12, 2015 at 9:24

With a little help from fromIndex parameter

This solution features a closure over the index for starting the position for searching the element if the array. If the element of the sub array is found, the search for the next element starts with an incremented index.

function hasSubArray(master, sub) {
    return sub.every((i => v => i = master.indexOf(v, i) + 1)(0));
}

var array = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3];

console.log(hasSubArray(array, [777, 22, 22]));
console.log(hasSubArray(array, [777, 22, 3]));
console.log(hasSubArray(array, [777, 777, 777]));
console.log(hasSubArray(array, [42]));

Massey answered 8/12, 2015 at 9:28 Comment(4)

sub=[777, 22, 3] returns true. Is that intentional? OP did say "actual offset it not important" but I'm not quite sure what that means. – Inconsequent 11/9, 2018 at 21:58

I'm asking you if your code intentionally matches that, because just looking at your example I would have expected [777,22,22] has to be contiguous in the master array, but that's not the case. – Inconsequent 11/9, 2018 at 22:19

You've got another issue in there actually. It should index = i + 1 to prevent double-matching on the same character. Otherwise [777, 777, 777] also matches! – Inconsequent 11/9, 2018 at 23:26

@mpen, ad1 ([777, 22, 3]): yes, it is intentional, because 22 has a greater index than 777 and 3 ahs a greater index of 22. ad2 ([777, 22, 22]): that is true. ad3 ([777, 777, 777]): you are right, the found index has to be incremented. – Massey 12/9, 2018 at 8:11

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 

var sub = [777, 22, 22]; 

console.log(master.join(',').includes(sub.join(',')))

//true

You can do this by simple console.log(master.join(',').includes(sub.join(','))) this line of code using include method

Stefansson answered 6/10, 2020 at 3:37 Comment(2)

If the order is not important for you, you should first sort the arrays: var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; var sub = [777, 22, 22]; console.log(master.sort().join(',').includes(sub.sort().join(','))) – Nonsuit 29/8, 2023 at 9:37

This will also return true for [77, 22 ,22], [7, 22, 2], etc. – Calotte 16/12, 2023 at 22:15

It’s surprising how often this is implemented incorrectly.

What we’re looking for is a substring in the mathematical sense.

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters.

In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

A subsequence which consists of a consecutive run of elements from the original sequence, such as ⟨ B, C, D ⟩ from ⟨ A, B, C, D, E, F ⟩ is a substring.

Note that a “string”, here, can consist of any element and is not limited to Unicode code-point sequences.

Effectively all previous answers have one of many possible flaws:

The string concatenation approach (array1.toString().includes(array2.toString())) fails when your array elements have commas. (Example: [ "a", "b" ] does not contain [ "a,b" ]).
Some implementations check beyond array bounds. (Example: [ "3" ] does not contain [ "3", undefined ], just because array[1] reports undefined for both).
Some implementations fail to handle repetition correctly.
Some implementations aren’t checking for substrings (in the mathematical sense) correctly, but for subsets or subsequences or something else.
Some implementations don’t account for the empty array. The empty string is the substring of every string.

Check if an array constitutes a “substring” of another array

Right off the bat, this handles the empty array correctly.

Then, it builds a list of candidate starting indexes by matching against the first element of the potential subarray.

Find the first candidate where every element of the slice matches index by index with the full array, offset by the candidate starting index. The checked index also has to exist within the full array, hence Object.hasOwn.

const isSubArray = (full, slice) => {
    if(slice.length === 0){
      return true;
    }

    const candidateIndexes = full
        .map((element, fullIndex) => ({
          matched: element === slice[0],
          fullIndex
        }))
        .filter(({ matched }) => matched),
      found = candidateIndexes
        .find(({ fullIndex }) => slice.every((element, sliceIndex) => Object.hasOwn(full, fullIndex + sliceIndex) && element === full[fullIndex + sliceIndex]));

    return Boolean(found);
  };

console.log(isSubArray([], []) === true);
console.log(isSubArray([ 0 ], []) === true);
console.log(isSubArray([ 0, 1, 2 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === false);
console.log(isSubArray([ 2, 1 ], [ 1, 2 ]) === false);
console.log(isSubArray([ 1, 2, 3 ], [ 2, 3, undefined ]) === false);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === false);
console.log(isSubArray([ "a", "b" ], [ "a,b" ]) === false);

.as-console-wrapper { max-height: 100% !important; top: 0; }

This has quadratic complexity, yes. There might be more efficient implementations using Trees or Ropes. You might also want to research some efficient substring search algorithms and try to apply them to this problem.

Get the index of the found “substring”, or `-1` if not found

It’s basically the same code, but with return true; replaced by return 0;, and return Boolean(found); replaced by return found?.fullIndex ?? -1;.

const findSubArrayIndex = (full, slice) => {
    if(slice.length === 0){
      return 0;
    }

    const candidateIndexes = full
        .map((element, fullIndex) => ({
          matched: element === slice[0],
          fullIndex
        }))
        .filter(({ matched }) => matched),
      found = candidateIndexes
        .find(({ fullIndex }) => slice.every((element, sliceIndex) => Object.hasOwn(full, fullIndex + sliceIndex) && element === full[fullIndex + sliceIndex]));

    return found?.fullIndex ?? -1;
  };

console.log(findSubArrayIndex([], []) === 0);
console.log(findSubArrayIndex([ 0 ], []) === 0);
console.log(findSubArrayIndex([ 0, 1, 2 ], [ 1, 2 ]) === 1);
console.log(findSubArrayIndex([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === -1);
console.log(findSubArrayIndex([ 2, 1 ], [ 1, 2 ]) === -1);
console.log(findSubArrayIndex([ 1, 2, 3 ], [ 2, 3, undefined ]) === -1);
console.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === 1);
console.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === 2);
console.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === -1);
console.log(findSubArrayIndex([ "a", "b" ], [ "a,b" ]) === -1);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Semi-acceptable alternative: JSON

JSON-encoding both arrays might be a viable strategy as well. Here, the surrounding […] of the potential subarray need to be removed, then an includes will tell you if the JSON string is included in the other JSON string. This works — as opposed to the simple string concatenation or join approach — because JSON has delimiters that cannot appear verbatim in the encoded elements; if they do appear in the original elements, they’d be correctly escaped.

The caveat is that this won’t work for values that are not encodable in JSON.

const isSubArray = (full, slice) => JSON.stringify(full)
    .includes(JSON.stringify(slice).replaceAll(/^\[|\]$/g, ""));

console.log(isSubArray([], []) === true);
console.log(isSubArray([ 0 ], []) === true);
console.log(isSubArray([ 0, 1, 2 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === false);
console.log(isSubArray([ 2, 1 ], [ 1, 2 ]) === false);
console.log(isSubArray([ 1, 2, 3 ], [ 2, 3, undefined ]) === false);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === false);
console.log(isSubArray([ "a", "b" ], [ "a,b" ]) === false);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Archiepiscopal answered 15/10, 2022 at 16:55 Comment(0)

Just came up with quick thought , but efficiency depends on size of the array

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3];
var sub = [777, 22, 22];

if ((master.toString()).indexOf(sub.toString()) > -1 ){
    //body here
}

Flagrant answered 8/12, 2015 at 12:15 Comment(3)

This is actually the solution I went with in my implementation and I like it since it simple to understand. But I don't feel like it actually solves the problem because of two reasons: it could use prototype on array and I should get the actual index in the array (and not the string). Thanks! – Witherspoon 9/12, 2015 at 7:32

What if var master = [12, 44, 22, 66, 222, 777, 22, 224, 22, 6, 77, 3]; var sub = [777, 22, 22];? This would be very dangerous. – Suprarenal 9/9, 2016 at 11:59

@Suprarenal it could be something like someArray.map(value => value.toString()).join(";") so that the string would be delimited, avoiding false matches. – Bordie 31/1, 2020 at 16:43

The simplest way to match subset/sub-array

const master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 

const sub1 = [777, 44, 222]; 
const sub2 = [777, 18, 66]; 

sub1.every(el => master.includes(el));  // reture true
sub2.every(el => master.includes(el));  // return false

Marcellmarcella answered 4/3, 2022 at 6:31 Comment(1)

“The order of the subarray is important” — You totally ignore the order. – Archiepiscopal 15/10, 2022 at 15:12

If the order is important, it has to be an actually sub-array (and not the subset of array) and if the values are strictly integers then try this

console.log ( master.join(",").indexOf( subarray.join( "," ) ) == -1 )

for checking only values check this fiddle (uses no third party libraries)

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 

var sub = [777, 22, 22]; 

function isSubset( arr1, arr2 )
{
    for (var i=0; i<arr2.length; i++)
    {
        if ( arr1.indexOf( arr2[i] ) == -1 )
        {
          return false;
        }
    }
    return true;
}
console.log( isSubset( master, sub ) );

There are faster options explained here as well.

Diphthong answered 8/12, 2015 at 9:18 Comment(4)

@Allargando Why you say so? it is working. It outputs 'true' – Diphthong 8/12, 2015 at 9:21

Well, for my example it should have returned false – Allargando 8/12, 2015 at 9:22

@Allargando got it. take your point. Trying to come up with one now which can handle multiple instances of same value. – Diphthong 8/12, 2015 at 9:23

This fails to account for repetitions in the subarray. – Archiepiscopal 15/10, 2022 at 15:23

You can try with filter and indexOf like this:

Note: This code works in case we do not cover the order in sub array.

Array.prototype.arrayContains = function (sub) {
  var self = this;
  var result = sub.filter(function(item) {
    return self.indexOf(item) > -1;
  });
  return sub.length === result.length;
}

Example here.

UPDATED: Return index of sub array inside master (cover order in sub array)

Array.prototype.arrayContains = function(sub) {
  var first;
  var prev;
  for (var i = 0; i < sub.length; i++) {
    var current = this.indexOf(sub[i]);
    if (current > -1) {
      if (i === 0) {
        first = prev = current;
        continue;
      } else {
        if (++prev === current) {
          continue;
        } else {
          return -1;
        }
      }
    } else {
      return -1;
    }
  }
  return first;
}

Demo: here

Ese answered 8/12, 2015 at 9:30 Comment(2)

I like that you used prototype and that it's simple. If you can get it to return the array indexOf I'll be willing to accept as answer. – Witherspoon 9/12, 2015 at 7:35

This doesn’t return anything for empty subarrays. [1, 2, 2].arrayContains([2, 2]) should be true. – Archiepiscopal 15/10, 2022 at 15:31

EDIT

Misunderstood question initially.

function arrayContainsSub(arr, sub) {
        var first = sub[0],
            i = 0,
            starts = [];

        while (arr.indexOf(first, i) >= 0) {
            starts.push(arr.indexOf(first, i));
            i = arr.indexOf(first, i) + 1;
        }

        return !!starts
                    .map(function(start) {
                        for (var i = start, j = 0; j < sub.length; i++, j++) {
                            if (arr[i] !== sub[j]) {
                                return false;
                            }
                            if (j === sub.length - 1 && arr[i] === sub[j]) {
                                return true;
                            }
                        };

                    }).filter(function(res) {
                        return res;
                    }).length;
    }

This solution will recursively check all available start points, so points where the first index of the sub has a match in the array

Old Answer Kept in case useful for someone searching.

if(master.indexOf(sub) > -1){ //Do awesome stuff }

Important to remember that this will only match of master literally references sub. If it just contains an array with the same contents, but references a different specific object, it will not match.

Dragline answered 8/12, 2015 at 9:13 Comment(1)

arrayContainsSub([], []) and arrayContainsSub([ 3 ], []) should be true. arrayContainsSub([ 3, 4, 4 ], [ 4, 4, undefined ]) should be false. – Archiepiscopal 15/10, 2022 at 15:26

For this answer, I am preserving the order of sub-array. Means, the elements of sub-array should be in Consecutive order. If there is any extra element while comparing with the master, it will be false.

I am doing it in 3 steps:

Find the index of the first element of sub in the master and store it an array matched_index[].
for each entry in matched_index[] check if each element of sub is same as master starting from the s_index. If it doesn't match then return false and break the for loop of sub and start next for-loop for next element in matched_index[]
At any point, if the same sub array is found in master, the loop will break and return true.

function hasSubArray(master,sub){

    //collect all master indexes matching first element of sub-array
    let matched_index = [] 
    let start_index = master.indexOf(master.find(e=>e==sub[0]))
    
    while(master.indexOf(sub[0], start_index)>0){
        matched_index.push(start_index)
        let index = master.indexOf(sub[0], start_index)
        start_index = index+1
    } 

    let has_array //flag
    
    for(let [i,s_index] of matched_index.entries()){
        for(let [j,element] of sub.entries()){
            if(element != master[j+s_index]) {
                has_array = false
                break
            }else has_array = true
        }
        if (has_array) break
    }
    return has_array
}

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3];

console.log(hasSubArray(master, [777, 22, 22]));
console.log(hasSubArray(master, [777, 22, 3]));
console.log(hasSubArray(master, [777, 777, 777]));
console.log(hasSubArray(master, [44]));
console.log(hasSubArray(master, [22, 66]));

Nameless answered 12/8, 2019 at 21:31 Comment(1)

hasSubArray(master, []) should be true; hasSubArray(master, [ 3, undefined ]) should be false. – Archiepiscopal 15/10, 2022 at 15:59

Here's my offering. It seems to work nicely. First it looks through the whole master array for the first element in the sub array and keeps a list of candidates. Then it checks every candidate to see if the elements that follow match the sub array

const findSub = (master, sub) => {
  const candidates = [];
  const found = [];
  master.forEach((element, i) => {
    if (element === sub[0]) {
      candidates.push(i);
    }
  });
  candidates.forEach((candidate) => {
    if (master.slice(candidate, candidate + sub.length).every((element, i) => element === sub[i])) {
      found.push(candidate);
    }
  });
  return found;
}

Punic answered 26/12, 2023 at 13:19 Comment(0)

-1

If run this snippet below it should work

x = [34, 2, 4];
y = [2, 4];
y.reduce((included, num) => included && x.includes(num), true);

EDIT: @AlexanderGromnitsky You are right this code is incorrect and thank you for the catch! The above code doesn't actually do what the op asked for. I didn't read the question close enough and this code ignores order. One year later here is what I came up with and hopefully this may help someone.

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 
var sub = [777, 22, 22]; 
var is_ordered_subset = master.join('|').includes(sub.join('|'))

This code is somewhat elegant and does what op asks for. The separator doesn't matter as long as its not an int.

Mclaurin answered 22/3, 2017 at 18:9 Comment(1)

doesn't work: it should return false for y==[4,2] – Nash 25/3, 2018 at 11:22

-1

  async function findSelector(a: Uint8Array, selector: number[]): Promise<number> {
    let i = 0;
    let j = 0;
    while (i < a.length) {
      if (a[i] === selector[j]) {
        j++;
        if (j === selector.length) {
          return i - j + 1;
        }
      } else {
        j = 0;
      }
      i++;
    }
    return -1;
  }

Imitate answered 12/10, 2022 at 7:14 Comment(1)

Why is this an async function? findSelector([], []) and findSelector([ 2 ], []) should be true. – Archiepiscopal 15/10, 2022 at 15:34

-2

I had a similar problem and resolved it using sets.

function _hasSubArray( mainArray, subArray )
{
    mainArray = new Set( mainArray );
    subArray = new Set( subArray );

    for ( var element of subArray )
    {
        if ( !mainArray.has( element ) )
        {
            return false;
        }
    }
    return true;
}

Tahsildar answered 20/12, 2018 at 21:6 Comment(1)

_hasSubArray([23,34,45,56], [23,34,23]) // returns true, though should return false – Mabellemable 26/4, 2021 at 11:51

-3

Try using every and indexOf

var mainArr = [1, 2, 3, 4, 5]
var subArr = [1, 2, 3]

function isSubArray(main, sub) {
    return sub.every((eachEle) => {
        return (main.indexOf(eachEle) + 1);
    });
}
isSubArray(mainArr, subArr);

Madigan answered 19/12, 2019 at 14:23 Comment(1)

That's a good option if you don't search for the exact order of a subarray. OP mentioned that The order of the subarray is important, but in your case also [1,2,4] returns true – Mabellemable 26/4, 2021 at 11:56

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Check if an array constitutes a “substring” of another array

Get the index of the found “substring”, or -1 if not found

Semi-acceptable alternative: JSON

Recommended topics

Hot tags

Get the index of the found “substring”, or `-1` if not found